Limits and Possibilities of BDDs for State Space Search

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.