Symbolic Bidirectional Breadth-First Heuristic Search
Allen, Edward B.
Date of Degree
Original embargo terms
MSU Only Indefinitely
Graduate Thesis - Open Access
Master of Science
James Worth Bagley College of Engineering
Department of Computer Science and Engineering
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.
Richards, Simon Kim, "Symbolic Bidirectional Breadth-First Heuristic Search" (2004). Theses and Dissertations MSU. 4175.