New Algorithms and Hardness Results For Multi-Agent Plan Recognition
Document Type
Conference Proceeding
Publication Date
6-11-2011
School
Computing Sciences and Computer Engineering
Abstract
We extend our recent formalization of multi-agnet plan recognition (MAPR), to accomodate compact multi-agent plan libraries and incomplete plans, and propose polynomial time algorithms for several cases of static teams: when team-size is bounded by 2, or when the social structure graph is a star, a tree of bounded depth, or a apth. However, we show that when the teams are dynamic and even when the social structure graph is as simple as a path, MAPR is NP-complete. Finally, we show rigorously for the first time, that when activity interleaving is allowed, even the single agent version of MAPR is NP-complete.
Publication Title
Proceedings of the 1st ICAPS Workshop On Goal, Activity, and Plan Recognition
First Page
24
Last Page
31
Recommended Citation
Banerjee, B.,
Lyle, J.,
Kraemer, L.
(2011). New Algorithms and Hardness Results For Multi-Agent Plan Recognition. Proceedings of the 1st ICAPS Workshop On Goal, Activity, and Plan Recognition, 24-31.
Available at: https://aquila.usm.edu/fac_pubs/20621
COinS