BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning

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 ≥ 96% success on every system while attaining the lowest planning time on three of four.

Video

Supplementary video: the edge-selection strategy, the bidirectional search, and planning runs on all four systems.

Method

Kinodynamic planners usually generate motions online, either through steering functions, which are expensive and hard to define for complex systems, or through Monte-Carlo forward propagation, which wastes effort in clutter. BBoE instead precomputes a large bundle of edges offline: short, dynamically feasible motions obtained by applying random controls for random durations. At planning time, the edges that start near the current state are transformed onto it and reused. Pose components are transformed away, so the bundle only needs to cover the kinodynamic subspace (velocities, steering and hitch angles), which is why 190 edges suffice for the unicycle and 50,000 to 100,000 for the 5D and 6D systems.

BBoE architecture: exploration and exploitation phases — **Two phases.** During exploration, the forward tree expands toward sampled states using the biased edges, while the reverse tree propagates random edges backward in time. During exploitation, the forward tree traces the reverse tree toward the goal using either the biased or the randomized edges.

2D projections of the edge bundles for each system — **Edge bundles.** Two-dimensional projections of a subset of the edges for each system; every edge starts at the origin. The unicycle edges are the maneuver library of the GBRRT paper; the other bundles are sampled from continuous control and duration ranges.

**Biased edges.** Neighboring edges are sorted by how close their stored end state lands to the desired state; BBoE then propagates every N-th edge of the sorted list, skipping the neighbors of a colliding edge, which tend to hit the same obstacle.

**Randomized edges.** When the current and desired states stay fixed, as in exploitation, the biased set can stall on the same collisions. With probability 1 − k_bias, BBoE draws the same number of edges uniformly from the sorted list instead, which finds narrow passages the biased set misses.

Results

All planners share a 5 s budget per trial, 50 random seeds, and, where applicable, the same edge bundle. Baselines: RRT, SST, GBRRT (each with Monte-Carlo and edge-bundle variants on the unicycle), BoE, and the search components of dB-RRT-F and dB-RRT-C. Columns E, M, H and VH are the easy, medium, hard and very-hard unicycle tiers, each 10 randomly generated environments; Uni, CWT, Tr and Qd are the fixed unicycle, car-with-trailer, treaded-vehicle and quadrotor environments.

Success rate (%)

Planner	Easy	Medium	Hard	Very Hard	Unicycle	CWT	Treaded	Quadrotor
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	–	–	–
BoE	100	62	60	18	48	0	96	0
GBRRT	–	–	–	–	–	100	88	88
GBRRT-MC	100	100	98	100	100	–	–	–
GBRRT-EB	100	100	100	100	100	–	–	–
Db-RRT-F	100	100	90	52	100	86	78	24
Db-RRT-C	100	100	96	70	100	98	100	48
BBoE	100	100	100	100	100	100	96	96

Cross-system evaluation

Mean initial-solution time (top) and mean solution cost (bottom) over successful trials. BBoE reaches 0.23 s on the unicycle, 0.71 s on the car with trailer and 1.66 s on the 6D quadrotor in a narrow-passage environment, and stays within the 1.2–2.0 s cluster of bidirectional planners on the treaded vehicle.

Unicycle solution time — Unicycle: solution time

Treaded solution time — Treaded: solution time

Quadrotor solution time — Quadrotor: solution time

Unicycle solution cost — Unicycle: solution cost

Treaded solution cost — Treaded: solution cost

Quadrotor solution cost — Quadrotor: solution cost

Scaling with obstacle clutter

On the unicycle, BBoE becomes the fastest planner from the medium tier onward (0.13 s medium, 0.18 s hard, 0.35 s very hard) while keeping 100% success, and the gap widens with clutter: on very-hard environments it is about 1.4× faster than the next-best GBRRT-EB, while the dB-RRT family drops to 52% and 70% success.

Medium tier time — Medium: solution time

Very hard tier time — Very hard: solution time

Medium tier cost — Medium: solution cost

Very hard tier cost — Very hard: solution cost

Planning in action

Forward tree in blue, reverse tree in red, final solution in green. Each clip is one planning run until the first solution.

BBoE across systems

Unicycle

Treaded vehicle

Car with trailer

Quadrotor (6D)

BBoE across unicycle difficulty tiers

Easy

Medium

Hard

Very hard

Baselines on a very-hard environment

RRT-MC

SST-MC

GBRRT-MC

BBoE

When does it fail?

For a fixed bundle, BBoE is probabilistically complete with respect to the graph the bundle induces, but not over the full state space, and it claims no optimality. Its failure mode is a coverage gap: a passage that requires a maneuver absent from the bundle cannot be traversed regardless of the budget. The environment below makes this concrete for the unicycle. Its only passage is a pair of offset slots joined by a chamber with 0.12 m of free width, so crossing it needs a pivot in place or a turning radius under 0.1 m. The 190-edge maneuver library has neither (every edge lasts 1 s at 1 m/s or more, with a tightest turning radius of 0.64 m), so BBoE fails on all 50 seeds, while a hand-built continuous-control trajectory passes the same collision checker.

Adversarial keyhole environment: BBoE trees after 5 s and a feasible continuous-control path — Both trees saturate their halves of the map without entering the keyhole; the green path is a feasible continuous-control trajectory through it.

Code and reproducibility

The planner, all baselines, the edge bundles, the benchmark scripts, and the logs behind every table and figure are released under the MIT license at github.com/brsrikrishna/bidirectional_bundle_of_edges_BBoE. Each benchmark is a single script with fixed seeds; the README lists the exact commands and the expected numbers.

Citation

@article{raghu2026bboe,
  title   = {{BBoE}: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning},
  author  = {Bangalore Raghu, Srikrishna and Roncone, Alessandro},
  journal = {IEEE Robotics and Automation Letters},
  year    = {2026},
  note    = {to appear}
}