Low-discrepancy sampling methods

Due to the fundamental importance of numerical integration and the intricate link between discrepancy and integration error, most sampling literature has led to low-discrepancy sequences and point sets [738,893,937]. Although motion planning is quite different from integration, it is worth evaluating these carefully constructed and well-analyzed samples. Their potential use in motion planning is no less reasonable than using pseudorandom sequences, which were also designed with a different intention in mind (satisfying statistical tests of randomness).

Low-discrepancy sampling methods can be divided into three categories: 1) Halton/Hammersley sampling; 2) (t,s)-sequences and (t,m,s)-nets; and 3) lattices. The first category represents one of the earliest methods, and is based on extending the van der Corput sequence. The Halton sequence is an $n$-dimensional generalization of the van der Corput sequence, but instead of using binary representations, a different basis is used for each coordinate [430]. The result is a reasonable deterministic replacement for random samples in many applications. The resulting discrepancy (and dispersion) is lower than that for random samples (with high probability). Figure 5.8a shows the first $196$ Halton points in ${\mathbb{R}}^2$.

Choose $n$ relatively prime integers $p_1, p_2, \ldots, p_{n}$ (usually the first $n$ primes, $p_1=2$, $p_2=3$, $\ldots$, are chosen). To construct the $i$th sample, consider the base-$p$ representation for $i$, which takes the form $i= a_0 + p a_1 + p^2 a_2 + p^3 a_3 + \ldots$. The following point in $[0,1]$ is obtained by reversing the order of the bits and moving the decimal point (as was done in Figure 5.2):

$$r(i,p) = \frac{a_0}{p} +\frac{a_1}{p^2} +\frac{a_2}{p^3} +\frac{a_3}{p^4} + \cdots .$$ (5.24)

For $p = 2$, this yields the $i$th point in the van der Corput sequence. Starting from $i = 0$, the $i$th sample in the Halton sequence is

$$\big( r(i,p_1), r(i,p_2), \ldots, r(i,p_n) \big) .$$ (5.25)

Suppose instead that $k$, the required number of points, is known. In this case, a better distribution of samples can be obtained. The Hammersley point set [431] is an adaptation of the Halton sequence. Using only $d-1$ distinct primes and starting at $i = 0$, the $i$th sample in a Hammersley point set with $k$ elements is

$$\big( i/k, r(i,p_1), \ldots, r(i,p_{n-1}) \big) .$$ (5.26)

Figure 5.8b shows the Hammersley set for $n=2$ and $k=196$.

The construction of Halton/Hammersley samples is simple and efficient, which has led to widespread application. They both achieve asymptotically optimal discrepancy; however, the constant in their asymptotic analysis increases more than exponentially with dimension [738]. The constant for the dispersion also increases exponentially, which is much worse than for the methods of Section 5.2.3.

Figure 5.8: The Halton and Hammersley points are easy to construct and provide a nice alternative to random sampling that achieves more regularity. Compare the Voronoi regions to those in Figure 5.3. Beware that although these sequences produce asymptotically optimal discrepancy, their performance degrades substantially in higher dimensions (e.g., beyond 10).

Improved constants are obtained for sequences and finite points by using (t,s)-sequences, and (t,m,s)-nets, respectively [738]. The key idea is to enforce zero discrepancy over particular subsets of ${\mathcal R}$ known as canonical rectangles, and all remaining ranges in ${\mathcal R}$ will contribute small amounts to discrepancy. The most famous and widely used (t,s)-sequences are Sobol' and Faure (see [738]). The Niederreiter-Xing (t,s)-sequence has the best-known asymptotic constant, $(a/n)^n$, in which $a$ is a small positive constant [739].

The third category is lattices, which can be considered as a generalization of grids that allows nonorthogonal axes [682,893,959]. As an example, consider Figure 5.5b, which shows $196$ lattice points generated by the following technique. Let $\alpha$ be a positive irrational number. For a fixed $k$, generate the $i$th point according to $(i/k,\{i \alpha\})$, in which $\{\cdot\}$ denotes the fractional part of the real value (modulo-one arithmetic). In Figure 5.5b, $\alpha = (\protect\sqrt 5 + 1)/2$, the golden ratio. This procedure can be generalized to $n$ dimensions by picking $n-1$ distinct irrational numbers. A technique for choosing the $\alpha$ parameters by using the roots of irreducible polynomials is discussed in [682]. The $i$th sample in the lattice is

$$\left(\frac{i}{k}, \{i \alpha_1\}, \ldots, \{i \alpha_{n-1}\} \right).$$ (5.27)

Recent analysis shows that some lattice sets achieve asymptotic discrepancy that is very close to that of the best-known nonlattice sample sets [445,938]. Thus, restricting the points to lie on a lattice seems to entail little or no loss in performance, but has the added benefit of a regular neighborhood structure that is useful for path planning. Historically, lattices have required the specification of $k$ in advance; however, there has been increasing interest in extensible lattices, which are infinite sequences [446,938].