## 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 measure5.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