Generating random directions

Some sampling-based algorithms require choosing motion directions at random.^5.4 From a configuration $q$, the possible directions of motion can be imagined as being distributed around a sphere. In an $(n+1)$-dimensional C-space, this corresponds to sampling on ${\mathbb{S}}^n$. For example, choosing a direction in ${\mathbb{R}}^2$ amounts to picking an element of ${\mathbb{S}}^1$; this can be parameterized as $\theta \in [0,2 \pi ]{/\sim }$. If $n = 4$, then the previously mentioned trick for $SO(3)$ should be used. If $n=3$ or $n > 4$, then samples can be generated using a slightly more expensive method that exploits spherical symmetries of the multidimensional Gaussian density function [341]. The method is explained for ${\mathbb{R}}^{n+1}$; boundaries and identifications must be taken into account for other spaces. For each of the $n+1$ coordinates, generate a sample $u_i$ from a zero-mean Gaussian distribution with the same variance for each coordinate. Following from the Central Limit Theorem, $u_i$ can be approximately obtained by generating $k$ samples at random over $[-1,1]$ and adding them ($k \geq 12$ is usually sufficient in practice). The vector $(u_1,u_2,\ldots,u_{n+1})$ gives a random direction in ${\mathbb{R}}^{n+1}$ because each $u_i$ was obtained independently, and the level sets of the resulting probability density function are spheres. We did not use uniform random samples for each $u_i$ because this would bias the directions toward the corners of a cube; instead, the Gaussian yields spherical symmetry. The final step is to normalize the vector by taking $u_i / \Vert u\Vert$ for each coordinate.