Generalized Plan Recognition

Henry A. Kautz, James F. AllenAAAI 1986

Introduction

In their seminal 1986 paper, Henry Kautz and James Allen introduced a formal theory that shifted plan recognition from heuristic-based "best guesses" to a rigorous framework of deductive logic. By treating the problem as one of logical inference rather than search, they addressed fundamental challenges in understanding agent behavior under uncertainty.

The Problem: Uncertainty in Plan Recognition

In the mid-1980s, AI systems struggled to infer an agent's goals from observed actions. For instance, seeing someone pick up car keys could imply they are going to the store, moving the car, or simply putting the keys away. Previous methods, such as action grammars or "likely inference" rules, were often brittle or lacked a formal basis for their conclusions. The core challenge was maintaining a set of possible explanations without prematurely committing to a single hypothesis.

Methods: A Formal Logical Framework

Kautz and Allen proposed a framework grounded in First-Order Logic and the technique of circumscription.

Action Taxonomy

Knowledge is represented as a hierarchy with two primary link types:

  • Specialization (ISA): For example, "MakeFettuccini" is a specialized form of "MakePastaDish."
  • Decomposition (Substeps): Actions like "Boil" are mandatory components of "MakePastaDish."
Figure 1: The action hierarchy illustrating specialization and decomposition links.

Closing the World through Circumscription

The authors used circumscription to formally assert that the known ways of performing an action are exhaustive and that every observed action must serve a higher-level purpose (unless it is a top-level goal). This "closed-world" assumption allows the system to make definitive deductions.

Deductive Inference and Decomposition

Instead of selecting the most probable plan, the system deduces a disjunction (an "OR" statement) of all possible plans consistent with the observations. This allows the system to retain multiple hypotheses until further evidence arrives.

Figure 2: A formal decomposition axiom for the action 'MakePastaDish'.

Simplicity Constraints

To manage ambiguity, the system applies a version of Occam’s Razor, assuming the agent is pursuing the minimum number of independent top-level goals necessary to explain the observations.

Evaluation and Insights

The paper utilizes a constructed "cooking world" domain—preparing various pasta and meat dishes—to demonstrate the logic's capabilities. Key insights include:

  • Recognition as Deduction: Framing plan recognition as ordinary deductive inference provides a solid mathematical foundation.
  • Handling Disjunction: The system can make useful predictions even when uncertain. If it knows an agent is making either Spaghetti or Fettuccini, it can predict the need to "Boil Water."
  • Shared Substeps: The model correctly attributes a single action to multiple independent plans if necessary.
  • Non-Monotonic Reasoning: The simplicity assumption allows the system to revise its conclusions as new observations arrive.

The system successfully handles scenarios that challenged earlier models, such as disjunctive observations (inferring common abstractions from "either/or" scenarios) and temporal flexibility (processing observations that arrive out of order). Through goal minimization, it can merge separate observations—like "Boiling Water" and "Making Sauce"—into a single "Making Pasta" plan.

Limitations

Despite its formal strengths, the system is limited by its reliance on a pre-defined "plan library"; it cannot learn new plans. Additionally, first-order logic and circumscription are computationally expensive, posing challenges for real-time implementation. Finally, the model treats all logically possible plans as equally likely, lacking a probabilistic component to weight more frequent behaviors.

Summary updated

BibTeX
@inproceedings{kautz1986generalized,
  author = {Henry A. Kautz and James F. Allen},
  title = {{Generalized Plan Recognition}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure