Complete Topological Mapping with Sparse Sensing Wesley H. Huang Kristopher R. Beevers Topological Mapping, Saturated Generalized Voronoi Diagram Sensing Limitations 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 SGVD1, a version of the saturated generalized Voronoi diagram defined under the L1 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 SGVD1, and then extend these behaviors to the sparse sensing case by introducing a “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. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-05-06
Complete Topological Mapping with Sparse Sensing
Wesley H. Huang
Kristopher R. Beevers
Topological Mapping,
Saturated Generalized Voronoi Diagram
Sensing Limitations
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 SGVD1, a version of the saturated generalized Voronoi diagram defined under the L1 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 SGVD1, and then extend these behaviors to the sparse sensing case by introducing a “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.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-05-06