Page 363 - Autonomous Mobile Robots

Map Building and SLAM Algorithms 353

a compatibility graph whose nodes are unary compatible matchings and whose
arcs represent pairs of binary compatible matchings. Finding the largest hypo-
thesis consistent with unary and binary constraints is equivalent to finding the
maximum clique in the compatibility graph (see Reference 30 for a discussion
and references). This idea has been applied recently by Bailey et al. [34] to the
problem of robot relocation with an a priori map.
Branch and bound algorithms are forced to traverse the whole correspond-
ence space until a good bound is found. In the SLAM relocation problem, when
the vehicle is not within the mapped area, a good bound is never found. Since the
correspondence space is exponential with the number of measurements, in this
worst case the execution times of branch and bound algorithms are very long.
To overcome this limitation, the data association process can be done using
random sampling (RS) instead of by a full traversal of the interpretation tree.
The RS algorithm that we use (Algorithm 9.4) is an adaptation of the RANSAC
algorithm [35] for the relocation problem. The fundamental idea is to ran-
domly select p out of the m measurements to try to generate vehicle localization
hypotheses using geometric constraints, and verify them with all m measure-
ments using JC. If P g is the probability that a randomly selected measurement
corresponds to a mapped feature (not spurious) and P fail is the acceptable prob-
ability of not finding a good solution when it exists, the required number of
tries is:

log P fail
t = p (9.21)
log(1 − P g )
Hypothesis generation–verification schemes such as this one perform better
because feature location is a tighter consistency criterion than geometric con-
straints, and thus branch pruning is more effective. The potential drawback of
this approach is that hypothesis verification is location dependent, and thus the
constraints to be used for validation cannot be precomputed. To limit the amount
of location dependent constraints to apply, verification can take place when a
hypothesis contains at least three consistent pairings. Choosing P fail = 0.05
and considering a priori that only half of the measurements are present in the
map P g = 0.5, the maximum number of tries is t = 23. If you can con-
sider that at least 90% of the measurements correspond to a map feature, the
number of required tries is only three. The RS algorithm randomly permutes
the measurements and performs hypothesis generation considering the first
three measurements not spurious (without star branch). The number of tries is
recalculated to adapt to the current best hypothesis, so that no unnecessary tries
are carried out [36].
Notice that the maximum number of tries does not depend on the number
of measurements. Experiments show that this fact is crucial in reducing the
computational complexity of the RS algorithm.

© 2006 by Taylor & Francis Group, LLC

FRANKL: “dk6033_c009” — 2006/3/31 — 16:43 — page 353 — #23