Pith. sign in

REVIEW 4 major objections 5 minor 52 references

Effective Sampling for Robot Motion Planning Through the Lens of Lattices

T0 review · 4 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A*_d lattice sampling gives PRM-style planners finite-time guarantees and at least an order-of-magnitude speedup.

desk verdict Sound lattice-based finite-time sample sets with a useful new practical metric, but the abstract overstates the speedup; deserves peer review after a qualified rewrite. read the letter →

arxiv 2502.04908 v2 pith:HRF5WNKJ submitted 2025-02-07 cs.RO cs.CGcs.DM

Itai Panasoff , Kiril Solovey This is my paper · ORCID
classification cs.ROcs.CGcs.DM
keywords motionplanninglatticesamplingdeterministic(δε)-completenesscoveringradiusA*_dprobabilisticroadmapscollision-checkcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Sampling-based motion planners usually get guarantees only as the number of samples grows to infinity. This paper shows how to turn deterministic lattice sample sets into a finite-time guarantee: for chosen clearance $\delta$ and stretch factor $\varepsilon$, every $\delta$-clear problem is solved with a path no longer than $(1+\varepsilon)$ times the optimal $\delta$-clear path, and if no path is found then no $\delta$-clear solution exists. The paper proves that a rescaled copy of the $A^*_d$ lattice, the best known geometric covering in dimensions up to 21, yields the smallest sample and collision-check complexity among the lattice sets it considers. The reported experiments on multi-robot and 7-degree-of-freedom manipulator problems show at least an order-of-magnitude speedup over staggered-grid sampling and large gains over uniform random sampling in running time, success rate, and path length. If correct, this makes certified finite-time planning practical in more dimensions than earlier constructions allowed.

What carries the argument

The load-bearing object is the $(\delta,\varepsilon)$-complete sample set $X^{\delta,\varepsilon}_\Lambda$, obtained from a lattice $\Lambda$ by rescaling so its covering radius becomes $\beta^* = \delta\varepsilon/\sqrt{1+\varepsilon^2}$; this turns a geometric covering into a guarantee that the roadmap graph contains a path of length at most $(1+\varepsilon)\,\mathrm{OPT}_\delta$ with connection radius $r^* = 2\delta(1+\varepsilon)/\sqrt{1+\varepsilon^2}$. For the $A^*_d$ lattice, the machinery includes an isometric embedding $T$ from $\mathbb{R}^{d+1}$ into $\mathbb{R}^d$ that preserves the covering radius, rational-ellipsoid lattice-point bounds to estimate sample complexity, and an annulus partition that improves the collision-check-complexity bound by the factor $\zeta = 1 - (\xi^{d+2}-\xi)/(d\xi-(d+1))$ with $\xi=(d/(d+1))^d$.

What would settle it

Run the implicit A* planner with $X^{\delta,\varepsilon}_{A^*_d}$ on a $\delta$-clear problem whose full PRM graph contains a $(1+\varepsilon)$-optimal path; if the planner returns no path or a strictly longer one, then the implicit search does not preserve the guarantee.

Watch

Extended reading notes

Core claim

The paper's central claim is that the covering radius of a lattice controls the quality of the sampling set: rescaling any lattice by the factor $\beta^*/f_\Lambda$ turns it into a $\beta^*$-cover, and Lemma 1 then gives a $(\delta,\varepsilon)$-complete PRM graph. Applying this to $A^*_d$, after an isometric embedding into $\mathbb{R}^d$ that preserves its covering radius, yields the sample set $X^{\delta,\varepsilon}_{A^*_d}$, which the paper proves has the smallest sample complexity among $\mathbb{Z}^d$, $D^*_d$, and $A^*_d$ and enjoys a tight collision-check bound. Theorems 2 and 3 quantify these costs, and the experimental section reports that the $A^*_d$ set reduces running time by at least an order of magnitude compared with the staggered grid and often by two to three orders compared with uniform random sampling, while keeping success rates high in the tested scenarios.

Load-bearing premise

The paper assumes, without proof, that the implicit A* search inherits the $(\delta,\varepsilon)$-completeness guarantee of the full roadmap graph, and that the scenario-by-scenario tuning of $\delta$ does not favor the lattice sampler.

