SetA*: An efficient BDD-based heuristic search algorithm

July 2002

SetA*: An efficient BDD-based heuristic search algorithm

Authors:

Rune Jensen, Randy Bryant, and Manuela Veloso

Abstract:

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.
@conference{Jensen-2002-8521,
author = {Rune Jensen And Randy Bryant And Manuela Veloso},
title = {SetA*: An efficient BDD-based heuristic search algorithm},
booktitle = {Proceedings of 18th National Conference on Artificial Intelligence (AAAI '02)},
year = {2002},
month = {July},
pages = {668 - 673},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.