Compilation to Binary Decision Diagrams (BDDs)
Idea: Represent disjunctive plans as BDDs and plan extension as BDD operations
- Proposition list at level k is an approximation to the set of states reachable in k steps.
- The set can be represented compactly as BDDs
- Plan growth can be modeled as direct manipulations on BDD
- Operations such as “action projection” need to be modeled as BDD modifications
BDDs support compact representation and direct manipulation of boolean
formulae on a finite set of propositions. (Popular in CAD community)
Standard algorithms for converting a boolean formulae into BDDs and for
supporting standard boolean operations on them [Bryant et. al.]