Complete Topological Mapping with Sparse Sensing

Wesley H. Huang and Kristopher R. Beevers
Rensselaer Polytechnic Institute, Department of Computer Science
Technical Report 05-06, March 2005.
[pdf]

Abstract

This paper describes algorithms for a mobile robot with sparse, short-range sensing to create a topological map of an unknown environment. While a limited array of sensors is appealing from the standpoint of having simpler and cheaper hardware, mapping is more difficult because the robot cannot guarantee it will detect obstacles as soon as they enter its sensing range. Thus, the robot's mapping strategy must ensure that all relevant parts of the environment are observed. Our approach constructs topological maps based on the SGVD_\infty, a version of the saturated generalized Voronoi diagram defined under the L_\infty distance metric, which is well-suited to robots with sparse sensing. We first describe behaviors that allow a robot with an omnidirectional short-range sensor to trace the SGVD_\infty, and then extend these behaviors to the sparse sensing case by introducing a &ldqua;virtual sensor” that tracks unseen obstacles and emulates the output of the omnidirectional sensor. We show that our behaviors are complete for the problem of mapping an arbitrary rectilinear environment. We have implemented the mapping behaviors and report the results of simulated experiments.

BibTeX entry

@TechReport{Huang00c,
  author = 	 {Wesley H. Huang and Kristopher R. Beevers},
  title = 	 {Complete Topological Mapping with Sparse Sensing},
  institution =  {Rensselaer Polytechnic Institute Department of Computer Science},
  year = 	 2005,
  number =	 6,
  month =	 {March}
}