Introduction
Goal Recognition (GR) is the process of inferring an agent's intended goal from a sequence of observed actions. While modern GR systems often leverage classical planning techniques, they typically rely on a perfectly accurate "snapshot" of the world—the initial state. In real-world scenarios, sensors are often noisy or occluded, leading to missing or incorrect information. Traditional planning-based recognizers are brittle; if the initial state suggests a goal is unreachable, the system may fail entirely. This paper proposes Action Graphs, a framework that shifts the focus from state-space search to structural dependencies, ensuring robustness against initial state inaccuracies.
Methodology: The Action Graph Framework
The core contribution is the Action Graph, a cyclic structure that maps logical dependencies between actions rather than simulating state transitions.
Graph Construction
The graph consists of action nodes and logical operator nodes that define how requirements are satisfied:
- DEP (Dependency): Indicates a strict temporal ordering where one action must precede another.
- AND (Ordered/Unordered): Specifies that multiple actions are required to fulfill a condition.
- OR: Represents multiple alternative paths to satisfy a requirement.
By filtering actions based only on static properties (e.g., fixed environmental layouts) and ignoring potentially incorrect dynamic properties (e.g., current object locations), the graph maintains all theoretically possible plans. This ensures that the path to a goal remains available even if the initial state is misreported.
Inference and Probability
The system operates in two phases. Offline, it uses breadth-first traversal to calculate the "distance" from every action to every potential goal. Online, as actions are observed, the system updates goal probabilities based on whether new observations move the agent "closer" to a specific goal in the graph. Crucially, probabilities are never set to zero, allowing the system to recover from noisy or unexpected observations.
Experimental Evaluation
The authors evaluated the Action Graph approach across 15 standard AI planning domains. To simulate real-world noise, they injected varying levels of inaccuracy into the initial state, ranging from 10% to 100% of fluents being incorrect.
Key Results
The performance of Action Graphs was compared against a state-of-the-art landmark-based heuristic, $h_{gc}$.
As shown in the results, the Action Graph approach demonstrates remarkable stability. While the $h_{gc}$ baseline's accuracy drops sharply as the initial state becomes more corrupted, the Action Graph maintains a nearly constant F1-score. Even at 100% inaccuracy—where the initial state provides no useful information—the structural dependency model continues to perform effectively.
Conclusion and Future Work
By decoupling goal recognition from the fragile state-space search of traditional planning, Action Graphs provide a resilient solution for messy, real-world environments. Future research will focus on improving the scalability of graph construction for large-scale domains and integrating more formal Bayesian frameworks for probability updates. Currently, the system remains dependent on accurate static environmental data; addressing errors in these fundamental "maps" remains an open challenge.
Summary updated