Map-Based Strategies for Robot Navigation in Unknown Environments

Abstract

Robot path planning algorithms for finding a goal in a unknown environment focus on completeness rather than optimality. In this paper, we investigate several strategies for using map information, however incomplete or approximate, to reduce the cost of the robot's traverse. The strategies are based on optimistic, pessimistic, and average value assumptions about the unknown portions of the robot's environment. The strategies were compared using randomly-generated fractal terrain environments. We determined that average value approximations work best across small regions. In their absence, an optimistic strategy explores the environment, and a pessimistic strategy refines existing paths.