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

Jeremy S. Lewis, Jason M. O'Kane
International Journal of Robotics Research
vol. 32
no. 32
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 2020-09-23.