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

Jeremy S. Lewis, Jason M. O'Kane
International Journal of Robotics Research
September 2013


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},
  title        = {Planning for provably reliable navigation using an
		 unreliable, nearly sensorless robot},
  journal      = {International Journal of Robotics Research},
  volume       = {32},
  number       = {11},
  month        = {September},
  pages        = {1339--1354},
  year	       = {2013}

O'Kane's home page
O'Kane's publication list

Wed Mar 4 12:52:19 EST 2020