Stefan Edelkamp, Peter Kissmann
The idea of using BDDs for optimal sequential planning is to reduce the memory requirements for the state sets as problem sizes increase. State variables are encoded binary and ordered along their causal graph dependencies. Sets of planning states are represented in form of Boolean functions, and actions are formalized as transition relations. This allows to compute the successor state set, which determines all states reached by applying one action to the states in the input set. Iterating the process (starting with the representation of the initial state) yields a symbolic implementation of breadth-first search. This paper studies the causes for good and bad BDD performance by providing lower and upper bounds for BDD growth in various domains. Besides general applicability to planning benchmarks, our approach covers different cost models; it applies to step-optimal propositional planning as well as planning with additive action costs.
Subjects: 15.7 Search; 1.11 Planning
Submitted: Apr 14, 2008