Factored planning

Abstract

We present a general-purpose method for dynamically factoring a planning domain, whose structure is then exploited by our generic planning method to find sound and complete plans. The planning algorithm's time complexity scales linearly with the size of the domain, and at worst exponentially with the size of the largest subdomain and interaction between subdomains. The factorization procedure divides a planning domain into subdomains that are organized in a tree structure such that interaction between neighboring subdomains in the tree is minimized. The combined planning algorithm is sound and complete, and we demonstrate it on a representative planning domain. The algorithm appears to scale to very large problems regardless of the black box planner used.