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.

Steven M LaValle 2012-04-20