Pith. sign in

REVIEW 2 major objections 5 minor 32 references

Fast Asymptotically Optimal Kinodynamic Planning via Vectorization

T0 review · 2 major / 5 minor · reviewed 2026-07-14 · grok-4.5

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

Pith's one-line read A parallel kinodynamic RRT wrapped in cost-bounded restarts finds high-quality robot trajectories in milliseconds on a GPU without CUDA.

desk verdict Solid systems paper: JAX/XLA vectorized kinodynamic RRT + AO-x gives real millisecond AO planning with open code and fair baselines. read the letter →

arxiv 2607.03987 v2 pith:YD4X7GQF submitted 2026-07-04 cs.RO

Yitian Gao , Andrew Lu , Zachary Kingston This is my paper · ORCID
classification cs.RO
keywords kinodynamicplanningsampling-basedmotionGPUaccelerationJAXasymptoticoptimalityAO-xparallelRRTMuJoCo-XLA
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

Kinodynamic motion planning must respect both geometry and the robot’s dynamics, but sequential sampling planners are often too slow for real-time use and many GPU versions demand specialized CUDA code. This paper introduces PAKR, a massively parallel kinodynamic RRT written in ordinary Python that JAX and XLA compile into a single GPU kernel. Fast but sub-optimal trees are deliberately accepted; the AO-x meta-algorithm then repeatedly restarts planning under a tightening cost bound so that solutions improve toward optimality. The authors prove that batching and branching do not destroy probabilistic completeness, show that moderate batch sizes and branching factors control the nearest-neighbor bottleneck, and demonstrate the planner on double integrators, airplanes, quadcopters, cart-poles, block pushing, and soft vine robots. Empirically the method matches or beats a leading CUDA planner in speed while returning smaller trees and better final costs than sequential asymptotically optimal baselines.

What carries the argument

Parallel AO Kinodynamic RRT (PAKR): each outer AO-x iteration freezes a cost bound, expands a tree by sampling B/A nearest parents and A controls per parent, propagates all B expansions in one vectorized step, and inserts only nodes whose f-cost lies below the bound; the whole loop is fused into a single GPU kernel.

What would settle it

On a standard Lipschitz system with a known optimal cost, run PAKR with the reported batch sizes and show that the returned cost fails to approach the optimum (or success rate collapses) as the number of AO-x restarts tends to infinity.

Watch

Extended reading notes

Core claim

PAKR establishes that vectorized forward-propagation RRT executed as a static-shape XLA kernel, when placed inside the AO-x cost-bounded restart loop, is probabilistically complete and asymptotically optimal under Lipschitz dynamics and cost, and that this combination yields competitive millisecond-scale runtimes with superior solution quality relative to existing GPU and CPU kinodynamic planners.

Load-bearing premise

That freezing the nearest-neighbor view for an entire batch and using a fixed integration step still leave the completeness and optimality arguments of ordinary kinodynamic RRT and AO-x intact.

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

2 major / 5 minor

Summary. The paper presents PAKR, a massively parallel kinodynamic RRT that vectorizes batch expansion (nearest-neighbor selection of B/A parents, A random controls per parent, simultaneous forward propagation) in JAX/XLA so that the entire planning loop runs as a single GPU kernel. The parallel RRT is wrapped in the AO-x meta-algorithm: each successful solution tightens a cost bound and the planner is restarted, yielding asymptotic optimality via rapid iterative replanning. Section IV-B argues that batching introduces only a one-batch delay in node visibility and that branching preserves all A=1 expansion opportunities, so probabilistic completeness of discrete-time forward-propagation RRT is retained; AO-x then supplies asymptotic optimality under standard Lipschitz assumptions on dynamics and cost. Experiments on double-integrator, Dubins airplane, quadcopter, unicycle, acrobot, MuJoCo cartpole/block-push and a soft vine robot report median times over 100 trials, competitive or better runtimes than Kino-PAX with substantially smaller trees (Table I), rapid cost improvement (Table II, Fig. 2), and superior or competitive final costs versus iDb-A* and SST* (Table III).

