A Single-Agent Approach to Multiagent Planning

In this paper we present a novel approach to multiagent planning in domains with concurrent actions and associated concurrent action constraints. In these domains, we associate the actions of individual agents with subsets of objects, which allows for a transformation of the problems into single-agent planning problems that are considerably easier to solve. The transformation forces agents to select joint actions associated with a single subset of objects at a time, and ensures that the concurrency constraints on this subset are satisfied. Joint actions are serialised such that each agent performs their part of the action separately. The number of actions in the resulting single-agent planning problem turns out to be manageable in many real-world domains, thus allowing the problem to be solved efficiently using a standard single-agent planner. We also describe a cost-optimal algorithm for compressing the resulting plan, i.e. merging individual actions in order to reduce the total number of joint actions. Results show that our approach can handle large problems that are impossible to solve for most multiagent planners.