SetA~*: An Efficient BDD-Based Heuristic Search Algorithm

摘要

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 HDD-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.