Abstract
Plan recognition—the task of inferring user goals from observed actions—is often hindered by a "state space explosion" in complex, real-world environments. This paper introduces an architecture that combines application-specific heuristics with a Truth Maintenance System (TMS) to manage this complexity. By formalizing heuristic guesses as retractable assumptions, the system maintains focus on the most likely interpretations while allowing for efficient, non-monotonic backtracking when new evidence contradicts current hypotheses.
Introduction
Plan recognition is a fundamental challenge for intelligent user interfaces, but it is complicated by concurrency, ambiguity, and partial information. In large systems, the number of mathematically possible interpretations grows exponentially, making it impossible to track every valid permutation.
Traditional approaches often struggle to balance efficiency with accuracy. The authors address this gap by proposing a system that "focuses" attention on the most plausible plans without permanently discarding alternatives. This allows the system to remain flexible and intelligent in the face of evolving user behavior.
System Architecture
The proposed architecture is integrated into the POISE intelligent user interface system. It utilizes a blackboard-based control structure to manage and prioritize plan hypotheses.
As illustrated in the architecture diagram, the system features several key components:
- Dual Blackboards: An Instantiation Blackboard for recording actual events and a Prediction Blackboard for simulating potential future actions.
- Heuristic Focus-of-Control: This mechanism uses application-specific, plan-specific, and user-goal heuristics to rank interpretations.
- Reason Maintenance System (RMS): The RMS tracks the justifications for every plan instantiation. When the system makes a heuristic guess, it records it as a formal assumption, enabling robust reasoning.
Heuristics and Intelligent Backtracking
The core innovation of this approach is the treatment of heuristics as retractable assumptions within a formal logic system. This transforms a simple "best-guess" algorithm into a robust reasoning engine.
When a later action invalidates a current assumption, the system performs dependency-directed backtracking. Unlike traditional chronological backtracking, which reverses steps one by one, this method uses the TMS to jump directly to the faulty assumption. The system then "undoes" only the relevant work, preserving unrelated inferences and significantly improving computational efficiency.
Evaluation and Plan Traces
The architecture was evaluated using office automation scenarios, such as a "Complete-Purchase" plan involving steps like checking goods and requesting information.
Detailed traces, such as the one shown above, illustrate how the system incrementally builds plan structures from user actions. This hierarchical approach allows the system to distinguish between "system errors" (incorrect internal guesses) and "user errors" (actions that do not fit any known plan), providing a basis for more helpful user feedback.
Conclusion
The POISE architecture demonstrates that a TMS-based approach to plan recognition is both computationally feasible and effective for real-time assistance. By focusing on likely paths while maintaining the ability to recover discarded ones, the system avoids the pitfalls of premature pruning. Future work will explore more sophisticated, quality-based retraction systems and the integration of semantic domain knowledge to further refine heuristic accuracy.
Summary updated