Page 358 - Autonomous Mobile Robots

348 Autonomous Mobile Robots

ALGORITHM 9.3
JCBB
Continuous_JCBB (E 1···m , F 1···n )
Best = []
JCBB ([],1)
return Best

procedure JCBB (H, i): {find pairings for observationE i }
if i > m then {leaf node?}
if pairings(H)> pairings(Best) then
Best ← H
end if
else
for j = 1to n do
if individual_compatibility(i, j) and then joint_compatibility(H, i, j)
then
JCBB([H j],i+1){pairing (E i , F j ) accepted}
end if
end for
if pairings(H) + m − i > pairings(Best) then {can do better?}
JCBB([H 0], i + 1) {star node, E i not paired}
end if
end if

pairing is jointly compatible with all the other pairings of a given hypothesis
decreases as the number of pairings in the hypothesis increases. The JC test can
be used to establish the consistency of a hypothesis H m , using Equation (9.13).
The JC test is the core of the joint compatibility branch and bound data
association algorithm (JCBB, Algorithm 9.3), that traverses the interpreta-
tion tree in search for the hypothesis that includes the largest number of
jointly compatible pairings. The quality of a node at level i, corresponding
to a hypothesis H i , is defined as the number of non-null pairings that can
be established from the node. In this way, nodes with quality lower than
the best available hypothesis are not explored, bounding the search [30]. The
NN rule using the Mahalanobis distance D 2 is used as heuristic for branch-
H i
ing, so that the nodes corresponding to hypotheses with a higher degree
increase with the
of JC are explored first. The size of both h H i and S H i
size of hypothesis H i . This makes this test potentially expensive to apply
(see References 31 and 32 for techniques for the efficient computation of
the Mahalanobis distance).

© 2006 by Taylor & Francis Group, LLC

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