The D* Algorithm for Real-Time Planning of Optimal Traverses

Abstract

Finding the lowest-cost path through a graph of states 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. Such is the case for a sensor-equipped mobile robot with incomplete or inaccurate information about its environment. As the robot acquires additional information via its sensors, it has the opportunity to revise its plan to reduce the total cost of the traverse. If the prior information is grossly incomplete or inaccurate, the robot may discover useful information in nearly every piece of sensor data. During the replanning process, the robot must either stop and wait for the new path to be computed or continue to move in the wrong direction; therefore, rapid replanning is essential. This paper describes a new algorithm, D*, capable of planning optimal traverses in real-time through focussed state expansion. D* repairs plans quickly by taking advantage of the fact that most arc cost corrections occur in the vicinity of the robot and the path needs only to replanned out to the robot's current state. D* can be used not only for route planning but for any graph-based cost optimization problem for which arc costs change during the traverse of the solution path.