Abstract

S. Koenig and M. Likhachev. A New Principle for Incremental Heuristic Search: Theoretical Results [Short Paper]. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages 402-405, 2006.

Abstract: Planning is often not a one-shot task because either the world or the agent's knowledge of the world changes. In this paper, we introduce a new principle that can be used to solve a series of similar search tasks faster with heuristic search methods than running individual searches in isolation, by updating the heuristics over time to make them more informed and thus future searches more focused. This principle is simple and easy to integrate into heuristic search methods, and it is easy to prove the correctness of the resulting heuristic search methods. Comment: Robert Holte has recently pointed out to us that his Hierarchical A* (R. Holte, T. Mkadmi, R. Zimmer, A. MacDonald. Speeding up Problem Solving by Abstraction: A Graph Oriented Approach. Artificial Intelligence, 85(1-2), 321-361, 1996), although it is not an incremental heuristic search method, updates the heuristics in a way similar to Adaptive A*. You might want to check out his search method as well.

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.