The Focussed D* Algorithm for Real-Time Replanning - Robotics Institute Carnegie Mellon University

The Focussed D* Algorithm for Real-Time Replanning

Conference Paper, Proceedings of 14th International Joint Conference on Artificial Intelligence (IJCAI '95), pp. 1652 – 1659, August, 1995

Abstract

Finding the lowest-cost path through a graph is central to many problems, including route planning for a mobile robot. If arc costs change during the traverse, then the remainder of the path may need to be replanned. This is the case for a sensor-equipped mobile robot with imperfect information about its environment. As the robot acquires additional information via its sensors, it can revise its plan to reduce the total cost of the traverse. If the prior information is grossly incomplete, the robot may discover useful information in every piece of sensor data. During replanning, the robot must either wait for the new path to be computed or move in the wrong direction; therefore, rapid replanning is essential. The D* algorithm (Dynamic A*) plans optimal traverses in real-time by incrementally repairing paths to the robot's state as new information is discovered. This paper describes an extension to D* that focusses the repairs to significantly reduce the total time required for the initial path calculation and subsequent replanning operations. This extension completes the development of the D* algorithm as a full generalization of A* for dynamic environments, where arc costs can change during the traverse of the solution path.

BibTeX

@conference{Stentz-1995-13935,
author = {Anthony (Tony) Stentz},
title = {The Focussed D* Algorithm for Real-Time Replanning},
booktitle = {Proceedings of 14th International Joint Conference on Artificial Intelligence (IJCAI '95)},
year = {1995},
month = {August},
pages = {1652 – 1659},
}