Editorial extensions

If this is right

  • Any PRM-style planner that builds its roadmap on $X^{\delta,\varepsilon}_{A^*_d}$ with the radius $r^*$ inherits a finite-time guarantee: a returned path is within $(1+\varepsilon)$ of the $\delta$-clear optimum, and failure to find a path certifies that no $\delta$-clear solution exists.
  • Because sample complexity grows with the $d$-th power of the covering radius, the lattice with the smallest covering radius dominates in high dimensions; the paper reports that $A^*_d$ is the best known covering for dimensions up to 21.
  • Lattice regularity lets a planner compute any vertex's neighbor set as a translation of the origin's neighbor set, removing the nearest-neighbor data structure from roadmap construction for deterministic samples.
  • In the reported experiments, $A^*_d$ sampling is at least an order of magnitude faster than staggered-grid sampling, and often two to three orders of magnitude faster than uniform random sampling, with higher success rates and comparable or shorter paths.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper: the speedups observed with the implicit search combine a proven guarantee on the full roadmap graph with an unproved inheritance by the search; replacing that search with one that provably preserves the roadmap's shortest paths would close that gap.
  • Beyond the paper: the paper's own parameter experiments show solutions appearing for combinations of $\delta$ and $\varepsilon$ where its sufficient condition predicts none, suggesting the $\beta^*$-cover relation is loose and that tighter bounds could cut the required sample count substantially.
  • Beyond the paper: instrumenting a planner to count actual collision checks rather than using the analytic proxy could reveal how much of $A^*_d$'s advantage comes from fewer vertex expansions versus fewer edge checks, which would refine the collision-check-complexity model.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper develops deterministic lattice-based sample sets for sampling-based motion planning that carry finite-time (δ,ε)-completeness guarantees. Starting from known covering radii of the lattices Z^d, D*_d, and A*_d, the authors rescale each lattice so that it becomes a β*-cover and invoke the completeness–cover lemma of Tsao et al. to obtain (δ,ε)-complete sample sets. The A*_d lattice, which is the best-known covering in low dimensions, is embedded into R^d by an explicit isometry, and the paper derives asymptotic expressions for sample complexity and a constant-factor improvement for a new collision-check complexity measure. The method is evaluated in multi-robot and 7-DOF manipulator scenarios through an implicit A* planner (iA*) that exploits the translational regularity of lattices, with reported speedups of orders of magnitude over rectangular grids, staggered grids, and uniform random sampling.

Significance. If the claims hold, this is a useful practical step for sampling-based motion planning: it supplies deterministic sample sets with finite-time worst-case path-quality guarantees, and the use of A*_d is a natural and well-motivated contribution over earlier staggered-grid constructions. The mathematical core is credible and self-contained: Theorem 1 correctly combines known covering radii with Lemma 1, and the derivation of the A*_d embedding in the appendix is explicit. The sample-complexity and collision-check-complexity bounds in Theorems 2 and 3 are also grounded in standard lattice-point-counting arguments. The paper is accompanied by a public code repository, which strengthens its reproducibility. However, the headline empirical claim of 'at least an order-of-magnitude speedup' is not uniformly supported by the reported data, and the transfer of the finite-time guarantee to the iA* planner used in all experiments is not formally established. These issues are local and fixable, so the paper is a credible candidate for publication after revision.

