Robotic exploration and navigation on hierarchical spatial maps

This thesis is concerned with topological map building and navigation using these maps. Topological maps are compact spatial representations in which i) the continuous world is modeled as a discrete set of places and their spatial relations; and ii) what is meant by places ranges from particular locations to large spatial regions. This thesis proposes a series of approaches that altogether enable a mobile robot to evolve its knowledge of topological maps and use them in navigating among places. First, navigating reliably between two locations is considered. A reactive strategy that allows the robot to arrive at the goal location with the desired heading is proposed. Next, exploration of unknown environments is addressed and an approach in which the robot determines the nodes of the map through discovering canonical appearances is presented. As such, the robot can build a topological map of its surroundings autonomously. Following, the integration of this knowledge with the existing knowledge in the robot's map memory is considered. As knowledge accumulates, state-of-the-art approaches face real-time applicability issues. This is addressed by proposing an approach based on hierarchical topological maps. The proposed approach assumes that the robot is capable of topological spatial cognition as presented previously. As such, the hierarchical map is constructed so that the level preceding the terminal nodes corresponds to places - where the concept of a place, is defined as a collection of appearances or locations sharing common perceptual signatures or physical boundaries. Finally, navigation using the hierarchical map is considered and a novel algorithm that enables the robot to generate a plan of the route between any given two nodes in the hierarchical map is developed. The proposed approaches are implemented on a mobile robot and extensive experimental results are reported.