Efficient Plan Recognition for Dynamic Multi-agent Teams

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

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


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.

author = {Gita Sukthankar and Katia Sycara},
title = {Efficient Plan Recognition for Dynamic Multi-agent Teams},
booktitle = {Proceedings of the Grace Hopper Conference},
year = {2007},
month = {October},
keywords = {multi-agent plan recognition},
} 2017-09-13T10:42:00-04:00