major comments (4)
  1. [§VI-C, Algorithm 2] The paper claims that lattice-based sample sets 'endow their planners with strong finite-time guarantees,' yet the planner used in all experiments is iA*, which searches an implicitly constructed partial graph G′ rather than the full PRM graph G_M(X,r*). No proof is given that the A* search over the implicit graph preserves the (δ,ε)-completeness path-length guarantee of the full graph. A correctly implemented A* with a consistent heuristic on an implicitly defined graph would indeed return a shortest path in the full graph, but this must be stated and proved, or the experimental claims should be explicitly decoupled from the theoretical guarantee.
  2. [§VII-B, §VII-E, Tables II and III] The δ tuning protocol may favor the lattice method. In both the multi-robot and manipulator experiments, δ is decreased until iA* with X_{A*_d} succeeds, while random sampling receives the same number of samples but a different connection radius r_rnd(n)=ψ(log n/n)^{1/d}. Thus the comparison is not at matched success rates or matched connection radii, and the reported speedups confound sampling quality with parameter tuning. The authors should either provide comparisons at matched success rates, report results for RND with radii comparable to r*, or substantially qualify the interpretation of the speedups.
  3. [Abstract, §I, §VII-C, Tables I and III] The abstract's claim of 'at least an order-of-magnitude speedup over existing deterministic and uniform random sampling methods' is not uniformly supported by the data. In Table I, the speedup of A*_d over D*_d is about 2.3× for BT5 (0.14 s vs 0.06 s) and about 3.5× for UM4 (8.47 s vs 2.43 s), not an order of magnitude. In Table III, RND at equal sample count is faster than iA*-LOC in window (2.9 ms vs 3.6 ms), sleeve (108.9 ms vs 160.2 ms), and sandwich (5.1 ms vs 9.7 ms), despite lower success rates. The paper also states in §VII-C that A*_d is 'at least 3×' faster than D*_d, which is contradicted by the BT5 row. The empirical claim should be reworded to match the data, or the missing matched-success-rate experiments should be added.
  4. [§VI-C, §VIII, Appendix E] The argument in Appendix E that failure to find a solution for δ=4 and ε∈{2,4,5} 'implies that no 4-clear solution exists' relies on the (δ,ε)-completeness of the pair (X_{A*_d}, r*) and on iA* correctly deciding non-reachability in the full graph. Since the iA* guarantee is not proved, the infeasibility interpretation is premature. This is the same issue as the first major comment, but it has a concrete consequence in the parameter study, so it should be resolved before the paper's theoretical claims are tied to the experimental planner.
minor comments (5)
  1. [§VI-B, Algorithm 1] The pseudo-code is unclear about the distinction between integer index vectors v ∈ Z^d and lattice points x = v·G_Λ. Line 14 writes 'pnew = p + e · GΛ' as if p were an integer vector, while line 15 tests '∥p∥ ≤ R' as if p were a lattice point. Please rewrite the algorithm so that the integer search state and the lattice point are separate variables, e.g., v and x = v·G_Λ, and check ∥x∥ ≤ R.
  2. [§II] There is a typo in the second paragraph: 'We concider a holonomic robot' should be 'We consider a holonomic robot.'
  3. [§IV, last paragraph] The sentence 'In the next session, we show...' should read 'In the next section, we show...'.
  4. [Appendix E, Figure 10] The text states that δ ∈ {2.75, 4}, but the caption of Figure 10 reports δ = 2.5 for the left column. The figure and text should be made consistent.
  5. [Tables I, II, III] The normalized solution-length columns are labeled 'Length (r)' without defining r in the caption. Please state explicitly that the length is normalized with respect to the A*_d solution length.

Circularity Check

0 steps flagged · score 0.0 of 10

The lattice-based derivation is self-contained; no circular reduction found.

full rationale

The derivation chain proceeds from externally established lattice covering radii (Conway & Sloane, cited as [3]), through a covering-radius rescaling argument (Theorem 1) to the completeness-cover lemma of Tsao et al. (Lemma 1). Lemma 1 is cited from prior peer-reviewed work and is a general theorem relating β*-covers to (δ,ε)-completeness; it is not tailored to the present claim or fitted to the reported speedups. The sample-complexity and collision-check bounds are derived from lattice point counting and rational ellipsoid estimates, not from the experimental outcomes. The speedup claims are empirical observations from Section VII, not outputs of a fitted model. The δ-tuning protocol in Section VII-B is a methodological fairness concern, but it does not make any derived guarantee equivalent to its own inputs: no equation is defined in terms of the conclusion, and no fitted parameter is renamed as a prediction. The self-citations to [4] and [50] are to independently published, checkable results, so they do not constitute load-bearing circularity. The unproved inheritance of the guarantee by iA* is a proof gap rather than a circular step, since A* on the implicit graph would return the graph's shortest path if fully explored.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

