EgoPlan: A Framework for Multi-Agent Planning Using Single Agent Planners

Abstract

Planning problems are, in general, PSPACE-complete; large problems, especially multi-agent problems with required co-ordination, can be intractable or impractical to solve. Factored planning and multi-agent planning both address this by separating multi-agent problems into tractable sub-problems, but there are limitations in the expressivity of existing planners and in the ability to handle tightly coupled multi-agent problems. This paper presents EGOPLAN, a framework which factors a multi-agent problem into related sub-problems which are solved by iteratively calling on a single agent planner. EGOPLAN is evaluated on a multi-robot test domain with durative actions, required coordination, and temporal constraints, comparing the performance of a temporal planner, OPTIC-CPLEX, with and without EGOPLAN. Our results show that for our test domain, using EGOPLAN allows OPTIC-CPLEX to solve problems that are twice as complex as it can solve without EGOPLAN, and to solve  complex problems significantly faster.