##

5.1.4 Using the Correct Measure

Since many metrics and measures are possible, it may sometimes seem
that there is no ``correct'' choice. This can be frustrating because
the performance of sampling-based planning algorithms can depend
strongly on these. Conveniently, there is a natural measure, called
the Haar measure, for some transformation groups, including .
Good metrics also follow from the Haar measure, but unfortunately,
there are still arbitrary alternatives.

The basic requirement is that the measure does not vary when the sets
are transformed using the group elements. More formally, let
represent a matrix group with real-valued entries, and let
denote a measure on . If for any measurable subset
, and any element ,
, then
is called the *Haar measure*^{5.2} for . The notation represents the
set of all matrices obtained by the product , for any .
Similarly, represents all products of the form .

**Example 5..13** (Haar Measure for

)
The Haar measure for

can be obtained by parameterizing the
rotations as

with

0 and

identified, and letting

be the Lebesgue measure on the unit interval. To see the
invariance property, consider the interval

, which produces
a set

of rotation matrices. This corresponds to the
set of all rotations from

to

. The
measure yields

. Now consider multiplying every matrix

by a rotation matrix,

, to yield

. Suppose

is the rotation matrix for

. The set

is the
set of all rotation matrices from

up to

. The measure

remains unchanged. Invariance
for

may be checked similarly. The transformation

translates
the intervals in

. Since the measure is based on
interval lengths, it is invariant with respect to translation. Note
that

can be multiplied by a fixed constant (such as

)
without affecting the invariance property.

An invariant metric can be defined from the Haar measure on .
For any points
, let
, in
which is the shortest length (smallest measure) interval
that contains and as endpoints. This metric was already
given in Example 5.2.

To obtain examples that are not the Haar measure, let represent
probability mass over and define any nonuniform probability
density function (the uniform density yields the Haar measure). Any
shifting of intervals will change the probability mass, resulting in a
different measure.

Failing to use the Haar measure weights some parts of more
heavily than others. Sometimes imposing a bias may be desirable, but
it is at least as important to know how to eliminate bias. These
ideas may appear obvious, but in the case of and many other
groups it is more challenging to eliminate this bias and obtain the
Haar measure.

**Example 5..14** (Haar Measure for

)
For

it turns out once again that quaternions come to the
rescue. If unit quaternions are used, recall that

becomes
parameterized in terms of

, but opposite points are identified.
It can be shown that the surface area on

is the Haar measure.
(Since

is a 3D manifold, it may more appropriately be
considered as a surface ``volume.'') It will be seen in Section

5.2.2 that uniform random sampling over

must be
done with a uniform probability density over

. This corresponds
exactly to the Haar measure. If instead

is parameterized
with Euler angles, the Haar measure will not be obtained. An
unintentional bias will be introduced; some rotations in

will
have more weight than others for no particularly good reason.

Steven M LaValle
2012-04-20