Title :
Optimal and efficient path planning for partially-known environments
Author_Institution :
Robotics Inst., Carnegie Mellon Univ., Pittsburgh, PA, USA
Abstract :
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 benefit of a floorplan or terrain map. Existing approaches plan an initial path based on known information and then modify the plan locally or replan 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
Keywords :
computational complexity; mobile robots; optimisation; path planning; D* algorithm; changing environments; efficient path planning; exploratory robot; mobile robot; optimal path planning; partially-known environments; planning trajectories; unknown environments; Cost function; Mobile robots; Motion planning; Orbital robotics; Path planning; Regions; Robot sensing systems; State estimation; State-space methods; Trajectory;
Conference_Titel :
Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-5330-2
DOI :
10.1109/ROBOT.1994.351061