Efficient Context Free Parsing of Multi-Agent Activities For Team and Plan Recognition
Document Type
Conference Proceeding
Publication Date
6-4-2012
School
Computing Sciences and Computer Engineering
Abstract
We extend a recent formalization of multi-agent plan recognition (MAPR), to accommodate compact multi-agent plan libraries inthe form of context free grammars (CFG), incomplete plan recognition cast it as a problem of parsing a single agent activity trace. With the help of our multi-agent CFG, we do the same for MAPR. However, known hardness results from multi-agent plan recognition constrain our options for efficient parsing, but we claim that static teams are a necessary (though not sufficient) condition for polynomial parsing. The necessity is supported by the fact that MAPR becomes NP-complete when teams can change dynamically. For sufficiency, we impose additional restrictions and claim that if the social structure among the agents is of certain types, then polynomial time parsing is possible.
Publication Title
Proceedings of the 11th International Conference On Autonomous Agents and Multiagent Systems
Recommended Citation
Banerjee, B.,
Lyle, J.,
Kraemer, L.
(2012). Efficient Context Free Parsing of Multi-Agent Activities For Team and Plan Recognition. Proceedings of the 11th International Conference On Autonomous Agents and Multiagent Systems.
Available at: https://aquila.usm.edu/fac_pubs/20618
COinS