Carnegie Mellon University
Optimal and Efficient Path Planning for Unknown and Dynamic Environments

Anthony (Tony) Stentz
tech. report CMU-RI-TR-93-20, Robotics Institute, Carnegie Mellon University, August, 1993

  • Adobe portable document format (pdf) (2MB)
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.

The task of planning trajectories for a mobile robot has received considerable attention in the research literature. Algorithms exist for handling a variety of robot shapes, configurations, motion constraints, and environments. Most of the work assumes the robot has a complete and accurate model of its environment before it begins to move; less attention has been paid to the problem of unknown or partially-known environments. This situation occurs for an exploratory robot or one that must move to a goal location without the benefit of a floorplan (indoor) or terrain map (outdoor). Existing approaches plan an initial global path or route based on known information and then modify the plan locally as the robot discovers obstacles with its sensors. While this strategy works well in environments with small, sparse obstacles, it can lead to grossly suboptimal and incomplete results in cluttered spaces. An alternative approach is to replan the global path from scratch each time a new obstacle is discovered. While this approach is optimal, it is grossly inefficient and can require a high-performance computer for real-time operation. This paper introduces a new algorithm, D*, capable of planning paths in unknown, partially-known, and changing environments in an efficient, optimal, and complete manner. D* models the environment as a graph, where each node represents a robot state (e.g., a location in a room), and each arc represents the cost (e.g., distance to travel) of moving between two states. Initially, a path is planned from the goal to the robot's location using known information. As the robot moves, its sensors discover obstacles in its path. These discoveries are handled by modifying the arc costs. D* propagates information minimally about these arc changes in the graph to compute a new optimal path. The process repeats until the robot reaches the goal or determines that it cannot. After a discussion of prior work, the paper introduces the algorithm, proves its soundness, optimality, and completeness, illustrates some path planning applications, compares it to an alternative algorithm, and summarizes the results.

exploratory robot, path plans, unknown environments, partially-known environments, D*

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

Text Reference
Anthony (Tony) Stentz , "Optimal and Efficient Path Planning for Unknown and Dynamic Environments," tech. report CMU-RI-TR-93-20, Robotics Institute, Carnegie Mellon University, August, 1993

BibTeX Reference
   author = "Anthony (Tony) {Stentz }",
   title = "Optimal and Efficient Path Planning for Unknown and Dynamic Environments",
   booktitle = "",
   institution = "Robotics Institute",
   month = "August",
   year = "1993",
   number= "CMU-RI-TR-93-20",
   address= "Pittsburgh, PA",