State-set branching: Leveraging BDDs for heuristic search

Rune Møller Jensen, Manuela M. Veloso, Randal E. Bryant

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

Abstract

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*.
Original languageEnglish
JournalArtificial Intelligence
Volume172
Issue number2-3
Pages (from-to)103-139
Number of pages37
ISSN0004-3702
DOIs
Publication statusPublished - 2008

Keywords

  • Heuristic search
  • BDD-based search
  • Boolean representation

Fingerprint

Dive into the research topics of 'State-set branching: Leveraging BDDs for heuristic search'. Together they form a unique fingerprint.

Cite this