Factored Planning: How, When, and When Not

Abstract

Automated domain factoring, and planning methods that uti-lize them, have long been of interest to planning researchers. Recent work in this area yielded new theoretical insight and algorithms, but left many questions open: How to decom-pose a domain into factors? How to work with these fac-tors? And whether and when decomposition-based methods are useful? This paper provides theoretical analysis that an-swers many of these questions: it proposes a novel approach to factored planning; proves its theoretical superiority over previous methods; provides insight into how to factor do-mains; and uses its novel complexity results to analyze when factored planning is likely to perform well, and when not. It also establishes the key role played by the domain’s causal graph in the complexity analysis of planning algorithms.