New Algorithms and Hardness Results For Multi-Agent Plan Recognition

Document Type

Conference Proceeding

Publication Date



Computing Sciences and Computer Engineering


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


Last Page