A Reduced Ordered Binary Decision Diagram (BDD) is a symbolic data structure introduced to the model checking community by Bryant in 1986 to help verify properties of systems with very large state spaces. Recently, BDDs have been used in heuristic search algorithms as an approach to representing and solving search problems with very large state spaces. However, these algorithms are still not memory efficient. This thesis presents a symbolic heuristic search algorithm that uses BDDs in a memory efficient way by performing bidirectional breadthirst heuristic search. The approach is evaluated empirically against existing symbolic methods and is shown to provide a significant improvement in performance.
| Identifer | oai:union.ndltd.org:MSSTATE/oai:scholarsjunction.msstate.edu:td-5174 |
| Date | 11 December 2004 |
| Creators | Richards, Simon Kim |
| Publisher | Scholars Junction |
| Source Sets | Mississippi State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses and Dissertations |
Page generated in 0.002 seconds