Abstract
Goal recognition is a critical task for intelligent systems, yet traditional planning-based approaches are often too computationally expensive for real-time applications. This paper presents a novel technique that leverages plan graph heuristics and interaction estimates to achieve significant speedups. By accounting for subgoal dependencies and utilizing incremental pruning, the proposed method provides accurate goal estimates up to two orders of magnitude faster than state-of-the-art planners.
Introduction
Goal recognition involves inferring an agent's intended objective from a sequence of observed actions. This capability is essential for proactive assistants, human-robot interaction, and security monitoring. The prevailing paradigm, established by Ramírez and Geffner, relies on comparing the costs of optimal plans with and without the constraint of matching observed actions. While theoretically sound, this "gold standard" requires multiple calls to an AI planner for every potential goal, leading to prohibitive latency in complex or multi-goal environments.
Methodology: Interaction Estimates and Plan Graphs
To overcome the bottlenecks of full planning, the authors propose a heuristic-based approach centered on plan graphs and interaction estimates.
Plan Graph Cost Estimation
Instead of exhaustive search, the method propagates costs through a plan graph—a layered structure of reachable states and actions. This provides a fast approximation of the effort required to reach a goal.
Interaction Estimates ($I^*$)
Traditional heuristics often assume subgoals are independent, which can lead to significant inaccuracies. This work incorporates "interaction estimates" to account for synergy (where subgoals share costs) or interference (where achieving one subgoal complicates another). This allows for more nuanced cost calculations than simple reachability analysis.
Incremental Pruning (IPR)
The system employs Incremental Plan Recognition to refine the plan graph based on observations. Actions inconsistent with observed behavior are pruned, effectively narrowing the search space to paths that respect the agent's visible actions. This pruning is handled flexibly using "earliest time steps" to accommodate sequential observations without rigid timing constraints.
Experimental Evaluation
The technique was evaluated across several standard AI planning benchmarks, including BlocksWorld, Intrusion, Kitchen, Logistics, Campus, and Easy Grid. Each domain featured 15 problems with varying levels of observability, ranging from 10% to 100% of the total plan.
Results and Discussion
The experimental results demonstrate that the proposed heuristic approach offers a compelling trade-off between speed and accuracy.
Key Findings
- Computational Efficiency: The method consistently outperformed full-planning approaches like LAMA and HSP* by up to 100x. In the "Easy Grid" domain, it solved problems in seconds that took other methods minutes.
- High Recognition Quality: Despite the heuristic nature of the estimates, the accuracy ($Q$)—the frequency with which the true goal was ranked as most likely—remained high. The system effectively identified the true goal, particularly when at least 30-50% of the plan was observed.
- The Role of Interaction: Accounting for action interference (mutual exclusion) proved crucial. It allowed the system to rule out impossible goals much faster than simple reachability analysis.
Conclusion and Future Work
This research highlights that perfect planning is not always necessary for effective goal recognition; accurate cost estimates often suffice. While the current model assumes noise-free observations, future iterations could incorporate probabilistic reasoning to handle sensor errors. Additionally, extending the framework to temporal planning with concurrent actions remains a promising avenue for robotics applications.
Summary updated