Optimal and efficient path planning for partially-known environments

The task of planning trajectories for a mobile robot has received considerable attention in the research literature. 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 partially known environments. This situation occurs for an exploratory robot or one that must move to a goal location without the benejit of ajloorplan or terrain map. Existing approaches plan an initial path based on known information and then modijj the plan locally or replan the entire path as the robot discovers obstacles with its sensors, sacrgcing optimulity or computational efJiciency respectively. This paper introduces a new algorithm, D*, capable of planning paths in unknown, partially known