Page 364 - Autonomous Mobile Robots

354 Autonomous Mobile Robots

ALGORITHM 9.4
Relocation using RANSAC
Relocation_RS (H)
P fail = 0.05,p=3, P g = 0.5
Best = []
i =0
repeat
ˆ z = random_permutation(ˆ z)
RS([], 1)
P g = max(P g , pairings(Best) / m)
p

t = log P fail / log 1 − P g
i=i+1
until i ≥ t
return Best
procedure RS (H):
{H : current hypothesis}
{i : observation to be matched}
if i > m then
if pairings(H) > pairings(Best) then
Best = H
end if
else if pairings(H) == 3 then
B
x = estimate_location_(H)
R
if joint_compatibility(H) then
JCBB(H, i) { hypothesis verification}
end if
else {branch and bound without star node}
for j=1to n do
if unary(i, j) ∧ binary(i, j, H) then
RS([H j],i+1)
end if
end for
end if

9.3.4 Locality

As explained in Section 9.3.3, the main problem of the interpretation tree
approach is the exponential number of possible hypotheses (tree leaves):
m
N h = (n + 1) . The use of geometric constraints and branch and bound search

© 2006 by Taylor & Francis Group, LLC

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