Optimal Kinodynamic Motion Planning Through Anytime Bidirectional Heuristic Search with Tight Termination Condition

• URL: http://arxiv.org/abs/2604.11587v1
• Date: Mon, 13 Apr 2026 15:03:00 GMT
• Title: Optimal Kinodynamic Motion Planning Through Anytime Bidirectional Heuristic Search with Tight Termination Condition
• Abstract summary: Bidirectional Tight Informed Trees (BTIT*) is an optimal kinodynamic sampling-based motion planning algorithm.<n>BTIT* integrates an anytime bidirectional search (Bi-HS) and ensures the emphmeet-in-the-middle property (MMP) and optimality (MM-optimality)
• Score: 2.005183503104021
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces Bidirectional Tight Informed Trees (BTIT*), an asymptotically optimal kinodynamic sampling-based motion planning algorithm that integrates an anytime bidirectional heuristic search (Bi-HS) and ensures the \emph{meet-in-the-middle} property (MMP) and optimality (MM-optimality). BTIT* is the first anytime MEET-style algorithm to utilize termination conditions that are efficient to evaluate and enable early termination \emph{on-the-fly} in batch-wise sampling-based motion planning. Experiments show that BTIT* achieves strongly faster time-to-first-solution and improved convergence than representative \emph{non-lazy} informed batch planners on two kinodynamic benchmarks: a 4D double-integrator model and a 10D linearized Quadrotor. The source code is available here.

Related papers

• From Atoms to Entropy: Optimal Noise Allocation for Diffusion Training in the Convex Regime [52.459513910242485]
  We develop a general statistical framework for studying optimal noise-level allocation in diffusion training.<n>We show that the optimized training schedule admits an atomic minimizer, concentrated on finitely many noise levels.<n>We then evaluate the entropic schedule in larger-scale experiments, where full schedule optimization is currently intractable.
  arXiv  Detail & Related papers  (2026-07-10T20:59:06Z)
• Optimal any-angle path planning in static and dynamic environments [3.8673630752805437]
  Zeta* and Zeta*-SIPP are developed for static and dynamic environments respectively.<n>Zeta*-SIPP, with either scanning method, is more than 20 times faster than the corresponding state-of-the-art optimal planner TO-AA-SIPP.
  arXiv  Detail & Related papers  (2026-06-30T12:40:23Z)
• 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)
• Just in time Informed Trees: Manipulability-Aware Asymptotically Optimized Motion Planning [46.553063931217245]
  We introduce the Just-in-Time Informed Trees (JIT*) algorithm, an enhancement over Effort Informed Trees (EIT*)<n>JIT* consistently outperforms traditional sampling-based planners across $mathbbR4$ to $mathbbR16$ dimensions.
  arXiv  Detail & Related papers  (2026-01-27T18:58:51Z)
• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization [45.99743804547533]
  Two-way partial AUCAUC is a critical performance metric for binary classification with imbalanced data.<n>Existing algorithms for TPAUC optimization remain under-explored.<n>We introduce two innovative double-coordinate block-coordinate algorithms for TPAUC optimization.
  arXiv  Detail & Related papers  (2025-05-28T03:55:05Z)
• CBOL-Tuner: Classifier-pruned Bayesian optimization to explore temporally structured latent spaces for particle accelerator tuning [46.348283638884425]
  We propose a complex-based convolutional-temporal autoencoder (AE) for latent space representation.<n>CBOLTune demonstrates superior performance in identifying multiple optimal settings.
  arXiv  Detail & Related papers  (2024-12-02T17:43:16Z)
• Bidirectional Looking with A Novel Double Exponential Moving Average to Adaptive and Non-adaptive Momentum Optimizers [109.52244418498974]
  We propose a novel textscAdmeta (textbfADouble exponential textbfMov averagtextbfE textbfAdaptive and non-adaptive momentum) framework. We provide two implementations, textscAdmetaR and textscAdmetaS, the former based on RAdam and the latter based on SGDM.
  arXiv  Detail & Related papers  (2023-07-02T18:16:06Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Ascent. We show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings. We extend our algorithm to extend the setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings.
  arXiv  Detail & Related papers  (2022-10-31T17:59:29Z)
• BBTv2: Pure Black-Box Optimization Can Be Comparable to Gradient Descent for Few-Shot Learning [83.26610968655815]
  Black-Box Tuning is a derivative-free approach to optimize continuous prompt tokens prepended to the input of language models. We present BBTv2, a pure black-box optimization approach that can drive language models to achieve comparable results to gradient-based optimization.
  arXiv  Detail & Related papers  (2022-05-23T11:10:19Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)

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.