caa a22 4500 605514615 CHVBK 20210128100705.0 cr unu---uuuuu 210128e20150101xx s 000 0 eng 10.1007/s10458-014-9248-2 doi (NATIONALLICENCE)springer-10.1007/s10458-014-9248-2 The complexity of multi-agent plan recognition [Elektronische Daten] [Bikramjit Banerjee, Jeremy Lyle, Landon Kraemer] Multi-agent plan recognition (MAPR) seeks to identify the dynamic team structures and team plans from observations of the action sequences of a set of intelligent agents, based on a library of known team plans (plan library), and an evaluation function. It has important applications in decision support, team work, analyzing data from automated monitoring, surveillance, and intelligence analysis in general. We introduce a general model for MAPR that accommodates different representations of the plan library, and includes single agent plan recognition as a special case. Thus it provides an ideal substrate to investigate and contrast the complexities of single and multi-agent plan recognition. Using this model we generate theoretical insights on hardness, with practical implications. A key feature of these results is that they are baseline, i.e., the polynomial solvability results are given in terms of a compact and expressive plan language (context free language), while the hardness results are given in terms of a less compact language. Consequently the hardness results continue to hold in virtually all realistic plan languages, while the polynomial solvability results extend to the subsets of the context free plan language. In particular, we show that MAPR is in P (polynomial in the size of the plan library and the observation trace) if the number of agents is fixed (in particular 1) but NP-complete otherwise. If the number of agents is a variable, then even the one step MAPR problem is NP-complete. While these results pertain to abduction, we also investigate a related question: adaptation, i.e., the problem of refining the evaluation function based on feedback. We show that adaptation is also NP-hard for a variable number of agents, but easy for a single agent. These results establish a clear distinction between the hardnesses of single and multi-agent plan recognition even in idealized settings, indicating the necessity of a fundamentally different set of techniques for the latter. The Author(s), 2014 Plan recognition nationallicence Multi-agent plan recognition nationallicence Abductive reasoning nationallicence Computational complexity nationallicence Banerjee Bikramjit University of Southern Mississippi, 118 College Dr. #5106, 39406, Hattiesburg, MS, USA aut Lyle Jeremy University of Southern Mississippi, 118 College Dr. #5106, 39406, Hattiesburg, MS, USA aut Kraemer Landon University of Southern Mississippi, 118 College Dr. #5106, 39406, Hattiesburg, MS, USA aut Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/1(2015-01-01), 40-72 1387-2532 29:1<40 2015 29 10458 https://doi.org/10.1007/s10458-014-9248-2 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10458-014-9248-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Banerjee Bikramjit University of Southern Mississippi, 118 College Dr. #5106, 39406, Hattiesburg, MS, USA aut NATIONALLICENCE 700 1- Lyle Jeremy University of Southern Mississippi, 118 College Dr. #5106, 39406, Hattiesburg, MS, USA aut NATIONALLICENCE 700 1- Kraemer Landon University of Southern Mississippi, 118 College Dr. #5106, 39406, Hattiesburg, MS, USA aut NATIONALLICENCE 773 0- Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/1(2015-01-01), 40-72 1387-2532 29:1<40 2015 29 10458