Optimal and Efficient Path Planning for Unknown and Dynamic Environments

Abstract

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.