A modified A* algorithm for robust plan recognition

It is shown that the A* algorithm can be directly applied to the basic plan recognition problem while keeping its desirable properties of admissibility and the possibility of polynomial runtime. Two relatively minor modifications can extend the robustness by allowing the algorithm to recognize situations in which the user has an incorrect plan. Four algorithms are presented, starting with a direct adaptation of A* for recognizing correct plans, and progressing to an optimized algorithm for recognizing violated, ill-formed plans