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.

Steven M LaValle 2012-04-20