Planning for provably reliable navigation using an unreliable, nearly sensorless robot

Abstract

This paper addresses a navigation problem for a certain type of simple mobile robot modeled as a point moving in the plane. The only requirement on the robot is that it must be able to translate in a desired direction, with bounded angular error (measured in a global reference frame), until it reaches the nearest obstacle in its motion direction. One straightforward realization of this capability might use a noisy compass and a contact sensor. We present a planning algorithm that enables such a robot to navigate reliably through its environment. The algorithm constructs a directed graph in which each node is labeled with a subset of the environment boundary. Each edge of the graph is labeled with a sequence of actions that can move the robot from any location in one such set to some location in the other set. We use a variety of local planners to generate the edges, including a “corner-finding” technique that allows the robot to travel to and localize itself at a convex vertex of the environment boundary. The algorithm forms complete plans by searching the resulting graph. We have implemented this algorithm and present results from both simulation and a proof-of-concept physical realization.