# Deterministic Sampling-Based Motion Planning: Optimality, Complexity, and Performance

arXiv: https://arxiv.org/abs/1505.00023 · HTML: https://mlsanity.com/paper/1505.00023/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2015.

## Built on by (most cited first, 6 of 6)

- [Refer-it-in-RGBD: A Bottom-up Approach for 3D Visual Grounding in RGBD Images](https://mlsanity.com/paper/2103.07894/) (2021)
- [The Duality of Generative AI and Reinforcement Learning in Robotics: A Review](https://mlsanity.com/paper/2410.16411/) (2024)
- [CODEI: Resource-Efficient Task-Driven Co-Design of Perception and Decision Making for Mobile Robots Applied to Autonomous Vehicles](https://mlsanity.com/paper/2503.10296/) (2025)
- [Neural Low-Discrepancy Sequences](https://mlsanity.com/paper/2510.03745/) (2025)
- [Lazy Probabilistic Roadmaps Revisited](https://mlsanity.com/paper/2209.14471/) (2022)
- [Factorization of Multi-Agent Sampling-Based Motion Planning](https://mlsanity.com/paper/2304.00342/) (2023)

## Abstract (arXiv)

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.