Symbolic Bidirectional Breadth-First Heuristic Search

Author

Simon Kim Richards

Issuing Body

Mississippi State University

Advisor

Hansen, Eric

Committee Member

Allen, Edward B.

Committee Member

Hodges, Julia

Date of Degree

12-11-2004

Original embargo terms

MSU Only Indefinitely

Document Type

Graduate Thesis - Campus Access Only

Major

Computer Science

Degree Name

Master of Science

College

James Worth Bagley College of Engineering

Department

Department of Computer Science and Engineering

Abstract

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.

URI

https://hdl.handle.net/11668/19723

Comments

binary decision diagrams||heuristic search

Recommended Citation

Richards, Simon Kim, "Symbolic Bidirectional Breadth-First Heuristic Search" (2004). Theses and Dissertations. 4175.
https://scholarsjunction.msstate.edu/td/4175