Branch and Price for Multi-Agent Plan Recognition


  • Bikramjit Banerjee The University of Southern Mississippi
  • Landon Kraemer The University of Southern Mississippi


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 accommodate 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.




How to Cite

Banerjee, B., & Kraemer, L. (2011). Branch and Price for Multi-Agent Plan Recognition. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 601-607. Retrieved from



AAAI Technical Track: Multiagent Systems