Page 365 - Autonomous Mobile Robots

Map Building and SLAM Algorithms 355

dramatically reduce the number of nodes explored, by cutting down entire
branches of the tree. However, Grimson [30] has shown that in the general case
where spurious measurements can arise, the amount of search needed to find
the best interpretation is still exponential. In these conditions, the interpretation
tree approach seems impracticable except for very small maps.
To overcome this difficulty we introduce the concept of locality: given that
the set of measurements has been obtained from a unique vehicle location (or
from a set of nearby locations), it is sufficient to try to find matchings with local
sets of features in the map. Given a map feature F j , we define its locality L(F j )
as the set of map features that are in the vicinity to it, such that they can be seen
from the same vehicle location. For a given mapping problem, the maximum
cardinality of the locality sets will be a constant c that depends on the sensor
range and the maximum density of features in the environment.
During the interpretation tree search, once a matching has been established
with a map feature, the search can be restricted to its locality set. For the first
measurement, there are n possible feature matchings. Since there are at most c
features covisible with the first one, for the remaining m−1 measurements there
are only c possible matches, giving a maximum of n(c + 1) m−1 hypotheses.
If the first measurement is not matched, a similar analysis can be done for the
second tree level. Thus, the total number of hypotheses N h will be:
m
(c + 1) − 1
m−1
N h ≤ n(c + 1) + ··· + n + 1 = n + 1 (9.22)
c
This implies that, using locality, the complexity of searching the interpretation
tree will be linear with the size of the map.
There are several ways of implementing locality:

1. SLAM can be implemented by building sequences of independent
local maps [10]. If the local maps are stored, the search for matchings
can be performed in time linear with the number of local maps. In
this case, the locality of a feature is the set of features belonging
to the same local map. A drawback of this technique is that global
localization may fail around the borders between two local maps.
2. Alternatively, the locality of a feature can be computed as the set of
map features within a distance less than the maximum sensor range.
There are two drawbacks in this approach: first, this will require
2
O(n ) distance computations, and second, in some cases features
that are close cannot be seen simultaneously (e.g., because they are
in different rooms), and thus should not be considered local.
3. The locality of a feature can be defined as the set of features that have
been seen simultaneously with it at least once. We choose this last
alternative, because it does not suffer from the limitations of the first

© 2006 by Taylor & Francis Group, LLC

FRANKL: “dk6033_c009” — 2006/3/31 — 16:43 — page 355 — #25