Probabilistic sampling-based algorithms, such as the probabilistic roadmap
(PRM) and the rapidly-exploring random tree (RRT) algorithms, represent one of
the most successful approaches to robotic motion planning, due to their strong
theoretical properties (in terms of probabilistic completeness or even
asymptotic optimality) and remarkable practical performance. Such algorithms
are probabilistic in that they compute a path by connecting independently and
identically distributed random points in the configuration space. Their
randomization aspect, however, makes several tasks challenging, including
certification for safety-critical applications and use of offline computation
to improve real-time execution. Hence, an important open question is whether
similar (or better) theoretical guarantees and practical performance could be
obtained by considering deterministic, as opposed to random sampling sequences.
The objective of this paper is to provide a rigorous answer to this question.
Specifically, we first show that PRM, for a certain selection of tuning
parameters and deterministic low-dispersion sampling sequences, is
deterministically asymptotically optimal. Second, we characterize the
convergence rate, and we find that the factor of sub-optimality can be very
explicitly upper-bounded in terms of the l2-dispersion of the sampling sequence
and the connection radius of PRM. Third, we show that an asymptotically optimal
version of PRM exists with computational and space complexity arbitrarily close
to O(n) (the theoretical lower bound), where n is the number of points in the
sequence. This is in stark contrast to the O(n logn) complexity results for
existing asymptotically-optimal probabilistic planners. Finally, through
numerical experiments, we show that planning with deterministic low-dispersion
sampling generally provides superior performance in terms of path cost and
success rate.

该研究论文探究了将确定性的低离散度采样序列应用于机器人运动规划中的概率采样算法，并证明了其渐近最优性，并通过数值实验验证了其在路径成本和成功率方面表现出更高的性能。