No new physical or mathematical entities are postulated; A*_d is a known lattice from Conway-Sloane. The T embedding is a new mapping but not an invented entity.

free parameters (3)
  • delta (clearance parameter) = per scenario, decreased until A*_d succeeded
    Chosen by hand for each scenario; determines beta*, r*, and sample count. Not derived, and affects all reported running times.
  • epsilon (stretch factor) = 10 for main experiments
    Fixed by hand to emphasize running time; affects sample complexity exponentially.
  • psi (random baseline radius constant) = not specified
    The connection radius for uniform random sampling in comparisons is r_rnd(n)=psi(log n/n)^(1/d); psi is unspecified, so the baseline is not fully determined.
assumptions (4)
  • domain assumption Lemma 1: a beta*-cover with beta*=delta*epsilon/sqrt(1+epsilon^2) and connection radius r*=2delta(1+epsilon)/sqrt(1+epsilon^2) yields (delta,epsilon)-completeness
    This is the completeness-cover relation proved in Tsao et al. [50], cited and not reproven; the entire construction builds on it.
  • standard math Known covering radii of Z^d, D*_d, and A*_d from Conway-Sloane
    These numerical values determine the rescaling in Theorem 1 and the complexity comparison; taken as external proved results.
  • standard math Rational ellipsoid lattice point discrepancy bounds (Ivic et al.)
    Used in Theorem 2 to replace the exact count |Lambda intersect B_R| by volume/det plus a discrepancy term.
  • domain assumption The iA* algorithm preserves the (delta,epsilon)-completeness of the full PRM graph
    Not proven in the paper; the experimental speedup claims use iA*, which explores only a partial graph. A* optimality on the implicit graph likely suffices, but this is not stated.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Effective Sampling for Robot Motion Planning Through the Lens of Lattices." pith.science (2026). https://pith.science/paper/HRF5WNKJ

@misc{pith2026250204908,
  author       = {Pith},
  title        = {Pith review of: Effective Sampling for Robot Motion Planning Through the Lens of Lattices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HRF5WNKJ}},
  note         = {Machine review of arXiv:2502.04908}
}
abstract

Sampling-based methods for motion planning, which capture the structure of the robot's free space via (typically random) sampling, have gained popularity due to their scalability, simplicity, and for offering global guarantees, such as probabilistic completeness and asymptotic optimality. Unfortunately, the practicality of those guarantees remains limited as they do not provide insights into the behavior of motion planners for a finite number of samples (i.e., a finite running time). In this work, we harness lattice theory and the concept of $(\delta,\epsilon)$-completeness by Tsao et al. (2020) to construct deterministic sample sets that endow their planners with strong finite-time guarantees while minimizing running time. In particular, we introduce a highly-efficient deterministic sampling approach based on the $A_d^*$ lattice, which is the best-known geometric covering in dimensions $\leq 21$. Using our new sampling approach, we obtain at least an order-of-magnitude speedup over existing deterministic and uniform random sampling methods for complex motion-planning problems. Overall, our work provides deep mathematical insights while advancing the practical applicability of sampling-based motion planning.

Figures

Figures reproduced from arXiv: 2502.04908 by the authors.

