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

Jeremy S. Lewis and Jason M. O'Kane
International Journal of Robotics Research
vol. 32
no. 11
pp. 1339–1354
September 2013

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.

  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}

O'Kane's home page
O'Kane's publication list
Last updated 2024-03-28.