5.2.2 Random Sampling

Now imagine moving beyond $[0,1]$ and generating a dense sample sequence for any bounded C-space, ${\cal C}\subseteq {\mathbb{R}}^m$. In this section the goal is to generate uniform random samples. This means that the probability density function $p(q)$ over ${\cal C}$ is uniform. Wherever relevant, it also will mean that the probability density is also consistent with the Haar measure. We will not allow any artificial bias to be introduced by selecting a poor parameterization. For example, picking uniform random Euler angles does not lead to uniform random samples over $SO(3)$. However, picking uniform random unit quaternions works perfectly because quaternions use the same parameterization as the Haar measure; both choose points on ${\mathbb{S}}^3$.

Random sampling is the easiest of all sampling methods to apply to C-spaces. One of the main reasons is that C-spaces are formed from Cartesian products, and independent random samples extend easily across these products. If $X = X_1 \times X_2$, and uniform random samples $x_1$ and $x_2$ are taken from $X_1$ and $X_2$, respectively, then $(x_1,x_2)$ is a uniform random sample for $X$. This is very convenient in implementations. For example, suppose the motion planning problem involves $15$ robots that each translate for any $(x_t,y_t) \in [0,1]^2$; this yields ${\cal C}= [0,1]^{30}$. In this case, $30$ points can be chosen uniformly at random from $[0,1]$ and combined into a $30$-dimensional vector. Samples generated this way are uniformly randomly distributed over ${\cal C}$. Combining samples over Cartesian products is much more difficult for nonrandom (deterministic) methods, which are presented in Sections 5.2.3 and 5.2.4.