Abstract

C. Hernandez, P. Meseguer, X. Sun and S. Koenig. Path-Adaptive A* for Incremental Heuristic Search in Unknown Terrain. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages 358-361, 2009.

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. Errata: In the pseudocode in Figure 4, c(s,a) should be c(s,s') on Line 32 and the statement on Line 46 is unnecessary (but not wrong). Furthermore, this version of the paper already corrects two other small mistakes: The table entries for acyclic and cyclic mazes were swapped and Line 52 in the pseudocode should use sstart instead of s.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.


This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.