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) |
(5.17) |
Steven M LaValle 2020-08-14