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

Yi Wang; Bingxian Mu; Shahab Shokouhi; May-Win Thein

cs.ROApr 13, 2026

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

Authors: Yi Wang, Bingxian Mu, Shahab Shokouhi, May-Win Thein

Organizations: Department of Mechanical Engineering, University of New Hampshire, Durham, NH, 03824, USA. · Faculty of Sustainable Design Engineering, University of Prince Edward Island, Charlottetown, PE C1A 4P3, Canada

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 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 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 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.

Figures & tables

Figure 1: Experimental environment for the double-integrator robot (DIR) in a 2D workspace. This environment features enclosures, narrow passages, and multiple topological routes.

Figure 2: Experimental environment for the 10D linearized quadrotor (LQ) system in a 3D workspace. This environment features with non-convex corridors and narrow passages.

Panel of Figure 3 — Figure 3: Comparative performance of evaluated planners across different domains in terms of median solution cost and success rate over time, with 95 $\%$ confidence interval in each plot. Note that the median solution cost is $\infty$ when the success rate of a planner is below 50 $\%$ . The dots in each plot denote median initial solution times and costs with 95 $\%$ confidence intervals (CI), while shadows around the dots indicate a more conservative 99 $\%$ CI.

Motion Planning

Motion planning finds safe, feasible paths and trajectories for robots and vehicles amid geometric, dynamic, and task constraints.

See all 404 papers

BOWConnect: Parallel Bayesian Optimization over Windows with Learned Local Cost Maps for Sample-Efficient Kinodynamic Motion Planning
Jun 25, 2026Sourav Raxit, Abdullah Al Redwan Newaz, Jose Fuentes +1Constrained Motion Planning Kinodynamic Motion Planning
Department of Computer Science, Louisiana State University New Orleans, New Orleans, LA 70148, USA · Knight Foundation School of Computing and Information Sciences, Florida International University, Miami, FL 33199, USA
Bidirectional Incremental Generalized Hybrid A*
May 28, 2026Sidharth Talia, Oren Salzman, Siddhartha SrinivasaKinodynamic Motion Planning Tree Search
Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation
Aug 26, 2026Shashank A. Deshpande, Jonathan P. HowDifferential Flatness Kinodynamic Motion Planning
Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA, USA

Jun 25, 2026J/K move · Enter open · S save

BOWConnect: Parallel Bayesian Optimization over Windows with Learned Local Cost Maps for Sample-Efficient Kinodynamic Motion Planning

Sourav Raxit, Abdullah Al Redwan Newaz, Jose Fuentes, Leonardo Bobadilla

Department of Computer Science, Louisiana State University New Orleans, New Orleans, LA 70148, USA · Knight Foundation School of Computing and Information Sciences, Florida International University, Miami, FL 33199, USA

Constrained Motion Planning Kinodynamic Motion Planning Motion Planning Sampling-Based Motion Planning

Open paper AskPDF arXiv

This paper presents BOWConnect, a bidirectional parallel kinodynamic motion planner that addresses three fundamental limitations of existing sampling-based methods: sample inefficiency in high-dimensional state spaces, unreliable cost heuristics under dynamic constraints, and poor performance in narrow passage environments. Unlike classical planners that rely on random control sampling and geometric distance heuristics, BOWConnect integrates Bayesian Optimization over Windows (BOW) as a learning-based steering function within a parallel tree-based exploration framework, enabling each worker to learn local cost maps and constraints to guide sampling toward dynamically feasible and collision-free controls. A bidirectional architecture simultaneously grows forward and backward trees from the start and goal regions in parallel threads, with a spatial hashing mechanism enabling fast connection queries and a boundary value problem solver generating kinodynamically consistent bridge trajectories. Extensive evaluations across ten benchmark environments demonstrate that BOWConnect achieves 100% success while delivering the fastest or near-fastest planning time in complex scenarios, including narrow passages and non-convex spaces where state-of-the-art planners fail or degrade substantially. Real-world deployment on a ground vehicle and a quadrotor confirms real-time planning with no collisions. Videos of real-world and simulated experiments, high-resolution versions of the figures, and the open-source code are available at https://bow-connect.github.io/.

Abstract

Motion Planning

Explore similar work

BOWConnect: Parallel Bayesian Optimization over Windows with Learned Local Cost Maps for Sample-Efficient Kinodynamic Motion Planning

Bidirectional Incremental Generalized Hybrid A*

Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation