Introduction
Plan recognition involves inferring an agent's top-level goals and specific plans from observed actions. While algorithmic efficiency is often the focus of research, this study shifts the lens toward the inherent complexity of the "plan library"—the set of rules defining goal achievement. The core challenge lies in domains where multiple interleaved goals or multiple instances of the same goal (e.g., concurrent cyber attacks) are possible, making the problem computationally daunting regardless of the algorithm used.
Modeling Plan Libraries with HTNs
The research utilizes Hierarchical Task Networks (HTNs) to represent plan libraries. In this model, AND nodes signify that all child actions must be completed, while OR nodes represent choices between alternative paths. Directed arcs indicate strict ordering constraints.
An explanation is defined as a minimal forest of plan trees accounting for all observed actions. Complexity is measured by how the number of valid explanations grows as new observations are added, focusing on "attachment points" and "leaders"—the basic actions that initiate a new goal instance.
The Combinatorics of Complexity
A primary source of computational difficulty is the "Unordered Leader" trap. When goals can begin with several different actions in any order, the system must consider every possible distribution of these actions across potential goal instances. The research employs Stirling Numbers of the Second Kind to describe the distribution of $m$ observed leaders into $i$ root goals.
This results in a complexity lower-bound of $n^m$, where $n$ is the number of goals and $m$ is the number of observations. Conversely, simply adding a requirement that actions must happen in a specific order can collapse the number of possible explanations from exponential to linear.
Key Results and Design Implications
The analysis demonstrates that for plan libraries with $m$ unordered leaders shared by $n$ root goals, the explanation space grows exponentially. To maintain tractability, library designers should:
- Minimize common prefixes: Keep initial shared actions between different plans as short as possible to prevent the system from remaining "agnostic" about the true goal for too long.
- Enforce early ordering: Introduce constraints as soon as possible to prune the hypothesis space.
Furthermore, the study suggests that incremental recognition algorithms are superior to those attempting to enumerate the entire explanation space upfront, which is often doomed to fail in complex domains.
Future Directions
While providing a robust lower bound, this analysis acknowledges further complexities in real-world scenarios, such as partial observability, plan abandonment, and observational uncertainty. Future work aims to integrate these factors to understand their compounding effects on computational tractability.
Summary updated