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:
- Sampling the "Hard" Variables: The algorithm uses a Particle Filter to sample the agent's physical state and the termination status of policies.
- 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