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

Authors

  • Carlos Hernandez Universidad Católica de la Smma. Concepción
  • Pedro Meseguer Institute d'Investigacio
  • Xiaoxun Sun University of Southern California
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/icaps.v19i1.13395

Keywords:

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

Abstract

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.

Downloads

Published

2009-10-16

How to Cite

Hernandez, C., Meseguer, P., Sun, X., & Koenig, S. (2009). Path-Adaptive A* for Incremental Heuristic Search in Unknown Terrain. Proceedings of the International Conference on Automated Planning and Scheduling, 19(1), 358-361. https://doi.org/10.1609/icaps.v19i1.13395

Issue

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

Section

Short Papers