Introduction
Plan Recognition (PR) is the task of observing an agent's actions and inferring their underlying goals and future steps. This capability is essential for applications ranging from assistive robotics to cybersecurity. Traditionally, PR systems have relied on grammars to represent the hierarchical structure of plans. Specifically, Combinatory Categorial Grammars (CCGs)—originally developed for natural language processing—have proven effective due to their ability to handle complex, interleaved, and non-linear plan structures. However, a major hurdle in deploying these systems is the need for hand-coded grammars, a process that is labor-intensive and requires significant domain expertise.
The $LEX_{learn}$ Algorithm
To overcome the limitations of manual grammar engineering, this paper introduces $LEX_{learn}$, a supervised learning algorithm that automatically induces CCG lexicons from successful execution traces. Unlike linguistic CCG induction, which relies on predefined parts-of-speech, $LEX_{learn}$ is domain-independent. It treats the final goal state of a plan as the "meaning" of the observed action sequence.
The algorithm builds a plan lexicon through two interleaved processes:
- LexGen (Lexicon Generation): When the system encounters a sequence of actions it cannot parse, it proposes new "complex categories." These are formed using templates that define how actions combine to achieve goals. For instance, an action might be categorized as "expecting another action to its right to satisfy a specific goal."
- ParamEst (Parameter Estimation): To handle ambiguity, the algorithm uses gradient ascent to update the probabilities of action-to-category mappings based on their success in explaining training data.
To ensure the learned grammar remains generalizable, the authors impose a "two-argument limit" on categories. This prevents the system from simply memorizing long, specific sequences and instead forces it to discover reusable, hierarchical sub-plans.
Experimental Evaluation
The authors evaluated $LEX_{learn}$ across five diverse planning domains: Rovers (autonomous exploration), Depots (logistics with crates), Logistics (package delivery), Satellites (space imaging), and Monroe (disaster relief). Training data consisted of execution traces from automated planners, with varying levels of "noise" (0% to 25%) introduced to simulate real-world observation errors, such as dropped or shuffled actions.
Key Results and Insights
The primary performance metric was the F1 score, which measures the accuracy of goal identification.
As illustrated in Figure 1, $LEX_{learn}$ achieved high F1 scores across most domains. In the Monroe disaster relief domain, it maintained an F1 score above 0.8 even at 10% noise. A surprising finding was the stability of the Logistics domain under noise; the authors suggest that noise may act as a regularizer, preventing the learner from overfitting to specific "perfect" traces and encouraging the discovery of more robust, general categories.
The system was also evaluated on Mean-Time-To-Recognition (MTTR). In the Rovers domain, the goal was correctly identified after observing roughly 56% of the plan, while the more complex Monroe domain required nearly the entire trace (93%) for confident recognition.
Discussion
A key advantage of the learned CCGs is their compactness and flexibility compared to traditional Hierarchical Task Network (HTN) representations. $LEX_{learn}$ successfully identified common sub-sequences as reusable units, a task that often stymies traditional HTN learners like HTN-Maker. Furthermore, the CCG framework naturally captures non-right-recursive structures, allowing for more natural representations of plans where action ordering is partially flexible.
Conclusion
$LEX_{learn}$ provides a powerful, domain-independent method for learning the structural "grammar" of agent behavior. By automating the creation of CCG lexicons, it significantly lowers the barrier to building robust and scalable plan recognition systems. Future work will explore learning more complex category structures and automatically estimating prior goal probabilities from training data.
Summary updated