A New Model of Plan Recognition

Robert P. Goldman, Christopher W. Geib, Christopher A. MillerUAI 1999

TL;DR

This paper introduces a novel, abductive, and probabilistic model for plan recognition that centers on the execution of plans rather than just their static representation. This new perspective allows for more robust recognition of complex behaviors like interleaved and partially-ordered plans, contextual influences on action choice, and even the impact of interventions, making it more suitable for intelligent assistant systems.

What Problem Does This Paper Address?

Plan recognition, the task of inferring an agent's goals from their observed actions, is crucial for building intelligent systems that can assist humans. Previous approaches, notably Kautz and Allen's (1986) influential work, often treated plans as formal objects or relied on rule-based systems. While effective for simpler scenarios, these methods struggled with:

  • Partially-ordered and interleaved plans: Real-world actions often don't follow strict linear sequences, and agents can pursue multiple goals concurrently.
  • Contextual influences: The environment and situation significantly impact an agent's choices, a factor often overlooked.
  • Negative evidence: The absence of an expected action can be informative, but older models couldn't effectively use this "failure to observe."
  • Interacting agents: Systems that need to recognize plans while also potentially intervening or acting on behalf of the observed agent were not well-supported.

This paper aims to bridge these gaps by proposing a more dynamic and comprehensive model of plan recognition.

Methods

The core of the paper's contribution lies in its abductive, probabilistic theory of plan recognition that is centered around a model of plan execution. Instead of focusing on plan graphs as formal objects, the authors model how plans are executed.

Key methodological aspects include:

  • Probabilistic Abduction: The model uses probabilistic reasoning to find the "best explanation" for observed actions, assigning probabilities to hypotheses about an agent's intentions. This is framed within the Probabilistic Horn Abduction (PHA) framework.
  • Plan Execution Model: A simple, hierarchical model of plan execution is proposed. An agent selects a set of plans, and then repeatedly executes pending actions. Actions become "enabled" either because they are performed "for their own sake" or as part of a parent plan whose prerequisites are met.
  • Handling Complex Plan Structures: The model explicitly accounts for:
  • Partially-ordered plans: Actions within a method can have flexible ordering.
  • Interleaved plans: Multiple plans can be executed concurrently.
  • Overloaded actions: Actions that contribute to multiple plans are naturally handled.
  • Contextual Influence: The model incorporates the idea that the probability of adopting a plan can be conditional on environmental factors (e.g., an EVA preparation might increase the likelihood of intending to increase power).
  • Interventions: The framework is extended to handle situations where the recognizing system might intervene in the observed agent's plan execution, drawing on Pearl's theory of causal interventions.

Datasets

Not discussed in the paper. The paper focuses on a formal model and uses hypothetical examples derived from a sample "space station plan library" to illustrate its concepts.

Key Insights and Ideas

  • Plan Execution as Primary: Shifting the focus from static plan representations to the dynamic process of plan execution is key to solving many long-standing problems in plan recognition.
  • The "Pending Set" is Crucial: The concept of a "pending set" of actions elegantly handles partially-ordered and interleaved plans, as well as the progression of execution over time.
  • Negative Evidence is Informative: The model's ability to track enabled actions and observe their absence over time allows it to infer that certain plans are not being pursued, refining beliefs about the agent's true intentions.
  • Context Matters for Intent: Environmental factors and situational cues can significantly alter the a priori likelihood of an agent pursuing certain goals, and the model can incorporate this.
  • Interventions are Manageable: By integrating concepts from causal inference, the model can reason about situations where the recognizing system actively participates or influences the observed agent's actions.

Key Results

The paper presents a formal model and demonstrates its capabilities through several worked examples, rather than reporting quantitative results on specific datasets. The key "results" are qualitative:

  • The model successfully explains phenomena that were difficult for previous theories, such as the cumulative effect of interleaved, partially-ordered plans and the influence of context on plan adoption.
  • It provides a framework for systems that can recognize plans and potentially assist users by intervening or acting on their behalf.
  • The paper shows how the model can handle "negative evidence" (failure to observe expected actions) to refine beliefs about an agent's goals over time.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Lack of World State Representation: The current model does not explicitly represent the state of the world, meaning actions and interventions don't change the environment. Future work aims to incorporate this for a more realistic model.
  • Agent Interaction: While interventions are handled, the model doesn't fully capture complex multi-agent interaction where agents dynamically influence each other's world states.
  • Computational Complexity: The paper focuses on the "knowledge level" and mentions a proof-of-concept interpreter, but does not claim it provides an efficient solution. Exploring efficient algorithms for plan recognition within this framework is an open area.
  • Single Method Choice Assumption: The model currently assumes an agent chooses only one method for a given goal. Relaxing this would lead to a more complex but potentially more general model.

Summary updated

BibTeX
@inproceedings{goldman1999new,
  author = {Robert P. Goldman and Christopher W. Geib and Christopher A. Miller},
  title = {{A New Model of Plan Recognition}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1999},
}
Figure