Efficient Plan Recognition for Dynamic Multi-agent Teams

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.