B. J. Kuipers & Y.-T. Byun. 1991.
A robot exploration and mapping strategy based on a semantic hierarchy
of spatial representations.
Journal of Robotics and Autonomous Systems, 8: 47-63, 1991.
We have developed a robust qualitative method for robot exploration, mapping, and navigation in large-scale spatial environments. Experiments with a simulated robot in a variety of complex 2D environments have demonstrated that our qualitative method can build an accurate map of a previously unknown environment in spite of substantial random and systematic sensorimotor error.
Most current approaches to robot exploration and mapping analyze sensor input to build a geometrically precise map of the environment, then extract topological structure from the geometric description. Our approach recognizes and exploits qualitative properties of large-scale space before relatively error-prone geometrical properties.
[sensorimotor ↔ control] → topology → geometry
At the control level, distinctive places and distinctive travel edges are identified based on the interaction between the robot's control strategies, its sensorimotor system, and the world. A distinctive place is defined as the local maximum of a distinctiveness measure appropriate to its immediate neighborhood, and is found by a hill-climbing control strategy. A distinctive travel edge, similarly, is defined by a suitable measure and a path-following control strategy. The topological network description is created by linking the distinctive places and travel edges. Metrical information is then incrementally assimilated into local geometric descriptions of places and edges, and finally merged into a global geometric map. Topological ambiguity arising from sensorily indistinguishable places can be resolved at the topological level by the exploration strategy. With this representation, successful navigation is not critically dependent on the accuracy, or even the existence, of the geometrical description.
We present examples demonstrating the process by which the robot explores and builds a map of a complex environment, including the effect of sensory errors. We also discuss new research directions that are suggested by this approach.