Significance. If the claims hold, the work removes a practical barrier to GPU-accelerated kinodynamic planning: specialized CUDA is replaced by ordinary Python/JAX while still delivering millisecond-scale solutions and asymptotic optimality. The combination of a static-shape, fully vectorized expansion loop with AO-x restarts is a clean engineering insight that is immediately usable by the community (open-source code is provided). Scalability demonstrations on MuJoCo-XLA and a soft-robot simulator further broaden the result beyond analytic dynamics. The theoretical argument is modest but correctly reduces to standard completeness and AO-x results; the empirical tables are thorough and reproducible.

major comments (2)
  1. Section IV-B correctly shows that a one-batch freeze of the nearest-neighbor snapshot only delays, rather than eliminates, any finite successful extension sequence, and that A>1 merely adds extra control samples. The argument, however, still relies on the unquantified proviso that the fixed integration step Δt is “sufficiently small.” Because the static-shape XLA design freezes Δt at compile time, a short remark (or a simple numerical check) on how Δt is chosen relative to the Lipschitz constants of the tested systems would make the completeness claim fully self-contained.
  2. Table III reports final costs for PAKR that are competitive with or better than iDb-A* and SST* after a 300 s budget for the sequential planners. The comparison is informative, yet the paper never states the wall-clock budget given to PAKR’s outer AO-x loop on those four problems. Without that number it is impossible to judge whether the reported Cost_f values reflect a comparable computational effort or simply many more restarts. Adding the PAKR time budget (or the number of AO-x iterations) would strengthen the optimality claim.
minor comments (5)
  1. Abstract and Introduction repeatedly claim “superior solution quality”; Table I only compares tree size and runtime against the non-AO Kino-PAX, while quality claims rest on Tables II–III. A single clarifying sentence would avoid over-statement.
  2. Figure 1 caption states that cost is distance traveled “to better visualize convergence,” yet the rest of the paper (and DynoBench) uses time. Explicitly noting that the visualization cost differs from the experimental cost criterion would prevent confusion.
  3. The Euclidean heuristic h(x)=∥x-x_goal∥_{2} is used for cost-bounded pruning (Alg. 1, line 11). For systems whose natural cost is time or energy this heuristic is not necessarily admissible; a brief caveat would be useful.
  4. Typographical inconsistencies appear throughout (e.g., “app roaches,” “spec ialized,” “access ibility,” “po rtability”). A careful proof-reading pass is needed.
  5. Kino-PAX+ is cited as providing near-optimality but is not compared because no open-source code exists. A short note on the expected qualitative difference would help readers place the present results.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: completeness and AO rest on external standard results; empirical claims are measured against independent baselines.

full rationale

The paper's central theoretical claims (probabilistic completeness of the parallel kinodynamic RRT, and asymptotic optimality via AO-x) are reductions to well-known external results rather than self-definitional constructions. Sec. IV-B explicitly inherits PC from sequential forward-propagation kinodynamic RRT [29] and AO from the AO-x meta-algorithm [14] under Lipschitz dynamics/cost; the only original argument is that batching introduces at most a one-batch delay on node availability and that branching factor A>1 only adds extra control samples, neither of which changes the asymptotic probability of realizing a finite successful-extension sequence. Fixed-step Δt is likewise standard for discrete-time completeness provided Δt is small. No parameter is fitted to data and then re-presented as a prediction; batch size B and branching A are free algorithmic hyperparameters whose effects are measured, not derived. Empirical tables compare against independent open implementations (Kino-PAX, OMPL SST*, iDb-A*) on previously published environments; solution costs and runtimes are not forced by construction from any free parameter of the method. Self-citations (e.g., the soft-robot simulator [21]) are used only for experimental domains, not as load-bearing uniqueness or completeness theorems. Consequently the derivation chain is self-contained against external benchmarks and exhibits no circular reduction.

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

The central claims rest on standard sampling-based planning theory plus a handful of engineering parameters required by XLA static compilation. No new physical entities are postulated; free parameters are the usual planner knobs (batch size, branching, step size, tree capacity) chosen for performance rather than fitted to hide a theoretical gap.

