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, , , and , which are
chosen by the user. The first two, and , must be relatively
prime, meaning that
. The third parameter, , must
be chosen to satisfy
. Using modular arithmetic, a
sequence can be generated as

(5.16) |

by starting with some arbitrary seed . Pseudorandom numbers in are generated by the sequence

(5.17) |

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

Steven M LaValle 2012-04-20