Branch and Price For Multi-Agent Plan Recognition
Document Type
Conference Proceeding
Publication Date
8-1-2011
School
Computing Sciences and Computer Engineering
Abstract
The problem of identifying the (dynamic) team structures and team behaviors from the observed activities of multiple agents is called Multi-Agent Plan Recognition (MAPR). We extend a recent formalization of this problem to accomodate a compact, partially ordered, multi-agent plan language, as well as complex plan execution models--particularly plan abandonment and activity interleaving. We adopt a branch and price approach to solve MAPR in such a challenging setting, and fully instantiate the (generic) pricing problem for MAPR. We show experimentally that this approach outperforms a recently proposed hypothesis pruning algorithm in two domains: multi-agent blocks word, and intrusion detection. The key benefit of the branch and price approach is its ability to grow the necessary component (occurrence) space from which the hypotheses are constructed, rather than begin with a fully enumerated component space that has an intractable size, and search it with pruning. Our formulation of MAPR has the broad objective of bringing mature Operations Research methodologies to bear upon MAPR, envisaged to have a similar impact as mature SAT-solvers had on planning.
Publication Title
Proceedings of the Twenty-Fifth AAAI Conference On Artificial Intelligence
First Page
601
Last Page
607
Recommended Citation
Banerjee, B.,
Kraemer, L.
(2011). Branch and Price For Multi-Agent Plan Recognition. Proceedings of the Twenty-Fifth AAAI Conference On Artificial Intelligence, 601-607.
Available at: https://aquila.usm.edu/fac_pubs/20622
COinS