Computationally Efficient Global Localization in Large Spaces
This map is the result of previous work in simultaneous localization and mapping in large, unknown spaces.
The hierarchical atlas consists of a topological graph with feature-based maps associated to the graph edges.
Here, we assume that the robot has the hierarchical atlas for the environment, but does not know hwere it is located on that map.
To achieve localization, the robot first drives to a node and enumerates a sequence of candidate nodes in the graph.
The neighbors of the candidate nodes are noted as the next set of candidates, and the robot proceeds to a neighboring node.
Then, the set of candidates can be narrowed down based on observed properties of the neighbor.
The robot then uses the observed feature-based map associated with the traversed edge to further eliminate candidates.
If multiple candidates remain, this procedure is repeated until the robot is localized.
We have performed experiments in large-scale spaces verifying this approach.
The RGVG of the hierarchical atlas resulting from H-SLAM in Wean Hall on the 6th floor.
Nodes are shown as dark circles and labelled with their corresponding indices.
The thick solid lines represent the abstract edges connecting adjacent nodes.
We define a location configuration for the robot to be the node that it resides at and the edge from which the robot arrived.
The location state for this atlas is a vector of node-edge pairs representing the possible configurations of the robot.
The embedding of the edge maps of the hierarchical atlas in their environment.
Nodes are shown as dark circles with their corresponding indices.
The positions of landmarks for each map are marked with stars.
The matching path represents the sequence of observed nodes and edges.
The search forest represents hypothetical paths, and is used to organize the node and edge comparison tests.
The figure above shows the matching path and abbreviated search forest where the current match node and edge are N(hat)1 and E(hat)0.
The hypothetical path corresponding to Nh is Na→Nh.
The matching path and search forest resulting from an H-SLAM localization experiment in Wean Hall on the 6th floor.
The eliminated candidate nodes for N(hat)1 are crossed out and marked by a letter corresponding to the test which they failed.
(a) The RGVG corresponding to the possibility that N(hat)0 is in fact N1
(b) The RGVG corresponding to the possibility that N(hat)0 is in fact N3
(a) The embedding of F(hat)0 and F1,1 in the environment.
(b) The embedding of F(hat)0 and F2,0 in the environment.
In both figures, the nodes are shown as dark circles and are labelled with their indices.
The landmarks in F(hat)0 are shown as empty circles, and those of F1,1 and F2,0 as crosses.
The sonar sensor and encoder data logged during an H-SLAM localization experiment in Wean Hall on the 6th floor.
resulting updates of location state probability. It is important to note that the location state is of finite size
determined by the number of directional edges in the atlas. With each cycle, the observed data is compared to the
atlas data; the observed edge and node are compared to each edge and node in the atlas only once.
This comparison data is then used throughout the search forest to update the probabilities of hypothetical paths and destinations.
The probabilities are collected back into the location state and the forest is cleared for the next cycle.
Hence the computational complexity of the procedure is bounded by the size of the atlas and is therefore
computationally efficient.
Go back to: H-SLAM page
© Copyright 2002 Sensor Based Planning Lab, Carnegie Mellon University. All Rights Reserved.