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. 1 Introduction Path planning for mobile robots has been extensively studied in the robotics literature. Many algorithms exist for determining an optimal path from a starting point to a goal point given complete information about the robot's environment [Latombe, 91]. If the robot's environment is not f...