State-Set Branching: Leveraging OBDDs for Heuristic Search

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

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

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*.
OriginalsprogEngelsk
ForlagCarnegie Mellon University
UdgaveTechnical Report CMU-CS-02-174
Antal sider51
StatusUdgivet - 2002
Udgivet eksterntJa

Emneord

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

Fingeraftryk

Dyk ned i forskningsemnerne om 'State-Set Branching: Leveraging OBDDs for Heuristic Search'. Sammen danner de et unikt fingeraftryk.

Citationsformater