Probabilistic Plan Recognition Using Off-the-Shelf Classical Planners

Miquel Ramírez, Hector GeffnerAAAI 2010 · DOI

Introduction: The Challenge of Plan Recognition

Plan recognition is essentially "planning in reverse": given a sequence of observed actions, the goal is to infer what an agent is trying to achieve. Traditionally, this task relied on rigid plan libraries—predefined sets of all possible action sequences an agent might follow. This approach is notoriously brittle; if an agent performs even a single action not explicitly contained in the library, the system fails.

Earlier generative approaches attempted to use planning algorithms to determine goal reachability but often assumed "perfectly rational" agents. Under such assumptions, a single suboptimal action (noise or error) would lead the model to incorrectly rule out the true goal. This paper introduces a flexible, probabilistic framework that leverages standard, "off-the-shelf" classical planners to handle suboptimal behavior without the need for handcrafted libraries.

A Probabilistic Framework via Cost Difference

The authors propose a framework to calculate the posterior probability $P(G|O)$—the likelihood of a goal $G$ given observations $O$. The core innovation lies in the Cost Difference ($\Delta$). For each potential goal, the system computes two values using a classical planner:

  1. $c(G, O)$: The cost of the cheapest plan to reach goal $G$ that satisfies the observations $O$.
  2. $c(G, \neg O)$: The cost of the cheapest plan to reach goal $G$ that avoids the observations $O$.

By comparing these costs, the system determines how well the observations explain the pursuit of a specific goal. If $c(G, O)$ is significantly lower than $c(G, \neg O)$, the goal $G$ is deemed highly probable. These differences are transformed into probabilities using a Boltzmann distribution, allowing the model to remain robust even when agents take suboptimal "detours."

To enable the use of standard PDDL-compliant planners (like HSP or LAMA), the authors employ a domain transformation*. They introduce "tracking" fluents that become true only when observed actions occur in the correct sequence, allowing any standard planner to solve the recognition task without internal code modifications.

Experimental Evaluation

The framework was tested across six diverse domains, including classical benchmarks (BLOCKS WORD, IPC-GRID, LOGISTICS) and activity recognition tasks (INTRUSION DETECTION, CAMPUS, KITCHEN).

Performance metrics across various planning domains and planners.

The results demonstrate that the approach scales effectively. For instance, in the BLOCKS WORD domain with 20 candidate goals, a greedy planner could solve the recognition task in approximately 53 seconds, maintaining high accuracy even with partial observations.

Key Results and Insights

A significant finding is the system's ability to identify the true goal with high confidence even when only a small fraction of the agent's actions have been observed. As shown in the probability distribution over time, the model's confidence in the correct goal typically increases and converges as more evidence is gathered.

Evolution of goal probabilities $P(G|O_t)$ over successive time steps, showing convergence toward the true goal.

Planner Trade-offs

The researchers compared three planners to highlight performance trade-offs:

  • HSP*: Provides optimal results but is computationally intensive.
  • LAMA: An anytime/satisficing planner that offers a 10-100x speedup with minimal impact on recognition quality.
  • Greedy LAMA: The fastest option, suitable for real-time applications where speed is prioritized over absolute optimality.

Conclusion

This work demonstrates that plan recognition can be effectively reduced to a series of standard planning problems. By moving away from fixed libraries and binary optimality checks, the system achieves a new level of robustness to noisy agent behavior. Future work aims to extend this framework to environments with partial observability and contingent planning, further bridging the gap between classical planning and real-world activity recognition.

Summary updated

BibTeX
@inproceedings{ramirez2010probabilistic,
  author = {Miquel Ramírez and Hector Geffner},
  title = {{Probabilistic Plan Recognition Using Off-the-Shelf Classical Planners}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7745},
}
Figure