Optimal Graph Search with Iterated Graph Cuts
| Autor: | David Burkett, David Hall, Dan Klein |
|---|---|
| Rok vydání: | 2011 |
| Předmět: | |
| Zdroj: | Proceedings of the AAAI Conference on Artificial Intelligence. 25:12-17 |
| ISSN: | 2374-3468 2159-5399 |
| DOI: | 10.1609/aaai.v25i1.7829 |
| Popis: | 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*. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|