Map-based Strategies for Robot Navigation in Unknown Environments

Anthony Stentz

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.