free parameters (4)
  • batch size B = 4k–32k in experiments
    Compile-time constant that sets the number of parallel expansions; chosen by hand and ablated (Table IV) but not derived.
  • branching factor A = typically 16–64
    Number of random controls per selected parent; free design choice that trades NN cost against exploration (A∈[2,128]).
  • max tree size N and memory tiers
    Static allocation required by XLA; tiers at 4^[6,10] are engineering choices.
  • propagation step Δt and horizon T
    Fixed-step RK4 integrator length; must be ‘sufficiently small’ for discrete-time completeness but is selected for speed.
assumptions (4)
  • domain assumption System dynamics f and cost J are Lipschitz continuous.
    Invoked in Sec. III and IV-B to inherit AO-x guarantees.
  • domain assumption Sequential forward-propagation kinodynamic RRT is probabilistically complete (Kleinbort et al. corrections).
    Used to argue that batching only adds a bounded delay (Sec. IV-B).
  • domain assumption AO-x transforms any probabilistically complete planner into an asymptotically optimal one under the stated cost properties.
    Core meta-algorithm of Hauser & Zhou; assumed to apply once the inner planner is PC.
  • ad hoc to paper Euclidean distance is an admissible heuristic for cost-bounded pruning.
    Used in Alg. 1 line 11; reasonable for many systems but not proven optimal for all dynamics considered.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Asymptotically Optimal Kinodynamic Planning via Vectorization." pith.science (2026). https://pith.science/paper/YD4X7GQF

@misc{pith2026260703987,
  author       = {Pith},
  title        = {Pith review of: Fast Asymptotically Optimal Kinodynamic Planning via Vectorization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YD4X7GQF}},
  note         = {Machine review of arXiv:2607.03987}
}
read the original abstract

Sampling-based motion planners have been shown to be effective for systems with complex kinodynamic constraints and high dimensionality. However, these algorithms struggle to achieve real-time performance, leading to recent efforts to parallelize planning. While GPU-accelerated planners have achieved significant speedups, existing approaches require specialized CUDA programming that limits accessibility and portability. We present Parallel Asymptotically Optimal Kinodynamic RRT (PAKR), a massively parallel kinodynamic planner leveraging JAX and the XLA compiler to achieve GPU acceleration through standard Python tooling. By combining our parallel planner with the AO-x meta-algorithm, we achieve asymptotic optimality through fast iterative replanning. We provide a theoretical analysis of probabilistic completeness, analyze the effects of batch size and branching factor on convergence, and demonstrate scalability to complex dynamics using the MuJoCo-XLA simulator. Experiments show competitive runtimes with state-of-the-art GPU planners and superior solution quality.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 1 linked inside Pith

  1. [1]

    LaValle, Planning Algorithms

    S. LaValle, Planning Algorithms. Cambridge University Press, 2006

    2006

  2. [2]

    Motion p lanning,

    L. E. Kavraki and S . M. L aValle, “Motion p lanning,” inSp ringer Handbook o f Robotics, B. Siciliano and O. Khatib, Eds. Cham, Switzerland: Springer, 2016, pp. 139–162

    2016

  3. [3]

    Rapidly-exploring random trees: A new tool for path planning,

    S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning,”The Annual Research Report, 1998

    1998

  4. [4]

    Asymptotically optimal sampling-based kinodynamic planning,

    Y . Li, Z. Littl efield, and K . E. Bekris, “Asymptotically optimal sampling-based kinodynamic planning,”T he International J ournal of Robotics Research, vol. 35, no. 5, pp. 528–564, 2016

    2016

  5. [5]

    Sampling-based motion planning: A comparative review,

    A. Orthey, C. Chamzas, and L. E. Kavraki, “Sampling-based motion planning: A comparative review,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 7, 2023

    2023

  6. [6]

    Motions in microseconds via vectorized samp ling-based p lanning,

    W. T homason, Z. Kingston, and L. E. Kavraki, “ Motions in microseconds via vectorized samp ling-based p lanning,” i n IEEE International Conference on Robo tics and Automation, pp. 8749–

  7. [7]

    Available: http://arxiv.org/abs/2309.14545

    [Online]. Available: http://arxiv.org/abs/2309.14545

    arXiv

  8. [8]

    Massively parallelizing the RRT and the RRT*,

    J. Bialkowski, S. Karaman, and E. Frazzoli, “Massively parallelizing the RRT and the RRT*,” in2 011 I EEE/RSJ I nternational Conference on Intelligent Robots and Systems, 2011, pp. 3513–3518

    2011

