Best-first utility-guided search

• Twentieth International Conference on Artificial Intelligence (IJCAI-07)

In many shortest-path problems of practical interest, insufficient time is available to find a provably optimal solution. In dynamic environments, for example, the expected value of a plan may decrease with the time required to find it. One can only hope to achieve an appropriate balance between search time and the resulting plan cost. Several algorithms have been proposed for this setting, including weighted A*, Anytime A*, and ARA*. These algorithms multiply the heuristic evaluation of a node, exaggerating the effect of the cost-to-go. We propose a more direct approach, called Bugsy, in which one explicitly estimates search-nodes-to-go. One can then attempt to optimize the overall utility of the solution, expressed by the user as a function of search time and solution cost. Experiments in several problem domains, including motion planning and sequence alignment, demonstrate that this direct approach can surpass anytime algorithms without requiring performance profiling.

• go to publisher site »

citation

Ruml, W. ; Do, M. B. Best-first utility-guided search. Twentieth International Conference on Artificial Intelligence (IJCAI-07); 2007 January 6-12; Hyderabad; India; 2378-2384.