Pseudorandom number generation

Although there are advantages to uniform random sampling, there are also several disadvantages. This motivates the consideration of deterministic alternatives. Since there are trade-offs, it is important to understand how to use both kinds of sampling in motion planning. One of the first issues is that computer-generated numbers are not random.^5.5 A pseudorandom number generator is usually employed, which is a deterministic method that simulates the behavior of randomness. Since the samples are not truly random, the advantage of extending the samples over Cartesian products does not necessarily hold. Sometimes problems are caused by unforeseen deterministic dependencies. One of the best pseudorandom number generators for avoiding such troubles is the Mersenne twister [684], for which implementations can be found on the Internet.

To help see the general difficulties, the classical linear congruential pseudorandom number generator is briefly explained [619,738]. The method uses three integer parameters, $M$, $a$, and $c$, which are chosen by the user. The first two, $M$ and $a$, must be relatively prime, meaning that $\gcd(M,a) = 1$. The third parameter, $c$, must be chosen to satisfy $0 \leq c < M$. Using modular arithmetic, a sequence can be generated as

$$y_{i+1} = a y_i + c \mod M ,$$ (5.16)

by starting with some arbitrary seed $1 \leq y_0 \leq M$. Pseudorandom numbers in $[0,1]$ are generated by the sequence

$$x_i = y_i/M .$$ (5.17)

The sequence is periodic; therefore, $M$ is typically very large (e.g., $M = 2^{31}-1$). Due to periodicity, there are potential problems of regularity appearing in the samples, especially when applied across a Cartesian product to generate points in ${\mathbb{R}}^n$. Particular values must be chosen for the parameters, and statistical tests are used to evaluate the samples either experimentally or theoretically [738].