A New Principle for Incremental Heuristic Search: Theoretical Results

Sven Koenig* and Maxim Likhachev**

*University of Southern California, **Carnegie Mellon University

 

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.