Show all 32 references
  1. [9]

    pRRTC: GPU-parallel RRT-Connect for fast, consistent, and low-cost motion planning,

    C. H. Huang, P. J adhav, B. Plancher, and Z . Kingston, “ pRRTC: GPU-parallel RRT-Connect for fast, consistent, and low-cost motion planning,” 2025. [Online]. Available: https://arxiv.org/abs/2503.06757

    2025

  2. [10]

    Kino-PAX: Highly parallel kinodynamic sampling-based planner,

    N. Perrault, Q. H. Ho, and M. Lahijanian, “Kino-PAX: Highly parallel kinodynamic sampling-based planner,”I EEE Robotics and Automation Letters, vol. 10, no. 3, pp. 2430–2437, 2025

    2025

  3. [11]

    Randomized motion planning on pa rallel and distributed architectures,

    S. Caselli and M. Reggiani, “Randomized motion planning on pa rallel and distributed architectures,” inP roceedings of the Seventh Euromicro Workshop on Pa rallel and Distributed P rocessing. PDP’99, 1999, pp. 297–304

    1999

  4. [12]

    C-FOREST: Parallel shortest path planning with supe rlinear speedup,

    M. Otte and N . Correll, “C-FOREST: Parallel shortest path planning with supe rlinear speedup,”I EEE Transactions on Robo tics, vol. 29, no. 3, pp. 798–806, 2013

    2013

  5. [13]

    Revisiting the asymptotic optimality of RRT,

    K. Solovey, L. J anson, E. Schmerling, E. Frazzoli, and M . Pavone, “Revisiting the asymptotic optimality of RRT,” in IEEE International Conference on Robotics and Automation, 2020, pp. 2189–2195

    2020

  6. [14]

    Kinodynamic RRT*: Asymptotically optimal motion p lanning for r obots w ith linear dynamics,

    D. J. Webb and J. van den Berg, “Kinodynamic RRT*: Asymptotically optimal motion p lanning for r obots w ith linear dynamics,” in IEEE International Conference on Robo tics and Automation, 2013, pp. 5054– 5061

    2013

  7. [15]

    Asymptotically optimal planning by feasible kinodynamic p lanning in a s tate–cost space,

    K. Hauser and Y .Zhou, “Asymptotically optimal planning by feasible kinodynamic p lanning in a s tate–cost space,”I EEE Transactions on Robotics, vol. 32, no. 6, pp. 1431–1443, 2016

    2016

  8. [16]

    J AX: composable transformations o f Python+NumPy programs,

    J. Bradbury, R. Frostig, P. Hawkins, M. J. J ohnson, C. L eary, D. Maclaurin, G. Necula, A. Paszke, J. V anderPlas, S. Wanderman- Milne, and Q. Zhang, “J AX: composable transformations o f Python+NumPy programs,” 2018. [ Online]. Available: http://github. com/jax-ml/jax

    2018

  9. [17]

    MuJoCo: A physics eng ine for model-based con trol,

    E. T odorov, T. Erez, and Y . Tassa, “ MuJoCo: A physics eng ine for model-based con trol,” in IEEE/RSJ I nternational Conference on Intelligent Robots and Systems, 2012, pp. 5026–5033

    2012

  10. [18]

    Probabilistic roadmaps for path planning in high-dimensional configuration spaces,

    L. Kavraki, P. Svestka, J.-C. Latombe, and M. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transactions on Robo tics and Automation, vol. 1 2, no. 4, pp. 566–580, 1996

    1996

  11. [19]

    RRT-Connect: An e fficient approach to single-query path p lanning,

    J. Kuffner and S . L aValle, “RRT-Connect: An e fficient approach to single-query path p lanning,” i n IEEE International Conference on Robotics and Automation, vol. 2, 2000, pp. 995–1001 vol.2

    2000

  12. [20]

    Path planning in expansive configuration spaces,

    D. Hsu, J.-C. Latombe, and R. Motwani, “Path planning in expansive configuration spaces,” inProceedings of International Conference on Robotics and Automation, vol. 3, 1997, pp. 2719–2726 vol.3

    1997

  13. [21]

    Bidirectional sampling-based motion plan- ning without two-point boundary value solution,

    S. Nayak and M. W. Otte, “Bidirectional sampling-based motion plan- ning without two-point boundary value solution,”I EEE Transactions on Robotics, vol. 38, no. 6, pp. 3636–3654, 2022

    2022

  14. [22]

    Parallel simulation o f contact and ac tuation for soft growing robots,

    Y . Gao, L. Chen, P. Bhovad, S. Wang, Z. Kingston, and L. H. Blumenschein, “Parallel simulation o f contact and ac tuation for soft growing robots,”Soft Robotics, 2026

    2026

  15. [23]

    Parallelized control-aware motion planning with learned controller proxies,

    S. Chow, D. Chang, and G. A. Hollinger, “Parallelized control-aware motion planning with learned controller proxies,”I EEE Robo tics and Automation Letters, vol. 8, no. 4, pp. 2237–2244, 2023

    2023

  16. [24]

    Asymptotically optimal sampling- based motion planning methods,

    J. D. Gammell and M . P. Strub, “Asymptotically optimal sampling- based motion planning methods,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 4, no. 1, pp. 295–318, 2021

    2021

  17. [25]

    Motion planning for autonomous d riving w ith a con formal spatiotemporal lattice,

    M. McNaughton, C. Urmson, J. M. Dolan, and J.-W. L ee, “Motion planning for autonomous d riving w ith a con formal spatiotemporal lattice,” i n2 011 I EEE International Conference on Robo tics and Automation, 2011, pp. 4889–4895

    2011

  18. [26]

    Kinodynamic mo tion planning,

    B. Donald, P. X avier, J. Canny, and J. Reif, “Kinodynamic mo tion planning,”J ournal of t he ACM, vol. 40, no. 5, p. 104 8–1066, Nov. 1993

    1993

  19. [27]

    Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds,

    B. R. Donald and P. Xavier, “Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds,”Algorithmica, vol. 14, no. 6, pp. 443–479, 1995

    1995

  20. [28]

    Kino-PAX+: Near-optimal massively parallel kinodynamic sampling-based motion planner,

    N. Perrault, Q. H. Ho, and M. Lahijanian, “Kino-PAX+: Near-optimal massively parallel kinodynamic sampling-based motion planner,” arXiv preprint arXiv:2602.02846, 2026

    2026

  21. [29]

    Kleinbort, O

    M. Kleinbort, O. Salzman, and D. Halperin, Collision Detection or Nearest-Neighbor Search? On the Compu tational Bottleneck in Sampling-based Mo tion P lanning. Cham: Springer I nternational Publishing, 2020, pp. 624–639. [Online]. Available: https://doi.org/10. 1007/978-3-030...

    2020

  22. [30]

    Corrections to “probabilistic completeness of RRT for geometric and kinodynamic p lanning w ith forward p ropagation

    M. Kleinbort, K. Solovey, Z. Littlefield, K. E. Bekris, and D. Halperin, “Corrections to “probabilistic completeness of RRT for geometric and kinodynamic p lanning w ith forward p ropagation”’,”I EEE Robo tics and Automation Letters, vol. 8, no. 2, pp. 1149–1150, 2023

    2023

  23. [31]

    iDb- A*: Iterative search and optimization for optimal kinodynamic motion planning,

    J. Ortiz-Haro, W. H¨onig, V . N. Hartmann, and M . Toussaint, “iDb- A*: Iterative search and optimization for optimal kinodynamic motion planning,”I EEE Transactions on Robo tics, vol. 41, pp. 2031–2049, 2025

  24. [32]

    The Open Motion Planning Library,

    I. A. S ¸ucan, M. Moll, and L. E. Kavraki, “The Open Motion Planning Library,”I EEE Robo tics and Automation Magaz ine, vol. 19, no. 4, pp. 72–82, December 2012, https://ompl.kavrakilab.org

    2012

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.