Proceedings

The Focussed D* Algorithm for Real-Time Replanning

Download BibTeX Cite

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Planning. Pages 1662-1668.

© 1995 International Joint Conferences on Artificial Intelligence

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

  1. [Boult, 1987] T. Boult. Updating distance maps when objects move. In Proceedings of the SPIE Conference on Mobile Robots, 1987.
  2. [Jarvis, 1985] R. A. Jarvis. Collision-free trajectory plan- ning using the distance transforms. Mechanical Engineering Trans. of the Institution of Engineers, M£10(3), September 1985.
  3. [Korf, 1987] R. E . Korf. Real-time heuristic search: first results. In Proceedings of the Sixth National Conference on Artificial Intelligence, July 1987.
  4. [Lumelsky and Stepanov, 1986] V. J. Lumelsky and A. A. Stepanov. Dynamic path planning for a mobile automaton with limited information on the environment. IEEE Transac- tions on Automatic Control, AC-31(11), November 1986.
  5. [Nilsson, 1980] N.J. Nilsson. Principles of Artificial Intelli- gence, Tioga Publishing Company, 1980, pp. 72-88.
  6. [Pirzadeh and Snyder, 1990] A. Pirzadeh and W. Snyder. A unified solution to coverage and search in explored and unexplored terrains using indirect control. In Proceedings of the IEEE International Conference on Robotics and Automa- tion, May 1990.
  7. [Ramalingam and Reps, 1992] G. Ramalingam and T. Reps. An incremental algorithm for a generalization of the short- est-path problem. University of Wisconsin Technical Report #1087, May 1992.
  8. [Stentz, 1993] A. Stentz. Optimal and efficient path plan- ning for unknown and dynamic environments. Carnegie Mellon Robotics Institute Technical Report CMU-RI-TR- 93-20, August 1993.
  9. [Stentz, 1994] A. Stentz. Optimal and efficient path plan- ning for partially-known environments. In Proceedings of the IEEE International Conference on Robotics and Automa- tion, May 1994.
  10. [Trovato, 1990] K. I. Trovato. Differential A*: an adaptive search method illustrated with robot path planning for mov- ing obstacles and goals, and an uncertain environment. Jour- nal of Pattern Recognition and Artificial Intelligence, 4(2), 1990.
  11. [Zelinsky, 1992] A. Zelinsky. A mobile robot exploration algorithm. IEEE Transactions on Robotics and Automation, 8(6), December 1992.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards