SetA*: An efficient BDD-Based Heuristic Search Algorithm

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

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


In this paper we combine the goal directed search of A* with the ability of BDDs to traverse an exponential number of states in polynomial time. We introduce a new algorithm, SetA*, that generalizes A* to expand sets of states in each iteration. SetA* has substantial advantages over BDDA*, the only previous BDD-based A* implementation we are aware of. Our experimental evaluation proves SetA* to be a powerful search paradigm. For some of the studied problems it outperforms BDDA*, A*, and BDD based breadth-first search by several orders of magnitude. We believe exploring sets of states to be essential when the heuristic function is weak. For problems with strong heuristics, SetA* efficiently specializes to single-state search and consequently challenges single state heuristic search in general.
Original languageEnglish
Title of host publicationProceedings of Eighteenth National Conference on Artificial Intelligence (AAAI'02)
Number of pages6
PublisherAAAI Press
Publication date2002
ISBN (Print)978-0-262-51129-2
Publication statusPublished - 2002
Externally publishedYes


  • A* algorithm
  • Binary Decision Diagrams
  • Set-based search
  • Heuristic search
  • State space traversal


Dive into the research topics of 'SetA*: An efficient BDD-Based Heuristic Search Algorithm'. Together they form a unique fingerprint.

Cite this