Carnegie Mellon University
Browse

State-Set Branching: Leveraging BDDs for Heuristic Search

journal contribution
posted on 2008-01-01, 00:00 authored by Rune M. Jensen, Manuela M. Veloso, Randal BryantRandal Bryant

In this article, we present a framework called state set branching that combines symbolic search based on reduced ordered Binary Decision Diagrams (BDDs) with best-first search, such as A* and greedy best-first search. The framework relies on an extension of these algorithms from expanding a single state in each iteration to expanding a set of states. We prove that it is generally sound and optimal for two A* implementations and show how a new BDD technique called branching partitioning can be used to efficiently expand sets of states. The framework is general. It applies to any heuristic function, evaluation function, and transition cost function defined over a finite domain. Moreover, branching partitioning applies to both disjunctive and conjunctive transition relation partitioning. An extensive experimental evaluation of the two A* implementations proves state-set branching to be a powerful framework. The algorithms outperform the ordinary A* algorithm in almost all domains. In addition, they can improve the complexity of A* exponentially and often dominate both A* and blind BDD-based search by several orders of magnitude. Moreover, they have substantially better performance than BDDA*, the currently most efficient BDD-based implementation of A*.

History

Date

2008-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC