Towards autonomous topological place detection using the extended Voronoi graph

Patrick Beeson, Nicholas K. Jong, and Benjamin Kuipers. Towards autonomous topological place detection using the extended Voronoi graph. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 4373–4379, Barcelona, Spain, April 2005.

Abstract

Autonomous place detection has long been a major hurdle to topological map-building techniques. Theoretical work on topological mapping has assumed that places can be reliably detected by a robot, resulting in deterministic actions. Whether or not deterministic place detection is always achievable is controversial; however, even topological mapping algorithms that assume non-determinism benefit from highly reliable place detection. Unfortunately, topological map-building implementations often have hand-coded place detection algorithms that are brittle and domain dependent. This paper presents an algorithm for reliable autonomous place detection that is sensor and domain independent. A preliminary implementation of this algorithm for an indoor robot has demonstrated reliable place detection in real-world environments, with no a priori environmental knowledge. The implementation uses a local, scrolling 2D occupancy grid and a real-time calculated Voronoi graph to find the skeleton of the free space in the local surround. In order to utilize the place detection algorithm in non-corridor environments, we also introduce the extended Voronoi graph (EVG), which seamlessly transitions from a skeleton of a midline in corridors to a skeleton that follows walls in rooms larger than the local scrolling map.

Additional Information

Talk slides

BibTeX

@InProceedings{Beeson-icra-05,
  author =       {Patrick Beeson and Nicholas K. Jong and Benjamin Kuipers},
  title =        {Towards autonomous topological place detection using the
                  extended {Voronoi} graph},
  booktitle =    {Proceedings of the IEEE International Conference on Robotics
                  and Automation (ICRA)},
  year =         2005,
  address =      {Barcelona, Spain},
  month =        {April},
  pages =        {4373--4379},
  abstract =     {Autonomous place detection has long been a major hurdle to
                  topological map-building techniques. Theoretical work on
                  topological mapping has assumed that places can be reliably
                  detected by a robot, resulting in deterministic
                  actions. Whether or not deterministic place detection is
                  always achievable is controversial; however, even
                  topological mapping algorithms that assume non-determinism
                  benefit from highly reliable place detection. Unfortunately,
                  topological map-building implementations often have
                  hand-coded place detection algorithms that are brittle and
                  domain dependent.  This paper presents an algorithm for
                  reliable autonomous place detection that is sensor and
                  domain independent. A preliminary implementation of this
                  algorithm for an indoor robot has demonstrated reliable
                  place detection in real-world environments, with no a priori
                  environmental knowledge. The implementation uses a local,
                  scrolling 2D occupancy grid and a real-time calculated
                  Voronoi graph to find the skeleton of the free space in the
                  local surround. In order to utilize the place detection
                  algorithm in non-corridor environments, we also introduce
                  the extended Voronoi graph (EVG), which seamlessly
                  transitions from a skeleton of a midline in corridors to a
                  skeleton that follows walls in rooms larger than the local
                  scrolling map.},
  bib2html_pubtype ={Refereed Conference},
  bib2html_rescat ={Topological/Hybrid Map-Building},
  bib2html_extra_info ={<a
                  href="http://personal.traclabs.com/~pbeeson/talks/Beeson-icra-05_talk.pdf">
                  Talk slides</a>},
}

Download:

[325.9KB pdf]