Planning in the Fluent Calculus Using Binary Decision Diagrams

In the past, BDDs have significantly improved the performance of algorithms and enabled the solution of new classes of problems in areas such as formal verification and logic synthesis (see, for example, Burch et al. [1992]). Surprisingly, BDDs have only recently been introduced to implement the solution of planning problems (Cimatti et al. 1997). The goal of our project was to investigate whether BDDs might also help to increase the efficiency of algorithms solving problems in the field of reasoning about action and change. For a start, I have implemented the solution of fluent calculus planning problems restricted to deterministic actions and propositional fluents (Hölldobler and Störr 2000; Störr 2001). The idea of BDDs is similar to decision trees: A Boolean function is represented as a rooted acyclic-directed graph.