BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning

Srikrishna Bangalore Raghu; Alessandro Roncone

cs.ROSep 24, 2025

BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning

Authors: Srikrishna Bangalore Raghu, Alessandro Roncone

Organizations: Human Interaction and Robotics [HIRO] Group, Computer Science Department, University of Colorado Boulder, Boulder, CO USA.

Abstract

In this work, we introduce BBoE, a bidirectional, kinodynamic, sampling-based motion planner that consistently and quickly finds solutions in environments with varying obstacle clutter. The algorithm combines exploration and exploitation while relying on precomputed robot motions, resulting in efficient convergence towards the goal. Our key contributions include: i) a strategy to quickly find solutions in obstacle-rich spaces by leveraging a bundle of precomputed robot motions (i.e., edges); and ii) BBoE, a robust bidirectional kinodynamic planner that utilizes this strategy to produce fast and feasible solutions. Across four systems spanning 3D to 6D state spaces, BBoE is the only planner to achieve $\geq96\%$ success on every system while attaining the lowest planning time on three of four.

Figures & tables

Fig. 1 : The functionality of BBoE spans two phases, exploration and exploitation. During exploration, the forward tree primarily uses the biased edges ( $\boldsymbol{\beta}_{\text{biased}}$ ) to expand towards the candidate state, while the reverse tree relies on propagating random edges backward in time. During exploitation, either the biased edges or the randomized edges ( $\boldsymbol{\beta}_{\text{random}}$ ) are used while allowing the forward tree to accurately trace the reverse tree towards the goal.

Panel of Figure 2 — Fig. 2 : Given the robot’s current state, we gather all edges initiating within a radius of $\theta$ from it and store them in $\boldsymbol{\beta}_{\text{near\_sorted}}$ . From this set, we extract relevant edges and store them in sets $\boldsymbol{\beta}_{\text{random}}$ (a) and $\boldsymbol{\beta}_{\text{biased}}$ (b). We show the exact order of edge propagation in each scenario with the result.

Fig. 3 : Final BBoE solutions showing unicycle environments across four difficulty tiers (seed 15795) and four different dynamical systems. The forward tree (blue) traces the reverse tree (red) into the goal region. The solution path (green) consists of forward-tree edges.

System	State Dim.	Distance Function ( $d_{X}$ )	# Edges	Ref.
Unicycle	3	$\\|\Delta\mathbf{p}\\|$	190	[ 5 ]
Treaded	5	$\big(\\|\Delta\mathbf{p}\\|^{2}+0.25^{2}\\|\Delta\mathbf{v}\\|^{2}\big)^{1/2}$	50000	[ 5 ]
CWT	6	$\big(\\|\Delta\mathbf{p}\\|^{2}+0.25^{2}\Delta v^{2}\big)^{1/2}$	50000	[ 5 ]
Quadrotor	6	$\big(\\|\Delta\mathbf{p}\\|^{2}+\\|\Delta\mathbf{v}\\|^{2}\big)^{1/2}$	100000	[ 28 ]

TABLE I : Specifications of the systems used in the experiments. For the distance functions,

\mathbf{p}

and

\mathbf{v}

denote the position and velocity vectors of the respective systems. # Edges is the number of bundle edges used at planning time.

Fig. 4 : The 2-dimensional projection of a subset of the edges generated for each system. Every edge starts at the origin of the XY plane. The unicycle edges are essentially the maneuver libraries used in the GBRRT paper.

Panel of Figure 6 — Fig. 5 : Cross-system planner evaluation on the unicycle, treaded vehicle, car-with-trailer (CWT), and quadrotor (50 seeds each). Top row: mean initial solution time on successes per system. Bottom row: mean solution cost on successes per system. BBoE achieves the lowest planning time on three of four systems and $\geq 96\%$ success on every system.

Panel of Figure 7 — Fig. 6 : Unicycle planner evaluation across 40 environments (10 per difficulty tier, 50 seeds each). Top row: Mean initial solution time on successes per difficulty. Bottom row: Mean solution cost on successes per difficulty.

Planner	E	M	H	VH	Uni	CWT	Tr	Qd
RRT	–	–	–	–	–	96	80	90
RRT-MC	100	100	92	88	100	–	–	–
RRT-EB	100	100	100	90	100	–	–	–
SST	–	–	–	–	–	100	82	52
SST-MC	100	100	100	82	100	–	–	–
SST-EB	100	100	100	88	100	–	–	–

TABLE II : Cumulative success rate (%).

(a) num_skip_edges skip S T (s) Cost 1 48/50 0.69 [0.26, 2.37] 184 [158, 213] 5 50/50 0.72 [0.31, 2.23] 198 [169, 246] 20 50/50 0.46 [0.14, 1.48] 201 [168, 284] 100 50/50 0.49 [0.16, 1.26] 205 [160, 246]

(b)

k_{\text{bias}}

k_{\text{bias}}

S T (s) Cost 0.00 42/50 2.53 [0.75, 4.97] 453 [320, 712] 0.25 50/50 0.81 [0.44, 1.85] 280 [199, 441] 0.50 50/50 0.69 [0.31, 1.55] 222 [182, 329] 0.75 50/50 0.65 [0.28, 1.21] 205 [169, 260] 1.00 50/50 0.67 [0.26, 1.43] 192 [168, 222]

(c) Unidirectional BBoE Difficulty S T (s) Cost Easy 50/50 0.16 [0.03, 0.46] 143 [123, 169] Medium 50/50 0.12 [0.03, 0.41] 166 [134, 225] Hard 50/50 0.18 [0.04, 0.83] 167 [132, 253] Very Hard 44/50 0.28 [0.03, 1.45] 193 [147, 297]

TABLE III : BBoE ablations on the unicycle environments. Time/cost: mean [min, max] over successful trials.

Motion Planning

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

See all 414 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
DynoFluxBench: Benchmarking Kinodynamic Space-Time Planners in Dynamic Environments
Sep 16, 2026Franz Queißner, Andreas Orthey, Wolfgang HönigKinodynamic Motion Planning Motion Planning
TU Berlin, Germany
Kino-PAX $^+$ : Near-Optimal Massively Parallel Kinodynamic Sampling-based Motion Planner
Feb 2, 2026Nicolas Perrault, Qi Heng Ho, Morteza LahijanianConstrained Motion Planning Kinodynamic Motion Planning
Department of Aerospace Engineering Sciences, University of Colorado Boulder, CO, USA · Department of Aerospace and Ocean Engineering, Virginia Tech, VA, 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

DynoFluxBench: Benchmarking Kinodynamic Space-Time Planners in Dynamic Environments

Kino-PAX+^++: Near-Optimal Massively Parallel Kinodynamic Sampling-based Motion Planner

Kino-PAX $^+$ : Near-Optimal Massively Parallel Kinodynamic Sampling-based Motion Planner