Image-based navigation through large-scale environments

Abstract

To be truly autonomous, a robot must be able to infer its location from available landmarks. To navigate to locations whose landmarks are out of view, a robot must maintain some sort of map of the large-scale layout of landmarks and locations. Since landmarks can change, a map can become outdated; this work develops a principled approach to maintaining a reliable map in the face of uncertainty and change. In this work, snapshots--"raw," panoramic views of the world--represent locations. A correlation-based matching algorithm finds the correspondences between the robot's current panoramic view and the snapshot for a target location. Qualitative homing algorithms use these correspondences to bring the robot to the target location. The behavior of these algorithms in the presence of mismatched landmarks and bearing uncertainty is analyzed and proved to be optimal. Routes are represented by sequences of target locations; any target location along the route may be represented by several snapshots, taken at different times. Route learning algorithms determine how far apart to place target locations and whether to update a target location by storing another snapshot. Maps are represented as sets of intersecting routes. Map learning algorithms hypothesize where routes are likely to intersect; reliable maps can be constructed by testing the hypothesized route junctions sufficiently. The time and storage complexities of the route and map learning algorithms are analyzed. An image-understanding front-end was implemented. Experiments were carried out with a robot in typical indoor environments, including a furnished room, a lobby and a hallway. The experiments allowed an estimate of the practical storage and time complexity of the algorithms, showing them to be effective for a practical robot.