OPTIMAL AND EFFICIENT PATH PLANNING FOR UNKNOWN AND DYNAMIC ENVIRONMENTS

摘要

The task of planning trajectories for a mobile robot has received considerable attention in the research literature. Most 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 partially known environments. Existing approaches plan an initial path based on known information and then modify the plan locally or re-plan the entire path as the robot discovers obstacles with its sensors, sacrificing optimality or computational efficiency respectively. 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.