Automated Agent Decomposition for Classical Planning

Many real-world planning domains, including those used in common benchmark problems, are based on multiagent scenarios. It has long been recognised that breaking down such problems into sub-problems for individual agents may help reduce overall planning complexity. This kind of approach is especially effective in domains where interaction between agents is limited. In this paper we present a fully centralised, offline, sequential, total-order planning algorithm for solving classical planning problems based on this idea. This algorithm consists of an automated decomposition process and a heuristic search method designed specifically for decomposed domains. The decomposition method is part of a preprocessing step and can be used to determine the 'multiagent nature' of a planning problem prior to actual plan search. The heuristic search strategy is shown to effectively exploit any decompositions that are found and performs significantly better than current approaches on loosely coupled domains.