AAAI Publications, Nineteenth International Conference on Automated Planning and Scheduling

Font Size: 
Path-Adaptive A* for Incremental Heuristic Search in Unknown Terrain
Carlos Hernandez, Pedro Meseguer, Xiaoxun Sun, Sven Koenig

Last modified: 2009-10-16


Adaptive A* is an incremental version of A* that updates the h-values of the previous A* search to make them more informed and thus future A* searches more focused. In this paper, we show how the A* searches performed by Adaptive A* can reuse part of the path of the previous search and terminate before they expand a goal state, resulting in Path-Adaptive A*. We demonstrate experimentally that Path-Adaptive A* expands fewer states per search and runs faster than Adaptive A* when solving path-planning problems in initially unknown terrain.


Incremental Search;Heuristic Search;Path Planning;Free Space Assumption

Full Text: PDF  |  Errata