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 $SO(N)$. 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 $G$ represent a matrix group with real-valued entries, and let $\mu$ denote a measure on $G$. If for any measurable subset $A \subseteq G$, and any element $g \in G$, $\mu(A) = \mu(gA) = \mu(Ag)$, then $\mu$ is called the Haar measure^5.2 for $G$. The notation $gA$ represents the set of all matrices obtained by the product $ga$, for any $a \in A$. Similarly, $Ag$ represents all products of the form $ag$.

Example 5..13 (Haar Measure for $SO(2)$)   The Haar measure for $SO(2)$ can be obtained by parameterizing the rotations as $[0,1]{/\sim}$ with 0 and $1$ identified, and letting $\mu$ be the Lebesgue measure on the unit interval. To see the invariance property, consider the interval $[1/4,1/2]$, which produces a set $A \subset SO(2)$ of rotation matrices. This corresponds to the set of all rotations from $\theta = \pi/2$ to $\theta = \pi$. The measure yields $\mu(A) = 1/4$. Now consider multiplying every matrix $a \in A$ by a rotation matrix, $g \in SO(2)$, to yield $Ag$. Suppose $g$ is the rotation matrix for $\theta = \pi$. The set $Ag$ is the set of all rotation matrices from $\theta = 3\pi/2$ up to $\theta = 2 \pi = 0$. The measure $\mu(Ag) = 1/4$ remains unchanged. Invariance for $gA$ may be checked similarly. The transformation $g$ translates the intervals in $[0,1]{/\sim}$. Since the measure is based on interval lengths, it is invariant with respect to translation. Note that $\mu$ can be multiplied by a fixed constant (such as $2 \pi$) without affecting the invariance property.

An invariant metric can be defined from the Haar measure on $SO(2)$. For any points $x_1,x_2 \in [0,1]$, let $\rho = \mu([x_1,x_2])$, in which $[x_1,x_2]$ is the shortest length (smallest measure) interval that contains $x_1$ and $x_2$ as endpoints. This metric was already given in Example 5.2.

To obtain examples that are not the Haar measure, let $\mu$ represent probability mass over $[0,1]$ 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 $SO(2)$ 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 $SO(3)$ and many other groups it is more challenging to eliminate this bias and obtain the Haar measure. $\blacksquare$

Example 5..14 (Haar Measure for $SO(3)$)   For $SO(3)$ it turns out once again that quaternions come to the rescue. If unit quaternions are used, recall that $SO(3)$ becomes parameterized in terms of ${\mathbb{S}}^3$, but opposite points are identified. It can be shown that the surface area on ${\mathbb{S}}^3$ is the Haar measure. (Since ${\mathbb{S}}^3$ 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 $SO(3)$ must be done with a uniform probability density over ${\mathbb{S}}^3$. This corresponds exactly to the Haar measure. If instead $SO(3)$ is parameterized with Euler angles, the Haar measure will not be obtained. An unintentional bias will be introduced; some rotations in $SO(3)$ will have more weight than others for no particularly good reason. $\blacksquare$