Recognizing plans with loops represented in a lexicalized grammar

This paper extends existing plan recognition research to han- dle plans containing loops. We supply an encoding of plans with loops for recognition, based on techniques used to parse lexicalized grammars, and demonstrate its effectiveness em- pirically. To do this, the paper first shows how encoding plan libraries as context free grammars permits the applica- tion of standard rewriting techniques to remove left recursion and ε-productions, thereby enabling polynomial time parsing. However, these techniques alone fail to provide efficient algo- rithms for plan recognition. We show how the loop-handling methods from formal grammars can be extended to the more general plan recognition problem and provide a method for encoding loops in an existing plan recognition system that scales linearly in the number of loop iterations.