Factored Planning

Eyal Amir1 and Barbara Engelhardt
(Professor Stuart J. Russell)
(DOD-ONR) MURI FD N00014-01-1-0890, (DOD-ONR) MURI FD N00014-00-1-0637, and National Science Foundation

In this work we investigate a general-purpose planning approach that finds plans in structured domains. Our algorithm factors a planning domain into subdomains and finds plans using this factorization. The runtime for our algorithm scales linearly with the size of the domain, and exponentially with the size of the largest subdomain and the amount of interaction between subdomains. We achieve this by limiting the amount of back-and-forth interactions that a plan allows between subdomains, and by choosing a factoring that minimizes this interaction. We do so using earlier work on graph partitioning and treewidth, but the user may also provide a factorization to the algorithm. We prove that our planning algorithm is sound and complete.

Many real-world planning domains have the decomposable structure that our approach exploits. We implemented and tested our algorithm in such domains and discovered that it finds plans in a fraction of the time taken by state-of-the-art planners, and scales to very large problems.

[1]
E. Amir, "(De)Composition of Situation Calculus Theories," Proc. Natl. Conf. Artificial Intelligence, Austin, TX, July-August 2000.
[2]
E. Amir, "Projection in Decomposed Situation Calculus," Proc. Int. Conf. Principles of Knowledge Representation and Reasoning, Toulouse, France, April 2002.
1Postdoctoral Researcher

More information (http://www.cs.berkeley.edu/~eyal) or

Send mail to the author : (eyal@eecs.berkeley.edu)


Edit this abstract