Name
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. |
Year | Venue | Keywords |
|---|---|---|
2002 | Eighteenth national conference on Artificial intelligence | breadth first search,bayesian networks,heuristic search,polynomial time |
Field | DocType | ISBN |
Incremental heuristic search,Heuristic,Computer science,Algorithm,Beam search,Heuristics,Bayesian network,Artificial intelligence,Time complexity,Machine learning,Best-first search,Traverse | Conference | 0-262-51129-0 |
Citations | PageRank | References |
34 | 1.12 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rune M. Jensen | 1 | 174 | 9.27 |
| Randal E. Bryant | 2 | 9204 | 1194.64 |
| Manuela Veloso | 3 | 8563 | 882.50 |