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

Abstract This paper addresses a navigation problem for a very simple robot equipped with only a map, 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 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. To accelerate the planning process, we also present a priority function to focus computational effort on attempting to generate edges between the most promising node pairs. We have implemented this algorithm and present results from both simulation and a physical realization on the iRobot Create differential drive platform.

@article{LewOKa13,
  author = {Jeremy S. Lewis and Jason M. O'Kane},
  journal = {International Journal of Robotics Research},
  month = {September},
  number = {11},
  pages = {1339--1354},
  title = {Planning for provably reliable navigation using an
           unreliable, nearly sensorless robot},
  volume = {32},
  year = {2013}
}