Figure 1
Figure 1. Sample sets within a fixed disc in R2 , derived from the lattices Z 2 , D∗ 2 and A∗ 2 , which yield (δ, ε)-complete guarantees for the same values of δ and ε. The set X δ,ε Z2 can be viewed as a tessellation of space using cubes. The set X δ,ε D∗ 2 is obtained by placing a (rescaled) standard grid, and then placing another point in the middle of each cube. The set X δ,ε A∗ 2 can be viewed as a rescaled hexagonal gri… view at source ↗
Figure 2
Figure 2. (δ, ε)-complete sample sets in R3 derived from the lattices Z 3 , D∗ 3 and A∗ 3 . Note the sets X δ,ε D∗ d , X δ,ε A∗ d coincide for d = 3, and diverge for d ≥ 4. Note that the density of X δ,ε D∗ 3 and X δ,ε A∗ 3 (also known as the Body-Centered Cubic structure in crystallography), and is lower than the density of X δ,ε Z3 . Definition 6 (D∗ d lattice). The D∗ d lattice is defined by the generator matrix GD∗ d =  … view at source ↗
Figure 3
Figure 3. Visualization of embedding the lattice A∗ 2 originally defined in R3 onto R2 via the mapping T. The blue rectangle represents the plane H, where the corresponding A∗ 2 lattice points are drawn in red. The points are generated by taking integer vectors in Rd and applying the mapping Gt . H and A∗ 2 is reflected onto the plane H0 = {x3 = 0} using the mapping P Gt (denoted by the green rectangle). The third dimension i… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: A sample-complexity plot for the sample sets [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: A collision-check complexity plot for the sample sets [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: A subset of the scenarios used in the experimental results for the multi-robot setting. Some of the figures depict several scenarios, where each [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Manipulator tests in the VAMP environment, depicting the start and target configurations. Window: The arm moves through a window frame. Sleeve: [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]
Figure 8
Figure 8. Figure 8: Plot of the improvement factor γ. TABLE IV EXTENDED COMPARISON OF RUNNING TIME AND SOLUTION LENGTH USING LATTICES-BASED SAMPLE SETS (WHERE THE UNDERLYING LATTICE IS DENOTED IN THE TABLE) IN THE IA*-LOC ALGORITHM. SOLUTION LENGTH IS NORMALIZED WITH RESPECT TO THE LENGTH…
Figure 9
Figure 9. Figure 9: Additional scenarios used in the experiments. The scenario ZZB3, which is not illustrated here, is similar to ZZB2, only that the horizontal hallways [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]
Figure 10
Figure 10. Figure 10: Effect of the parameters δ, ε on the performance of LOC with X δ,ε A∗ d for δ = 2.5 (left) and δ = 4 (right). We report the running time (top) and solution length (bottom). The absence of data points for the parameters δ = 4, ε ∈ {2, 4, 5} indicates a solution failure…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 48 canonical work pages

  1. [1]

    Bailey, Alex Nash, Craig A

    James P. Bailey, Alex Nash, Craig A. Tovey, and Sven Koenig. Path-length analysis for grid-based path plan- ning. Artificial Intelligence, 301:103560, 2021

    work page 2021

  2. [2]

    Francesco Bullo and Andrew D. Lewis. Geometric Control of Mechanical Systems , volume 49 of Texts in Applied Mathematics. Springer Verlag, 2004

    work page 2004

  3. [3]

    Sphere packings, lattices and groups , volume 290

    John Horton Conway and Neil James Alexander Sloane. Sphere packings, lattices and groups , volume 290. Springer Science & Business Media, 2013

    work page 2013

  4. [4]

    Near-optimal multi-robot motion planning with finite sampling

    Dror Dayan, Kiril Solovey, Marco Pavone, and Dan Halperin. Near-optimal multi-robot motion planning with finite sampling. IEEE Transactions on Robotics , 2023

    work page 2023

  5. [5]

    Dellin and Siddhartha S

    Christopher M. Dellin and Siddhartha S. Srinivasa. A unifying formalism for shortest path problems with ex- pensive edge evaluations via lazy best-first search over paths with edge selectors. In International Conference on Automated Planning and Scheduling , pages 459–467. AAAI Press, 2016

    work page 2016

  6. [6]

    Andrew Dobson and Kostas E. Bekris. Sparse roadmap spanners for asymptotically near-optimal motion plan- ning. Int. J. Robotics Res. , 33(1):18–47, 2014

    work page 2014

  7. [7]

    Moustakides, and Kostas E

    Andrew Dobson, George V . Moustakides, and Kostas E. Bekris. Geometric probability results for bounding path quality in sampling-based roadmaps after finite compu- tation. In International Conference on Robotics and Automation, pages 4180–4186. IEEE, 2015

    work page 2015

  8. [8]

    Wolfgang Ebeling. Lattices and Codes: A Course Total time (s) Search time (s) Length (r) Success (%)Scenario (Robot #) A∗ d LOC A∗ d GLO RND GLO RND − GLO A∗ d GLO RND GLO RND − GLO RND GLO RND − GLO RND GLO RND − GLO N1(5) 0.36 3.05 4.16 3.40 0.84 3.37 2.59 1.48 1.46 80.00 90 N2(5) 0.41 2.67 2.74 4.28 0.82 2.11 3.62 2.43 3.31 65.00 95 N3(5) 0.59 3.83 5.4...

    work page

Show all 52 references
  1. [9]

    Asymptotically optimal inspection planning via efficient near-optimal search on sampled roadmaps

    Mengyu Fu, Alan Kuntz, Oren Salzman, and Ron Al- terovitz. Asymptotically optimal inspection planning via efficient near-optimal search on sampled roadmaps. Int. J. Robotics Res. , 42(4-5):150–175, 2023

    2023

  2. [10]

    Toward certifiable optimal motion planning for medical steerable needles

    Mengyu Fu, Kiril Solovey, Oren Salzman, and Ron Alterovitz. Toward certifiable optimal motion planning for medical steerable needles. Int. J. Robotics Res. , 42 (10):798–826, 2023

    2023

  3. [11]

    Gammell, Timothy D

    Jonathan D. Gammell, Timothy D. Barfoot, and Sid- dhartha S. Srinivasa. Batch informed trees (BIT*): Informed asymptotically optimal anytime search. Int. J. Robotics Res., 39(5), 2020

    2020

  4. [12]

    Resolu- tion independent density estimation for motion planning in high-dimensional spaces

    Bryant Gipson, Mark Moll, and Lydia E Kavraki. Resolu- tion independent density estimation for motion planning in high-dimensional spaces. In 2013 IEEE international conference on robotics and automation , pages 2437–

    2013

  5. [13]

    Al- gorithmic motion planning

    Dan Halperin, Oren Salzman, and Micha Sharir. Al- gorithmic motion planning. In Csaba D. Tóth, Joseph O’Rourke, and Jacob E. Goodman, editors, Handbook of Discrete and Computational Geometry , pages 1311–

  6. [14]

    Asymptotically optimal planning by feasible kinodynamic planning in a state-cost space

    Kris Hauser and Yilun Zhou. Asymptotically optimal planning by feasible kinodynamic planning in a state-cost space. IEEE Trans. Robotics , 32(6):1431–1443, 2016

    2016

  7. [15]

    Householder

    Alston S. Householder. Unitary triangularization of a nonsymmetric matrix. Journal of the ACM , 5(4):339– 342, 1958

    1958

  8. [16]

    Lattice points in large regions and related arithmetic functions: recent developments in a very classic topic

    A Ivic, E Krätzel, M Kühleitner, and WG Nowak. Lattice points in large regions and related arithmetic functions: recent developments in a very classic topic. arXiv preprint math/0410522, 2004

    2004 arXiv

  9. [17]

    Clark, and Marco Pavone

    Lucas Janson, Edward Schmerling, Ashley A. Clark, and Marco Pavone. Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions. I. J. Robotics Res. , 34(7):883–921, 2015

    2015

  10. [18]

    De- terministic sampling-based motion planning: Optimality, complexity, and performance

    Lucas Janson, Brian Ichter, and Marco Pavone. De- terministic sampling-based motion planning: Optimality, complexity, and performance. The International Journal of Robotics Research , 37(1):46–61, 2018

    2018

  11. [19]

    Sampling-based al- gorithms for optimal motion planning

    Sertac Karaman and Emilio Frazzoli. Sampling-based al- gorithms for optimal motion planning. The international journal of robotics research , 30(7):846–894, 2011

    2011

  12. [20]

    Probabilistic roadmaps for path planning in high-dimensional configuration spaces

    Lydia E Kavraki, Petr Svestka, J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE transac- tions on Robotics and Automation , 12(4):566–580, 1996

    1996

  13. [21]

    Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion plan- ning

    Michal Kleinbort, Oren Salzman, and Dan Halperin. Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion plan- ning. In Workshop on the Algorithmic Foundations of Robotics, pages 624–639. Springer, 2016

    2016

  14. [22]

    Bekris, and Dan Halperin

    Michal Kleinbort, Kiril Solovey, Zakary Littlefield, Kostas E. Bekris, and Dan Halperin. Probabilistic com- pleteness of RRT for geometric and kinodynamic plan- ning with forward propagation. Robotics and Automation Letters, 4(2):277–283, 2019

    2019

  15. [23]

    Uniform distribution of sequences

    Lauwerens Kuipers and Harald Niederreiter. Uniform distribution of sequences . Courier Corporation, 2012

    2012

  16. [24]

    Kinodynamic RRTs with fixed time step and best-input extension are not proba- bilistically complete

    Tobias Kunz and Mike Stilman. Kinodynamic RRTs with fixed time step and best-input extension are not proba- bilistically complete. In Workshop on the Algorithmic Foundations of Robotics, pages 233–244, 2014

    2014

  17. [25]

    Steven M. LaValle. Planning Algorithms . Cambridge University Press, 2006

    2006

  18. [26]

    LaValle and James J

    Steven M. LaValle and James J. Kuffner. Randomized kinodynamic planning. I. J. Robotics Res. , 20(5), 2001

    2001

  19. [27]

    A sampling and learning framework to prove motion planning infeasibility

    Sihui Li and Neil T Dantam. A sampling and learning framework to prove motion planning infeasibility. The International Journal of Robotics Research , 42(10):938– 956, 2023

    2023

  20. [28]

    A hexagonal grid-based sampling planner for aquatic environmental monitoring using un- manned surface vehicles

    Teng Li, Min Xia, Jiahong Chen, Shujun Gao, and Clarence de Silva. A hexagonal grid-based sampling planner for aquatic environmental monitoring using un- manned surface vehicles. In IEEE International Con- ference on Systems, Man, and Cybernetics , pages 3683– 3688, 2017

    2017

  21. [29]

    Yanbo Li, Zakary Littlefield, and Kostas E. Bekris. Asymptotically optimal sampling-based kinodynamic planning. I. J. Robotics Res. , 35(5):528–564, 2016

    2016

  22. [30]

    Calculus of variations and optimal con- trol theory: A concise introduction

    Daniel Liberzon. Calculus of variations and optimal con- trol theory: A concise introduction . Princeton University Press, 2011

    2011

  23. [31]

    Tenenbaum, and Yilun Du

    Yunhao Luo, Chen Sun, Joshua B. Tenenbaum, and Yilun Du. Potential based diffusion motion planning. In Forty- first International Conference on Machine Learning , 2024

    2024

  24. [32]

    Malyuta, T

    D. Malyuta, T. P. Reynolds, M. Szmuk, T. Lew, R. Bonalli, M. Pavone, and B. Acikmese. Convex optimization for trajectory generation. IEEE Control Systems Magazine, 42(5):40–113, 2022

    2022

  25. [33]

    Srinivasa

    Aditya Mandalika, Oren Salzman, and Siddhartha S. Srinivasa. Lazy receding horizon A* for efficient path planning in graphs with expensive-to-evaluate edges. In International Conference on Automated Planning and Scheduling, pages 476–484. AAAI Press, 2018

    2018

  26. [34]

    Srinivasa

    Aditya Mandalika, Sanjiban Choudhury, Oren Salzman, and Siddhartha S. Srinivasa. Generalized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles. In International Con- ference on Automated Planning and Scheduling , pages 745–7...

    2019

  27. [35]

    Motion planning around obstacles with convex optimization

    Tobia Marcucci, Mark Petersen, David von Wrangel, and Russ Tedrake. Motion planning around obstacles with convex optimization. Science Robotics, 8(84), 2023

    2023

  28. [36]

    Andreas Orthey, Constantinos Chamzas, and Lydia E. Kavraki. Sampling-based motion planning: A compar- ative review. Annual Review of Control, Robotics, and Autonomous Systems, 7(1), 2024

    2024

  29. [37]

    FCL: A general purpose library for collision and proximity queries

    Jia Pan, Sachin Chitta, and Dinesh Manocha. FCL: A general purpose library for collision and proximity queries. In 2012 IEEE International Conference on Robotics and Automation , pages 3859–3866, 2012

    2012

  30. [38]

    Solution of the problem of least dense lattice covering of five-dimensional space by equal spheres

    Sergei Sergeevich Ryshkov and Evgenii Petrovich Bara- novskii. Solution of the problem of least dense lattice covering of five-dimensional space by equal spheres. In Doklady Akademii Nauk , volume 222, pages 39–42. Russian Academy of Sciences, 1975

    1975

  31. [39]

    Donald E. Sands. Introduction to Crystallography. Dover Publications, New York, 1994

    1994

  32. [40]

    AMRA*: Anytime multi-resolution multi- heuristic A*

    Dhruv Mauria Saxena, Tushar Kusnur, and Maxim Likhachev. AMRA*: Anytime multi-resolution multi- heuristic A*. In IEEE International Conference on Robotics and Automation , pages 3371–3377, 2022

    2022

  33. [41]

    Lee, Ibrahim Awwal, Henry Bradlow, Jia Pan, Sachin Patil, Ken Goldberg, and Pieter Abbeel

    John Schulman, Yan Duan, Jonathan Ho, Alex X. Lee, Ibrahim Awwal, Henry Bradlow, Jia Pan, Sachin Patil, Ken Goldberg, and Pieter Abbeel. Motion planning with sequential convex optimization and convex collision checking. Int. J. Robotics Res. , 33(9):1251–1270, 2014

    2014

  34. [42]

    Towards prac- tical finite sample bounds for motion planning in TAMP

    Seiji A Shaw, Aidan Curtis, Leslie Pack Kaelbling, Tomás Lozano-Pérez, and Nicholas Roy. Towards prac- tical finite sample bounds for motion planning in TAMP. In Workshop on the Algorithmic Foundations of Robotics, 2024

    2024

  35. [43]

    Rahul Shome, Kiril Solovey, Andrew Dobson, Dan Halperin, and Kostas E. Bekris. dRRT *: Scalable and informed asymptotically-optimal multi-robot motion planning. Auton. Robots, 44(3-4):443–467, 2020

    2020

  36. [44]

    Lectures on the Geometry of Numbers, volume 201 of Springer-Verlag Grundlehren der mathematischen Wissenschaften

    Carl Ludwig Siegel. Lectures on the Geometry of Numbers, volume 201 of Springer-Verlag Grundlehren der mathematischen Wissenschaften. Springer, 1989

    1989

  37. [45]

    Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning

    Kiril Solovey, Oren Salzman, and Dan Halperin. Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. Int. J. Robotics Res. , 35(5):501–513, 2016

    2016

  38. [46]

    Strub and Jonathan D

    Marlin P. Strub and Jonathan D. Gammell. Adaptively informed trees (AIT*) and effort informed trees (EIT*): Asymmetric bidirectional sampling-based path planning. Int. J. Robotics Res. , 41(4):390–417, 2022

    2022

  39. [47]

    ¸ Sucan, Mark Moll, and Lydia E

    Ioan A. ¸ Sucan, Mark Moll, and Lydia E. Kavraki. The Open Motion Planning Library. IEEE Robotics & Automation Magazine , 19(4):72–82, December 2012. https://ompl.kavrakilab.org

    2012

  40. [48]

    Wil Thomason, Zachary Kingston, and Lydia E. Kavraki. Motions in microseconds via vectorized sampling-based planning. In IEEE International Conference on Robotics and Automation, pages 8749–8756

  41. [49]

    Strub, and Jonathan D

    Wil Thomason, Marlin P. Strub, and Jonathan D. Gam- mell. Task and motion informed trees (TMIT*): Almost- surely asymptotically optimal integrated task and motion planning. IEEE Robotics Autom. Lett. , 7(4):11370– 11377, 2022

    2022

  42. [50]

    Sample complexity of probabilistic roadmaps via ε-nets

    Matthew Tsao, Kiril Solovey, and Marco Pavone. Sample complexity of probabilistic roadmaps via ε-nets. In International Conference on Robotics and Automation , pages 2196–2202. IEEE, 2020

    2020

  43. [51]

    Anna Yershova and Steven M. LaValle. Deterministic sampling methods for spheres and SO(3). In IEEE International Conference on Robotics and Automation , pages 3974–3980, 2004

    2004

  44. [1342]

    Chapman and Hall/CRC, 3rd edition, 2017

    2017

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.