SetA*: An efficient BDD-Based Heuristic Search Algorithm

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

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer 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.
TitelProceedings of Eighteenth National Conference on Artificial Intelligence (AAAI'02)
Antal sider6
ForlagAAAI Press
ISBN (Trykt)978-0-262-51129-2
StatusUdgivet - 2002
Udgivet eksterntJa


Dyk ned i forskningsemnerne om 'SetA*: An efficient BDD-Based Heuristic Search Algorithm'. Sammen danner de et unikt fingeraftryk.