Multi-Agent Plan Recognition: Formalization and Algorithms

Document Type

Conference Proceeding

Publication Date

7-11-2010

School

Computing Sciences and Computer Engineering

Abstract

Multi-Agent Plan Recognition (MAPR) seeks to identify the dynamic team structures and team behaviors from the observations of the activity-sequences of a set of intelligent agents, based on a library of known team-activities (plan library). It has important applications in analyzing data from automated monitoring, surveillance, and intelligence analysis in general. In this paper, we formalize MAPR using a basic model that explicates the cost of abduction in single agent plan recognition by "flattening" or decompressing the (usually compact, hierarchical) plan library. We show that single-agent plan recognition with a decompressed library can be solved in time polynomial in the input size, while it is known that with a compressed (by partial ordering constraints) library it is NP-complete. This leads to an important insight: that although the compactness of the plan library plays an important role in the hardness of single-agent plan recognition (as recognized in the existing literature), that is not the case with multiple agents. We show, for the first time, that MAPR is NP-complete even when the (multi-agent) plan library is fully decompressed. As with previous solution approaches, we break the problem into two stages: hypothesis generation and hypothesis search. We show that Knuth's "Algorithm X" (with the efficient "dancing links" representation) is particularly suited for our model, and can be adapted to perform a branch and bound serarch for the second stage, in this model. We show empirically that this new approach leads to significant pruning of the hypothesis space in MAPR.

Publication Title

Proceedings of the Twenty-Fourth AAAI Conference On Artificial Intelligence

First Page

1059

Last Page

1064

Link to Full Text

Share

COinS