RI | Publications | The Focussed D* Algorithm for Real-Time Replanning

Text only version of this site

The Focussed D* Algorithm for Real-Time Replanning
A. Stentz
Proceedings of the International Joint Conference on Artificial Intelligence, August, 1995.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Download [Help]

Adobe portable document format (pdf) [82 KB]
Compressed postscript (ps.gz) [125 KB]

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 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.

Notes

Associated centers: SRI and FRC
Associated project: Mars Autonomy

Text Reference

A. Stentz, "The Focussed D* Algorithm for Real-Time Replanning," Proceedings of the International Joint Conference on Artificial Intelligence, August, 1995.

BibTeX Reference

@inproceedings{Stentz_1995_1213,
   author = "Anthony (Tony) Stentz",
   title = "The Focussed D* Algorithm for Real-Time Replanning",
   booktitle = "Proceedings of the International Joint Conference on Artificial Intelligence",
   month = "August",
   year = "1995"
}