Page 356 - Autonomous Mobile Robots

346 Autonomous Mobile Robots

. . .
E 1
F 2 ∗
F 1 F n
. . .
E 2
∗
F 1 F 2 F n
. . .

. . .
E m F n ∗
F 1 F 2
FIGURE 9.2 Interpretation tree of measurements E 1 , ... , E m in terms of map features
F 1 , ... , F n .

9.3 DATA ASSOCIATION IN SLAM
Assume that a new set of m measurements z ={z 1 , ... , z m } of the environ-
ment features {E 1 , ... , E m } have been obtained by a sensor mounted on the
vehicle. As mentioned in Section 9.2, the goal of data association is to generate
a hypothesis H =[j 1 j 2 ··· j m ] associating each measurement E i with its
(j i = 0 indicating that z i does not correspond
corresponding map feature F j i
to any map feature). The space of measurement-feature correspondences can
be represented as an interpretation tree of m levels [30] (see Figure 9.2); each
node at level i, called an i-interpretation, provides an interpretation for the first
i measurements. Each node has n + 1 branches, corresponding to each of the
alternative interpretations for measurement E i , including the possibility that
the measurement be spurious and allowing map feature repetitions in the same
hypothesis. Data association algorithms must select in some way one of the
m
(n+1) m-interpretations as the correct hypothesis, carrying out validations to
determine the compatibility between sensor measurements and map features.

9.3.1 Individual Compatibility Nearest Neighbor
The simplest criterion to decide a pairing for a given measurement is the nearest
neighbor (NN), which consists in choosing among the features that satisfy IC of
Equation (9.9), the one with the smallest Mahalanobis distance. A popular data
association algorithm, the Individual Compatibility Nearest Neighbor (ICNN,
Algorithm 9.2), is based on this idea. It is frequently used given its conceptual
simplicity and computational efficiency: it performs m · n compatibility tests,
making it linear with the size of the map.

© 2006 by Taylor & Francis Group, LLC

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