Fast Asymptotically Optimal Kinodynamic Planning via Vectorization

• URL: http://arxiv.org/abs/2607.03987v2
• Date: Sun, 12 Jul 2026 20:18:28 GMT
• Title: Fast Asymptotically Optimal Kinodynamic Planning via Vectorization
• Abstract summary: We present Parallel Asymptotically Optimal Kinodynamic RRTPAKR, a massively parallel kinodynamic planner leveraging JAX and the XLA compiler.<n>By combining our parallel planner with the AO-x meta-algorithm, we achieve optimality through fast iterative replanning.
• Score: 0.764671395172401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• cuRegOT: A GPU-Accelerated Solver for Entropic-Regularized Optimal Transport [8.189956090077677]
  cuRegOT is a high-performance GPU solver tailored for entropic-regularized OT.<n>We introduce a suite of algorithmic and architectural optimizations, including an amortized symbolic analysis strategy to mitigate CPU bottlenecks.<n>CuRegOT achieves significant speedups over state-of-the-art GPU-based solvers across a variety of benchmark tasks.
  arXiv  Detail & Related papers  (2026-05-09T08:27:39Z)
• GPU-Accelerated Continuous-Time Successive Convexification for Contact-Implicit Legged Locomotion [0.4588028371034407]
  Contact-implicit trajectory optimization (CITO) enables the automatic discovery of contact sequences.<n>We introduce integral cross-compITOlementarity constraints, which eliminate the risk of missing contact events between discretization nodes.<n>We show that the resulting framework, contact-implicit successive convexification (ci-SCvx), models full multibody dynamics in maximal coordinates.
  arXiv  Detail & Related papers  (2026-04-11T02:40:29Z)
• Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming [2.8852807790754618]
  We introduce a fully GPU-native trajectory optimization framework that combines sequential convex programming with a consensus-based alternating direction method of multipliers.<n>We validate the solver on a quadrotor agile flight task and a Mars powered descent problem using an on-board edge computing platform.<n> Benchmarks reveal a sustained 4x throughput speedup and a 51% reduction in energy consumption over a heavily optimized 12-core CPU baseline.
  arXiv  Detail & Related papers  (2026-03-11T12:39:14Z)
• Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
  Mixed-integer programming (MIP) extends linear programming by incorporating both continuous and integer decision variables.<n>This paper presents the first fully open-source implementation of deterministic parallel branch-and-bound for HiGHS, a high-performance MIP solver.<n>Our approach introduces a novel data-parallel architecture ensuring strict determinism by replicating complete solver state across worker threads.
  arXiv  Detail & Related papers  (2026-02-10T14:17:53Z)
• Kino-PAX$^+$: Near-Optimal Massively Parallel Kinodynamic Sampling-based Motion Planner [11.640483409938724]
  We introduce Kino-PAX$+$, a massively parallel kinodynamic motion planner with near-optimal guarantees.<n>Kino-PAX$+$ finds solutions up to three orders of magnitude faster than existing serial methods and achieves lower solution costs than a state-of-the-art GPU-based planner.
  arXiv  Detail & Related papers  (2026-02-02T21:50:18Z)
• Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings [73.44599934855067]
  LookaHES is a nonmyopic BO framework designed for dynamic, history-dependent cost environments.<n>LookaHES combines a multi-step variant of $H$-Entropy Search with pathwise sampling and neural policy optimization.<n>Our innovation is the integration of neural policies, including large language models, to effectively navigate structured, domain-specific action spaces.
  arXiv  Detail & Related papers  (2026-01-10T09:49:45Z)
• Eliminating Multi-GPU Performance Taxes: A Systems Approach to Efficient Distributed LLMs [61.953548065938385]
  We introduce the ''Three Taxes'' (Bulk Synchronous, Inter- Kernel Data Locality, and Kernel Launch Overhead) as an analytical framework.<n>We propose moving beyond the rigid BSP model to address key inefficiencies in distributed GPU execution.<n>We observe a 10-20% speedup in end-to-end latency over BSP-based approaches.
  arXiv  Detail & Related papers  (2025-11-04T01:15:44Z)
• Improved particle swarm optimization algorithm: multi-target trajectory optimization for swarm drones [20.531764063763678]
  Traditional Particle Swarm Optimization (PSO) methods struggle with premature convergence and latency in real-time scenarios.<n>We propose PE-PSO, an enhanced PSO-based online trajectory planner.<n>We develop a multi-agent framework that combines genetic algorithm (GA)-based task allocation with distributed PE-PSO, supporting scalable and coordinated trajectory generation.
  arXiv  Detail & Related papers  (2025-07-18T04:31:49Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.<n>An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Globally Optimal Event-Based Divergence Estimation for Ventral Landing [55.29096494880328]
  Event sensing is a major component in bio-inspired flight guidance and control systems. We explore the usage of event cameras for predicting time-to-contact with the surface during ventral landing. This is achieved by estimating divergence (inverse TTC), which is the rate of radial optic flow, from the event stream generated during landing. Our core contributions are a novel contrast maximisation formulation for event-based divergence estimation, and a branch-and-bound algorithm to exactly maximise contrast and find the optimal divergence value.
  arXiv  Detail & Related papers  (2022-09-27T06:00:52Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.