A Probabilistic Model of Plan Recognition

Eugene Charniak, Robert P. GoldmanAAAI 1991

Abstract

Inferring an agent's goals from observed actions is a fundamental challenge in artificial intelligence. This paper introduces a formal probabilistic model for plan recognition that utilizes Bayesian networks to evaluate competing hypotheses. By incorporating prior probabilities and evidence-based updates, the proposed system, Wimp3, overcomes the limitations of traditional logic-based approaches that rely on "minimal set" explanations.

Introduction

Plan recognition involves determining the underlying intent behind a sequence of actions. Historically, this was treated as a problem of nonmonotonic logic or "minimal set covering," where the best explanation was the one that minimized the number of "top-level" plans. However, logic alone often fails to distinguish between common and rare events that share identical action sequences. For example, a person going to an airport could be a traveler or a terrorist; a purely logical system cannot decide between these because both plans explain the actions.

The authors argue that humans resolve these ambiguities using "priors"—the knowledge that certain events are vastly more common than others. This paper addresses the need for a model that incorporates uncertainty and prior knowledge to resolve such ambiguities through a probabilistic framework.

System Architecture and Methods

The authors introduce Wimp3, a system designed to translate English narratives into a probabilistic framework for plan recognition. The system follows a structured pipeline to move from raw text to an evaluated plan hypothesis.

The Wimp3 System Architecture

The process involves several key components:

  1. Knowledge Representation: Facts are stored in a first-order language using predicates like inst (instance of a type) and isa (subset relation).
  2. Network Construction: Forward-chaining rules automatically build a Bayesian network from input observations and the knowledge base.
  3. Existential Slot-Filling: The model uses "up-existential" and "down-existential" arcs to represent the probability that a specific action (e.g., going to a store) fills a slot in a higher-level plan (e.g., shopping).
  4. Noisy-OR Gates: To manage competition between multiple plans explaining the same evidence, the model employs a "noisy-OR" distribution.
  5. Marker Passing: A heuristic marker-passing algorithm suggests potential plan hypotheses to keep computational costs manageable before full network evaluation.

Probabilistic Competition and Evidence

A core insight of this model is that different plans compete for the same evidence. In a Bayesian network, two distinct plans—such as "Shopping" and "Robbing"—can both serve as explanations for an action like entering a liquor store.

Bayesian Network for Competing Plans

As shown in the network above, the arrival of new evidence significantly shifts the posterior probabilities. While "going to the store" (go1) might initially support both liquor store shopping (lss3) and robbery (rob4), the subsequent observation of "pointing a gun" (point5, gun6) provides strong evidence for the robbery hypothesis, allowing the system to "change its mind" based on the updated probabilistic weights.

Evaluation and Results

The model was evaluated using a custom set of 25 short narrative stories in a single-blind test. The system's task was to correctly pair stories that shared the same underlying plans.

  • Initial Performance: The system correctly paired 19 out of 25 stories.
  • Refined Performance: After minor adjustments to the knowledge base to fix gaps discovered during debugging, the accuracy improved to 24 out of 25 stories.

The single failure case occurred because the generated Bayesian network became too large to evaluate, highlighting the primary bottleneck of this approach: computational complexity.

Conclusion

This work demonstrates that a probabilistic approach to plan recognition is superior to purely logical models by allowing for the integration of prior probabilities and competing evidence. However, significant challenges remain. Evaluating Bayesian networks is NP-hard, making them potentially intractable for long, complex stories. Furthermore, the reliance on a manually constructed knowledge base presents a hurdle for scaling the system to handle broad "common sense" knowledge. Future work aims to incorporate "down-existentials" to better handle scenarios where plans suggest specific sub-parts.

Summary updated

BibTeX
@inproceedings{charniak1991probabilistic,
  author = {Eugene Charniak and Robert P. Goldman},
  title = {{A Probabilistic Model of Plan Recognition}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure