Policy Recognition in the Abstract Hidden Markov Model

Hung Hai Bui, Svetha Venkatesh, Geoff A. W. West

Introduction

Plan recognition—the ability to infer an agent’s high-level intentions from a sequence of noisy, low-level observations—is a fundamental challenge in artificial intelligence. Whether in video surveillance, human-computer interaction, or assistive robotics, systems must interpret ambiguous physical movements as coherent, goal-directed behaviors. This task is complicated by three primary factors: sensor noise, uncertainty in action outcomes, and the inherent hierarchical nature of human activity.

In this paper, the authors introduce the Abstract Hidden Markov Model (AHMM), a framework designed for online plan recognition. By leveraging a specialized Rao-Blackwellised Particle Filter, the AHMM provides a mathematically robust method for real-time inference that scales linearly with the complexity of the plan hierarchy, overcoming the computational bottlenecks that have historically plagued hierarchical models.

The Abstract Hidden Markov Model (AHMM)

The AHMM is a stochastic process built upon Abstract Markov Policies (AMPs). An AMP can be conceptualized as a "macro" action: a high-level policy (e.g., "Get Coffee") invokes a series of mid-level policies (e.g., "Go to Kitchen," "Operate Machine"), which eventually terminate in primitive actions (e.g., "Move Left").

The AHMM represents this execution hierarchy as a Dynamic Bayesian Network (DBN). In this structure, the state of the agent and the status of the policies at each level of the hierarchy are modeled as hidden variables. This allows the model to capture the "context-specific independence" of human behavior: while a specific sub-policy is active, its execution is independent of the higher-level goals that triggered it, until that sub-policy reaches a termination state.

Efficient Inference via Rao-Blackwellisation

Standard inference in complex DBNs is often computationally intractable because the state space grows exponentially with the depth of the hierarchy. To address this, the authors employ Rao-Blackwellised Sequential Importance Sampling (RB-SIS).

This "divide and conquer" strategy exploits the conditional independence properties of the AHMM:

  1. Sampling the "Hard" Variables: The algorithm uses a Particle Filter to sample the agent's physical state and the termination status of policies.
  2. Analytical Solution for the "Easy" Variables: Once the state and termination times are known, the distribution of high-level policies becomes a tractable chain that can be calculated exactly using analytical methods.

This hybrid approach ensures that the computational complexity scales linearly with the number of levels in the hierarchy. This efficiency is what enables the model to perform plan recognition in real-time, even as the depth of the behavioral model increases.

Experimental Evaluation

The AHMM was evaluated through both controlled simulations and real-world applications:

Synthetic Tracking Task

Using a simulated environment consisting of an eight-room building layout, the authors compared the RB-SIS algorithm against standard Sequential Importance Sampling (SIS). The synthetic setup allowed for precise measurement against a known "ground truth." The results demonstrated that the Rao-Blackwellised version was approximately eight times more efficient than standard SIS, achieving significantly lower error rates for the same computational budget.

Real-World Video Surveillance

The system was deployed in a complex indoor environment monitored by six distributed cameras. The data included typical real-world challenges, such as occlusions and jittery coordinate tracking. The AHMM successfully tracked human subjects, distinguishing between similar physical trajectories based on their likely high-level goals—for instance, differentiating between a person simply "passing through" a room and a person intending to "use a specific server" based on the duration and subtle nuances of their movement.

Key Insights and Results

  • Robustness to Noise: The AHMM acts as a powerful filter, maintaining a stable estimate of high-level intentions even when low-level sensor data is temporarily lost or highly inaccurate.
  • Tractability of Hierarchies: The research proves that adding layers of abstraction does not necessarily lead to an exponential increase in inference difficulty, provided the model structure is exploited correctly.
  • Real-Time Performance: The system demonstrated the ability to process complex behavioral data in real-time using standard hardware (two 1GHz machines), making it viable for practical security and monitoring applications.

Limitations and Future Directions

While the AHMM represents a significant step forward, the authors identify several areas for future research. The current model assumes an agent pursues a single top-level goal; it does not yet account for interleaved or concurrent plans, such as a person checking their phone while walking to a destination. Additionally, the policy parameters in these experiments were hand-coded. Future work will focus on learning these parameters directly from observation databases and exploring more expressive languages for representing recursive or non-Markovian plan structures.

Summary updated

Abstract

In this paper, we present a method for recognising an agent's behaviour in dynamic, noisy, uncertain domains, and across multiple levels of abstraction. We term this problem on-line plan recognition under uncertainty and view it generally as probabilistic inference on the stochastic process representing the execution of the agent's plan. Our contributions in this paper are twofold. In terms of probabilistic inference, we introduce the Abstract Hidden Markov Model (AHMM), a novel type of stochastic processes, provide its dynamic Bayesian network (DBN) structure and analyse the properties of this network. We then describe an application of the Rao-Blackwellised Particle Filter to the AHMM which allows us to construct an efficient, hybrid inference method for this model. In terms of plan recognition, we propose a novel plan recognition framework based on the AHMM as the plan execution model. The Rao-Blackwellised hybrid inference for AHMM can take advantage of the independence properties inherent in a model of plan execution, leading to an algorithm for online probabilistic plan recognition that scales well with the number of levels in the plan hierarchy. This illustrates that while stochastic models for plan execution can be complex, they exhibit special structures which, if exploited, can lead to efficient plan recognition algorithms. We demonstrate the usefulness of the AHMM framework via a behaviour recognition system in a complex spatial environment using distributed video surveillance data.
BibTeX
@article{bui2002policy,
  author = {Hung Hai Bui and Svetha Venkatesh and Geoff A. W. West},
  title = {{Policy Recognition in the Abstract Hidden Markov Model}},
  journal = {J. Artif. Intell. Res.},
  year = {2002},
  doi = {10.1613/jair.839},
}
Figure