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.