Qualitative environmental navigation: theory and practice

Abstract

In this thesis we propose and investigate a new model for robot navigation in large unstructured environments. Current models which depend on metric information contain inherent mechanical and sensory uncertainties. Instead we supply the navigator with qualitative information. Our model consists of two parts, the map-maker and the navigator. Given a source and a goal, the map-maker derives a navigational path based on the topological relationships between landmarks. A navigational path is generated as a combination of "parkway" and "trajectory" paths, both of which are abstractions of the real world into topological data structures. Traversing within a parkway enables the navigator to follow visible landmarks. Traversing on a trajectory enables the navigator to move reliably into a homogeneous space, based on shapes formed by visible landmarks that are robust to positional and orientational errors. Reliability measures of parkway and trajectory traversals are defined by appropriate error models that account for the sensory errors of the navigator, the motor errors of the navigator, and the population of neighboring objects. Error detection and error recovery methods are also encoded into the generated path. The optimal path is further abstracted into a "custom map," which consists of a list of verbal directional instructions, the vocabulary of which is defined by our environmental description language. Based on the custom map generated by the map-maker, the navigating robot looks for events that are characterized by spatial properties of the environment. The map-maker and the navigator are implemented using two cameras, an IBM 7575 robot arm and PIPE (Pipelined Image Processing Engine.) Various e...