Title

Symbolic Bidirectional Breadth-First Heuristic Search

Advisor

Hansen, Eric

Committee Member

Allen, Edward B.

Committee Member

Hodges, Julia

Date of Degree

1-1-2004

Original embargo terms

MSU Only Indefinitely

Document Type

Graduate Thesis - Open Access

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

This document is currently not available here.

Share

COinS