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

Anthony (Tony) Stentz
tech. report CMU-RI-TR-94-37, Robotics Institute, Carnegie Mellon University, October, 1994


Download
  • Adobe portable document format (pdf) (1MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes
Sponsor: ARPA
Grant ID: DACA76-89-C-0014, DAAE07-90-C-R059
Number of pages: 30

Text Reference
Anthony (Tony) Stentz, "The D* Algorithm for Real-Time Planning of Optimal Traverses," tech. report CMU-RI-TR-94-37, Robotics Institute, Carnegie Mellon University, October, 1994

BibTeX Reference
@techreport{Stentz_1994_356,
   author = "Anthony (Tony) Stentz",
   title = "The D* Algorithm for Real-Time Planning of Optimal Traverses",
   booktitle = "",
   institution = "Robotics Institute",
   month = "October",
   year = "1994",
   number= "CMU-RI-TR-94-37",
   address= "Pittsburgh, PA",
}