Abstract
Plan recognition often suffers from "ambiguity explosion," where a few observed actions can be explained by thousands of different potential plans. This paper introduces the Sequential Plan Recognition Process (SPRP), a framework that strategically queries the agent to disambiguate hypotheses using information theory, significantly pruning the search space while ensuring the correct plan is never accidentally discarded.
The Challenge of Ambiguity Explosion
In Plan Recognition (PR), an observer attempts to infer an agent's goals and future actions based on observed behavior. A major hurdle in complex, open-ended environments—such as a student using chemistry lab software—is ambiguity. A handful of actions might be consistent with tens of thousands of different plan hypotheses.
Existing algorithms typically rank these hypotheses by probability but lack mechanisms to actively narrow them down. While direct questioning is an option, humans often struggle to describe complex hierarchies, and excessive querying is intrusive. The authors address this through optimal disambiguation: choosing the minimum number of simple "yes/no" queries to identify the correct plan in real-time.
The Sequential Plan Recognition Process (SPRP)
The SPRP framework introduces two novel components to manage the hypothesis space:
- Sound Pruning with Incomplete Plans: Because PR occurs while the agent is still active, many hypotheses contain "incomplete" plans with future steps not yet taken. The authors define a Matching criterion ($p \approx^m p'$). This ensures that when a query is answered, the algorithm only removes hypotheses that cannot possibly be refined into the correct one, maintaining both soundness and completeness.
- Probing Policies: The researchers compared several heuristics for selecting which plan to query:
- Most Probable Hypothesis (MPH): Queries a plan from the single most likely hypothesis.
- Most Probable Plan (MPP): Queries the plan appearing with the highest cumulative probability across all hypotheses.
- Minimal Entropy (ME): This approach uses Shannon entropy to calculate the expected information gain of a query, selecting the question that most effectively "splits" the hypothesis space regardless of the answer.
Experimental Evaluation
The SPRP was evaluated on two distinct domains:
- Simulated Domain: A synthetic dataset with 100 instances and a grammar featuring a branching factor of three, providing a controlled environment for logic testing.
- VirtualLabs: Real-world traces from a virtual chemistry laboratory. In this "messy" domain, just seven observations could result in over 32,000 hypotheses, serving as a rigorous stress test for real-time disambiguation.
Key Results and Insights
In the VirtualLabs domain, SPRP successfully collapsed a massive space of 11,759 hypotheses (at 7 observations) down to a single correct hypothesis. The Entropy-based approach (ME) was the clear winner, requiring significantly fewer queries to reach convergence compared to random selection or probability-based heuristics.
Technical analysis revealed several critical insights:
- The Matching Breakthrough: Plan recognition cannot be treated as standard classification. Because plans evolve, a "False" answer doesn't invalidate an entire hypothesis—only a specific path. Formal matching allows for pruning without losing the evolving truth.
- Entropy is King: Focusing on the most "informative" uncertainty rather than the most "probable" guess is more efficient for identification.
- Inherent Ambiguity: In simulated domains, even with infinite queries, the system could only narrow hypotheses to approximately 30% of the original set. This suggests some actions are truly ambiguous and cannot be resolved through querying alone.
Limitations and Future Directions
While effective, the current model does not fully account for the "annoyance factor" or the psychological cost of interrupting a human user. Future work may involve using Markov Decision Processes (MDPs) to plan query sequences that minimize total cost over time. Additionally, as domains scale, moving toward more compact, factored representations of the hypothesis space will be necessary to avoid memory bottlenecks.
Summary updated