Page 193 - Autonomous Mobile Robots

Landmarks and Triangulation in Navigation 177

(a) D

C
A
O B

(b)
Laser scan
No Mean distance Yes Output circle
<0.01 m? center coordinates

Next scan point Calculate mean distance
of adjacent points from
hypothesis circle center

Calculate hypothesis Calculate number of adjacent
circle center points expected to lie on
circle circumference

FIGURE 4.15 Least squares fitting of circles. (a) Geometric construction illustrating
the least squares method for circle location. (b) Flowchart of the least-squares circle
detection algorithm.

range discontinuity. The subset of laser range points processed is

r 1 r 2 ··· r n
S = (4.36)
θ 1 θ 2 ··· θ n
where r and θ are the polar coordinates of the scan points in the coordinate
system of the robot. The position of the hypothesis circle in polar coordinates is

r n+1 + R

C r
= 2 (4.37)
C θ θ n+1
2
The distance of the ith point from circle circumference is

2
2
d i = C + r − 2C r r i cos(C θ − θ i ) − R (4.38)
r i

© 2006 by Taylor & Francis Group, LLC

FRANKL: “dk6033_c004” — 2006/3/31 — 16:42 — page 177 — #29