Optimal Graph Search with Iterated Graph Cuts

Authors

  • David Burkett University of California, Berkeley
  • David Hall University of California, Berkele
  • Dan Klein University of California, Berkele

Abstract

Informed search algorithms such as A* use heuristics to focus exploration on states with low total path cost. To the extent that heuristics underestimate forward costs, a wider cost radius of suboptimal states will be explored. For many weighted graphs, however, a small distance in terms of cost may encompass a large fraction of the unweighted graph. We present a new informed search algorithm, Iterative Monotonically Bounded A* (IMBA*), which first proves that no optimal paths exist in a bounded cut of the graph before considering larger cuts. We prove that IMBA* has the same optimality and completeness guarantees as A* and, in a non-uniform pathfinding application, we empirically demonstrate substantial speed improvements over classic A*.

Downloads

Published

2011-08-04

How to Cite

Burkett, D., Hall, D., & Klein, D. (2011). Optimal Graph Search with Iterated Graph Cuts. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 12-17. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7829

Issue

Section

Constraints, Satisfiability, and Search