Page 171 - Introduction to Autonomous Mobile Robots

Chapter 4
156
line distance, but instead the distance parallel to the y-axis between the point and the line.
A good illustration of the variety of optimization criteria is available in [17] where several
algorithms for fitting circles and ellipses are presented which minimize algebraic and geo-
metric distances.
For each specific ρ θ,( i i ) , we can write the orthogonal distance between ρ θ,( i i ) and
d
i
the line as
–
ρ cos ( θ – α) r = d . (4.68)
i i i
If we consider each measurement to be equally uncertain, we can sum the square of all
errors together, for all measurement points, to quantify an overall fit between the line and
all of the measurements:

∑ 2 ∑ ( ( r) 2
S = d i = ρ cos θ – α) – (4.69)
i
i
i i
Our goal is to minimize when selecting the line parameters α r,( ) . We can do so by
S
solving the nonlinear equation system

∂S ∂S
∂ α = 0 r ∂ = . 0 (4.70)

The above formalism is considered an unweighted least-squares solution because no
distinction is made from among the measurements. In reality, each sensor measurement
may have its own, unique uncertainty based on the geometry of the robot and environment
when the measurement was recorded. For example, we know with regard to vision-based
stereo ranging that uncertainty and, therefore, variance increases as a square of the distance
between the robot and the object. To make use of the variance σ 2 i that models the uncer-
tainty regarding distance ρ of a particular sensor measurement, we compute an individual
i
weight w for each measurement using the formula
i

⁄
w = 1 σ 2 i 2 . (4.71)
i
Then, equation (4.69) becomes

2. The issue of determining an adequate weight when σ i is given (and perhaps some additional
information) is complex in general and beyond the scope of this text. See [9] for a careful treatment.