Research Description:

All robots that do not use pre-placed landmarks or GPS must employ a localization algorithm while mapping an unknown space, hence the term Simultaneous Localization and Mapping (SLAM), first coined by Leonard and Durrant-Whyte. This paper takes a topological approach to SLAM and then suggests how it can be used in mapping and covering unknown spaces with a robot experiencing dead-reckoning error. It is our belief that the topological and geometric structure of free space induce a natural hierarchy of symbols and connections among these symbols that represent the free space. At a high level, a topological map, first introduced by Kuipers et al, serves as an example of symbols and connections between them. For Kuipers, the symbols are distinct places which are local maxima of the distances to nearby obstacles and the connections are the graph edges that link distinct places. For indoor office-like environments, junctions and termination points of hallways represent symbols while the hallways themselves are the connections. For the generalized Voronoi diagram, the Voronoi vertices (we call them meet points) are the symbols while the edges form the connections.

The connections of a high level representation can be discretized into a sequence of symbols with their corresponding set of connections. Leonard and Durrant-Whyte's approach to SLAM is an example. Their method uses sensor information to define ``features'' and relations amongst them to direct a robot experiencing positioning error. Using a Kalman Filter approach to determine the ``best'' correlation of features, the robot can maintain an accurate estimate of its position while moving through the environment using the features as low-level symbols that guide the robot from one high-level symbol to the next.

At a low level, the robot's environment can be modeled by a local map such as a fine array of pixels. Thrun et al have been successful in demonstrating their probabilistic approach in museum environments using a grid-map representation. It is our belief that Thrun's main contribution is how to process a map, whether it be topological or a grid, but not the map itself. This paper reduces the SLAM problem to a graph matching problem at the topological scale. The graph matching is not the contribution; using topological information to localize is. We apply this topological method to mapping and coverage of unknown spaces.

Howie Choset
Urcan Umut Acar