Homotopy-Driven Exploration of Human-made Spaces Using Signs

Abstract

Robots deployed in airports, malls, and stadiums today require expert oversight, pre-provided maps, and infrastructure. These systems are engineered to their specific deployment spaces and rely heavily on geometric maps for motion planning. In this work we consider a robot with only local-sensing and present a navigation strategy that uses signs and homotopy classes to fuel planning. We prove that in the worst-case, this strategy still maintains the probabilistic completeness that sampling based motion planners provide. Furthermore, we experimentally show that this exploration strategy results in 100% goal completion in real airport floor plans, and demonstrate how the robot’s sensing capabilities affects efficiency. We also show the effect of the environment variables, such as total number of obstacles, and density of obstacles, on navigation.