Multi-Agent Plan Recognition: Formalization and Algorithms

Bikramjit Banerjee, Landon Kraemer, Jeremy LyleAAAI 2010 · DOI

Abstract

Multi-Agent Plan Recognition (MAPR) involves inferring the goals and plans of a group of agents from observed actions. This work provides a formal complexity analysis proving that MAPR is fundamentally more difficult than single-agent recognition. While single-agent systems can be simplified by "flattening" hierarchical plan libraries, MAPR remains NP-complete even in its simplest form. We formalize MAPR as a matrix-covering problem and introduce a branch-and-bound algorithm based on Knuth’s "Algorithm X" to identify optimal plan explanations efficiently.

Introduction

Plan recognition is the "inverse" of planning: given a sequence of observed actions, the goal is to determine what the agent is trying to achieve. Multi-Agent Plan Recognition (MAPR) increases this complexity by observing groups of agents who may coordinate in shifting teams or act independently.

A core challenge in this field is identifying the source of computational complexity. In single-agent systems, difficulty often stems from the structure of the plan library (e.g., complex hierarchies). It was previously hypothesized that if these hierarchies were "flattened" into simple lists of action sequences, the problem would become computationally easy.

Hierarchical Task Network (HTN) plans can be flattened into a symbolic plan library of action sequences.

However, this paper demonstrates that for multiple agents, the hardness is inherent to the coordination itself, not just the library structure.

Formalization and Complexity

The authors formalize MAPR as a matrix-covering problem. Observations are represented as a grid where rows correspond to time steps and columns to agents. The goal is to cover every cell in this grid using "stamps" (sub-matrices) from a plan library, such that each action is explained by exactly one plan.

MAPR formalized as covering activity traces (left) with templates from a team-plan library (right).

Using a reduction from the Exact Cover problem, the authors prove that MAPR is NP-complete even when the plan library is fully "decompressed" or flat. This reveals that the combinatorial explosion of possible team assignments is a fundamental source of NP-completeness in multi-agent environments.

Algorithmic Approach

To solve the MAPR problem, the authors map instances to a massive Boolean matrix and apply Donald Knuth’s Algorithm X. They utilize the Dancing Links (DLX) data structure, which allows for extremely fast row/column removal and backtracking during search.

Because the goal is often to find the maximum utility explanation rather than just any valid cover, the authors adapted Algorithm X into a branch-and-bound search. They implemented a BestPossible heuristic that estimates the maximum remaining utility in a branch; if that estimate is lower than the best solution found so far, the algorithm prunes that entire branch of the search tree.

Experimental Evaluation

The approach was evaluated using 2,400 synthetic instances featuring 20 agents over 100 time steps. The primary metric was "updates"—a count of how many times objects are removed or reinstated in the DLX data structure—to compare the work done with and without pruning.

Key Results

  • Theoretical Hardness: MAPR is proven NP-complete even if all plans involve only 3 agents and no single action sequence appears in more than 3 plans.
  • Pruning Efficiency: The branch-and-bound algorithm showed significant performance gains. In complex instances, the "work-ratio" (pruned work vs. unpruned work) dropped to nearly 0.2, meaning the algorithm only performed 20% of the work required by a standard exhaustive search to find the optimal solution.

Conclusion and Future Work

This research establishes that multi-agent coordination is a fundamental source of computational hardness in plan recognition. By framing MAPR as an Exact Cover problem, the authors leverage optimized combinatorial search techniques to find optimal solutions. Future work will focus on relaxing the strict model constraints to account for noise (unexplained actions), goal abandonment, and interleaved plans where agents work on multiple goals simultaneously.

Summary updated

BibTeX
@inproceedings{banerjee2010multi,
  author = {Bikramjit Banerjee and Landon Kraemer and Jeremy Lyle},
  title = {{Multi-Agent Plan Recognition: Formalization and Algorithms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7746},
}
Figure