Abstract
This paper addresses the problem of plan recognition for multi-agent teams. Complex multi-agent tasks typically require dynamic teams where the team membership changes over time. Teams split into subteams to work in parallel, merge with other teams to tackle more demanding tasks, and disband when plans are completed. We introduce a new multi-agent plan representation that explicitly encodes dynamic team membership and demonstrate the suitability of this formalism for plan recognition. From our multi-agent plan representation, we extract local temporal dependencies that dramatically prune the hypothesis set of potentially-valid team plans. The reduced plan library can be efficiently processed to obtain the team state history. Naive pruning can be inadvisable when low-level observations are unreliable due to sensor noise and classification errors. In such conditions, we eschew pruning in favor of prioritization and show how our scheme can be extended to rank-order the hypotheses. Experiments show that this robust pre-processing approach ranks the correct plan within the top 10%, even under conditions of severe noise.
Introduction
Plan recognition—the ability to infer an agent's goals and future actions from observed behavior—is a fundamental challenge in AI, often described as "mind-reading" for systems. In multi-agent environments, this task becomes exponentially more difficult. Real-world teams are dynamic: they split to handle parallel sub-tasks, recruit new members for demanding goals, and merge to consolidate resources. This paper introduces a novel representation and indexing scheme to tackle the combinatorial explosion and sensor noise inherent in large-scale multi-agent plan recognition.
Multi-agent Plan Representation
To capture the nuances of dynamic team membership, the researchers extend standard Hierarchical Task Networks (HTNs) by adding specialized nodes that account for team size and resource requirements. Two key additions are:
- SPLIT: Explicitly marks where a team divides into sub-teams to handle parallel sub-plans.
- RECRUIT: Indicates where a team must wait for additional agents to join before proceeding.
This representation allows the plan library to encode not just the sequence of actions, but the specific resource requirements (agent counts) necessary for each stage of execution. By treating agent counts as a hard constraint, the system can immediately deprioritize plans that require more agents than are currently observed.
Temporal Fingerprinting via Hashing
The core innovation lies in pre-compiling the plan library into "temporal fingerprints" stored in hash tables. This avoids the need to exhaustively check every plan against every observation during runtime. The system utilizes two primary hashes:
- Within-trace Hash ($g$): Maps pairs of consecutive observations to the plans that permit them (e.g., "If I see 'Advance' then 'Attack', which plans contain that sequence?").
- Across-trace Hash ($h$): Maps observations seen just before a team split to the potential sub-plans initiated by the resulting sub-teams.
Robustness to Noise: Pruning vs. Ranking
In ideal, "clean" environments, these hashes allow for aggressive pruning, instantly discarding any plan hypothesis that contradicts the observed temporal sequence. However, real-world sensors are imperfect. To handle this, the authors propose a ranking (prioritization) scheme. Instead of deleting plans, the system "scores" them based on how well they match the observed transitions. Every time an observation matches a transition allowed by a plan, that plan's score increases. This ensures that even if a few observations are misclassified, the correct plan remains highly ranked and visible to the recognizer.
Experimental Results and Scalability
The system was evaluated in a simulated military domain involving up to 100 agents and 40 simultaneously executing plans. The results demonstrate exceptional efficiency; for a 100-agent scenario, the wall-clock execution time was only 0.14 seconds on 2008-era hardware.
As shown in the performance data, while naive "unpruned" recognition costs grow linearly with the size of the plan library, the "Team+Temporal" pruning method maintains a nearly constant computational cost. Furthermore, the system proved robust to noise; even with 50% observation noise, the prioritization scheme consistently ranked the correct plan within the top 10% of all hypotheses.
Conclusion
By leveraging resource constraints and pre-computed temporal dependencies, this approach enables near real-time plan recognition in complex, multi-agent scenarios. While the current method assumes team assignments can be determined (e.g., via spatial clustering), it provides a powerful framework for filtering the combinatorial explosion of plan hypotheses in dynamic environments.
Summary updated