Patrick Beeson, Nicholas K. Jong, and Benjamin Kuipers. 2005.
Towards autonomous topological place detection using the Extended Voronoi
Graph.
IEEE International Conference on Robotics and
Automaton (ICRA-05).
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.
Download
BJK