State-Set Branching: Leveraging OBDDs for Heuristic Search

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

Research output: Book / Anthology / Report / Ph.D. thesisReportResearch

Abstract

In this paper, we introduce a framework called state-set branching that combines symbolic search based on the reduced Ordered Binary Decision Diagram (OBDD) with classical heuristic search, such as A* and 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 OBDD technique called branching partitioning can be used to efficiently expand sets of states. The framework is general. It applies to any heuristic function, any evaluation function, and any transition cost function. Moreover, branching partitioning applies to both disjunctive and conjunctive transition relation partitioning, An extensive experimental evaluation involving several new and classical domains proves state-set branching to be a powerful framework. It consistently outperforms single-state A*, except when the heuristic is very strong. In addition, we show that it can improve the complexity of single-state search exponentially and that it often dominates both single-state A* and blind OBDD-based search by several orders of magnitude. Moreover, it has substantially better performance than BDDA*, the only previous OBDD-based implementation of A*.
Original languageEnglish
PublisherCarnegie Mellon University
EditionTechnical Report CMU-CS-02-174
Number of pages51
Publication statusPublished - 2002
Externally publishedYes

Keywords

  • state-set branching
  • symbolic search
  • reduced Ordered Binary Decision Diagram (OBDD)
  • heuristic search
  • branching partitioning

Fingerprint

Dive into the research topics of 'State-Set Branching: Leveraging OBDDs for Heuristic Search'. Together they form a unique fingerprint.

Cite this