TOPOLOGICAL DIRECTION-GIVING AND VISUAL NAVIGATION IN LARGE ENVIRONMENTS

In this paper, we propose and investigate a new model for robot naviga tion in large unstructured environments. Current models, which depend on metric information, have to deal with inherent mechanical and senso ry errors. Instead we supply the navigator with qualitative informatio n. Our model consists of two parts, a map-maker and a navigator. Given a source and a goal, the map-maker derives a navigational path based on the topological relationships between landmarks. A navigational pat h is generated as a combination of ''parkway'' and ''trajectory'' path s, both of which are abstractions of the real world into topological d ata structures. Traversing within a parkway enables the navigator to f ollow landmarks that are continuously visible. Traversing on a traject ory enables the navigator to move reliably into featureless space, bas ed on local headings formed by visible landmarks that are robust to po sitional and orientational errors. Reliability measures of parkway and trajectory traversals are defined by appropriate error models that ac count for the sensory errors of the navigator, the population of neigh boring objects, and the rotational and translational errors of the nav igator. The optimal path is further abstracted into a ''custom map'', which consists of a list of symbolic directional instructions, the voc abulary of which is defined by our environmental description language. Based on the custom map generated by the map-maker, the navigating ro bot looks for events that are characterized by spatial properties of t he environment. The map-maker and the navigator are implemented using two cameras, an IBM 7575 robot arm, and a PIPE (Pipelined Image Proces sing Engine.)