A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations

Abstract

Kuipers, B. and Byun, Y.T., A robot exploration and mapping strategy based on a sematic hierarchy of spatial representations, Robotics and Autonomous System, 8 (1991) 47–63. 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 unkown 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 before relatively error-prone geometrical properties. 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 localgeometric 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.