Reliable Indoor Navigation with an Unreliable Robot: Allowing Temporary Uncertainty for Maximum Mobility

Jeremy S. Lewis, Jason M. O'Kane
In Proc. IEEE International Conference on Robotics and Automation 2012.

Abstract

In this work we consider a navigation problem for a very simple robot equipped with only a map, compass, and contact sensor. Our prior work on this problem uses a graph to navigate between the convex vertices of an environment. In this paper, we extend this graph with the addition of a new node type and four new edge types. The new node type allows for more uncertainty in robot position. The presence of one of these new edge types guarantees reliable transitions between these nodes. This enhanced graph enables the algorithm to navigate environment features not solvable by our previous algorithm, including T-junctions and long halls. We also present a heuristic to accelerate the planning process by prioritizing the promising edge tests to perform. Our heuristic effectively focuses the search and qualitative data show that it computes plans with much less computational effort than a naive approach. We describe a simulated implementation of the algorithm that finds paths not previously possible, and a physical implementation that demonstrates the feasibility of executing those plans in practice.

Download

BibTeX

@inproceedings{LewOKa12,
  author       = {Jeremy S. Lewis and Jason M. O'Kane},
  title        = {Reliable Indoor Navigation with an Unreliable Robot:
		 Allowing Temporary Uncertainty for Maximum Mobility},
  booktitle    = {Proc. IEEE International Conference on Robotics and
		 Automation},
  year	       = {2012}
}

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

Wed Sep 20 09:19:46 EDT 2017