Efficient Plan Recognition for Dynamic Multi-agent Teams

Gita Sukthankar and Katia Sycara
Proceedings of the Grace Hopper Conference, October, 2007.


Abstract
This paper addresses the problem of plan recognition for multi-agent teams. Complex multi-agent tasks typically require dynamic teams where the team membership changes over time. Teams split into subteams to work in parallel, merge with other teams to tackle more demanding tasks, and disband when plans are completed. We introduce a new multi-agent plan representation that explicitly encodes dynamic team membership and demonstrate the suitability of this formalism for plan recognition. From our multi-agent plan representation, we extract local temporal dependencies that dramatically prune the hypothesis set of potentially-valid team plans. The reduced plan library can be efficiently processed using existing tree search techniques to obtain the team state history. Although multi-agent plan recognition is theoretically more computationally expensive than single-agent plan recognition, we show that, in practice, the presence of agent resource dependencies significantly reduces the set of potentially-valid plans.

Keywords
multi-agent plan recognition

Notes
Sponsor: ARL
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Advanced Agent - Robotics Technology Lab
Associated Project(s): IBM ITA: Human-Agent Teamwork Models

Text Reference
Gita Sukthankar and Katia Sycara, "Efficient Plan Recognition for Dynamic Multi-agent Teams," Proceedings of the Grace Hopper Conference, October, 2007.

BibTeX Reference
@inproceedings{Sukthankar_2007_5812,
   author = "Gita Sukthankar and Katia Sycara",
   title = "Efficient Plan Recognition for Dynamic Multi-agent Teams",
   booktitle = "Proceedings of the Grace Hopper Conference",
   month = "October",
   year = "2007",
}