Path-Adaptive A* for Incremental Heuristic Search in Unknown Terrain

Vol. 19 (2009): Nineteenth International Conference on Automated Planning and Scheduling

Volume

Vol. 19 (2009): Nineteenth International Conference on Automated Planning and Scheduling

Short Papers

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.

10.1609/icaps.v19i1.13395