Optimal Graph Search with Iterated Graph Cuts


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


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




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



Constraints, Satisfiability, and Search