.bib

@inproceedings { Banerjee2010,
	year = {2010},
	title = {Multi-Agent Plan Recognition: Formalization and Algorithms},
	pages = {1059--1064},
	keywords = {Processes,Technical Papers -- Reasoning about Plans,and Actions},
	file = {:home/acmt/Dropbox/Documentos/Mendeley/Proceedings of AAAI Conference on Artificial Intelligence/2010/Banerjee, Kraemer/Banerjee, Kraemer - 2010 - Multi-Agent Plan Recognition Formalization and Algorithms.pdf:pdf},
	booktitle = {Proceedings of AAAI Conference on Artificial Intelligence},
	address = {Atlanta, GA},
	abstract = {Multi-Agent Plan Recognition (MAPR) seeks to identify the dynamic team structures and team behaviors from the obser- vations 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 recog- nition by ”flattening” or decompressing the (usually com- pact, 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 al- though the compactness of the plan library plays an important role in the hardness of single-agent plan recognition (as rec- ognized 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 particu- larly suited for our model, and can be adapted to perform a branch and bound search for the second stage, in this model. We show empirically that this new approach leads to signifi- cant pruning of the hypothesis space in MAPR. Introduction},
	author = {Banerjee, , Bikramjit and Kraemer, , Landon}
}