BDDPlan

BDDPlan is my attempt at planning by means of BDDs (Binary Decision Diagrams). You can read in the technical report hoelldobler:stoerr:00d as well as in hoelldobler:stoerr:00c, stoerr:thielscher:00 and stoerr:2003 about the theoretical background. A short general description is in stoerr:01.

The basic idea is to map a planning problem represented as an entailment problem in the fluent calculus, which is a way to specify action and change problems in first order logic, to propositional logic in a way that a plan, if one exists, can be reconstructed from models of the propositional formulae. In contrast to existing planning algorithms like SATPLAN, which map each planning problem to one large SAT-problem whose solutions represent possible plans, is that a series of propositional formulae is generated, which represent the set of reachable states after the execution of n actions successively. These formulae are represented by BDDs and are recursively calculated by means of BDDs. The process is repeated, until the set of goal states is met.

The good points about this kind algorithm are: * It always finds a shortest plan. There is no polynomial length restriction of the plans found, as in SATPLAN. * If there is no plan then it is able to prove there isn't one. * It is able to reuse its results to generate many solutions for the planning problem or a subset of its results for planning problems with different initial state but equal transition relation.

Of course, the above points hold only iff the computational ressources are sufficient. This is exactly the weak point: BDDs are prone to get very large. In the worst case they are exponential in the number of (ground instances of) fluents in the problem. The algorithm performs a symbolic breadth first search in the reachability tree of the planning problem. Thus, the represented sets can get very complex and large. The search is implicite, though, i.e. the states searched are never explicitly enumerated, but are represented as BDDs, which are often very small in comparison to the represented set. This is the basic hope behind using the idea: in practical problems the BDDs should often be small enough to solve the problem, even though the search space is extremely large.

Furthermore, I think BDDs lead to an very interesting way to think about problems: you don't think with clauses and formulas and stuff, but boolean functions.

Some technical trivia: BDDPlan is written in C++ (which I wanted to improve my knowledge of), making extensive use of the standard template library (which I wanted to learn about) and relies on the BDD library CAL for which I have written an objectoriented interface. As input language for planning problems I use the ADL-subset of PDDL (the Planning Domain Definition Language).