BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: We're looking at the paper: "BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning".
Dev: Here's the gist of the paper. In this work, BBoE introduces a bidirectional, kinodynamic motion planner that leverages a precomputed bundle of edges to outperform existing baselines in key metrics like planning time and success rate in cluttered environments <ref:2509.20333#pg2>.
Rosa: This approach is significant because it consistently and quickly finds low-cost solutions in environments with varying obstacle clutter <ref:2509.20333#pg2>.
Dev: Core Methodology BBoE is a bidirectional kinodynamic sampling-based motion planner that employs two trees rooted at the start and goal states and uses precomputed robot motions (i.e., edges) to navigate through obstacles <ref:2509.20333#pg2>.
Rosa: The algorithm combines exploration and exploitation while relying on precomputed robot state traversals, resulting in efficient convergence towards the goal <ref:2509.20333#pg2>.
Title and authors: Rosa: So, we're talking about this paper called "BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning". It comes from Srikrishna Bangalore Raghu and Alessandro Roncone. Essentially, they've introduced a way to plan robot paths that works in complex environments with lots of obstacles.
Dev: It sounds like the core idea is using this bundle of precomputed motions, these edges, to make the planning process much faster and more successful than what we see in current methods.
Rosa: Right. The paper explains that instead of just sampling randomly every time you need a path, you precompute a bunch of robot motions first and then use that collection as a roadmap to navigate through the obstacles.
Dev: It’s about combining exploration and exploitation, which is standard in these planners, but they are using these precomputed robot state traversals to guide the search towards the goal more efficiently.
Taro: When you talk about precomputed robot state traversals, I wonder how much of that computation actually happens before you start planning? Is it a lot of upfront work?
Rosa: Well, they form this edge bundle when a set of random starting states goes through forward propagation using random control inputs for random time durations and those inputs result in final states. That creates the bundle where every edge is just a tuple with the starting state, the control input, the duration of time applied, and the final state.
Dev: And then when you actually want to plan a path between two points, you use this bundle of edges as a roadmap to navigate through it in both directions. That's what they call BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning <ref:2509.20333#pg2>.
Rosa: Exactly. The key contribution they highlight is this strategy to navigate through obstacle-rich spaces by sorting and sequencing those preprocessed forward propagations before the search begins.
Dev: And the second big part is BBoE itself, which is this robust bidirectional planner that uses that strategy to produce solutions that are both fast and successful in cluttered settings.
Taro: So it’s not just one method, but a whole framework where you have these randomized edges and biased edges you sort and select sequentially to get the best path. How does the system decide between those two types of edges?
Rosa: They gather all edges starting within a radius of some angle from your current state, they store them in this set called beta near sorted, and then they extract relevant ones into these two sets: beta randomized and beta biased.
Title and authors: Dev: The paper introduces a novel strategy where you choose a user-defined number N such that the length of the beta near sorted is an integral multiple of N. Then, the set called beta biased consists of the single best edge, e zero, and every Nth edge from the beginning of that sorted list.
Rosa: That means you end up with M plus one biased edges in your set called beta biased where M is that multiple. This selection process gives rise to these M plus one biased edges <ref:2509.20333#pg3>.
Dev: And then there are two phases: exploration and exploitation. During the exploration phase, both trees only use this set of beta biased edges to expand towards the candidate states.
Taro: So during that initial exploration stage, you’re relying entirely on these carefully selected biased edges to move around? What happens when those edges don't lead anywhere useful?
Rosa: In the exploitation phase, accurately tracing the reverse tree guarantees goal convergence because the root of that tree is a subset of the goal region. That ensures you actually find a path back to where you started efficiently.
Dev: The results show that BBoE consistently outperforms other planners like RRT and GBRRT across multiple key metrics in all scenarios tested, which is really impressive for kinodynamic problems.
Rosa: Specifically for the Unicycle scenario, every planner we tested had a one hundred percent success rate, but all variants of BBoE were able to find a solution within ten seconds of average planning time.
Taro: Ten seconds compared to what? That’s fast enough for real-time applications, but how much faster is that really when you compare it against the baseline planners like RRT and GBRRT?
Dev: It's approximately four times faster than RRT and GBRRT in that scenario. That reduction in planning time directly means less latency in the control loop.
Rosa: Now, looking at the ablation studies, they found that choosing a smaller N value, like one hundred, sacrifices both speed and success rate when dealing with cluttered environments.
Taro: So it means if you choose too few edges to select for bias, you run into trouble because nearby edges tend to collide together.
Dev: That confirms the idea that not every edge is useful in a dense environment; they can overlap, which ruins the plan. But then they found a sweet spot with N equal to five hundred, which keeps convergence fast and success high.
Rosa: They also mentioned that the BBoE eighty-five percent bias variant seems to be the most balanced setup when you look at how dependent it is on both the randomized and biased sets.
Taro: I'm curious about what this means for a system that might suddenly encounter new, unexpected obstacles during operation. Does this edge selection strategy handle that dynamic change well?
Title and authors: Dev: The way they structured the selection, using these specific biased and randomized sets based on a probabilistic threshold called k bias, helps the system avoid doing redundant computation when new obstacles show up. This should lead to faster convergence towards the goal even when the environment is changing.
Rosa: So in short, this paper provides a bidirectional planner that cuts planning time and solution cost by leveraging precomputed motions rather than relying on expensive online Monte Carlo propagations <ref:2509.20333#pg2>.
Dev: It’s about making sure that when you're dealing with complex kinodynamic problems, especially those with high obstacle clutter, you get a feasible path quickly without needing massive amounts of computation during the actual planning run.
Taro: For someone who only cares about real-world performance outside the lab, how does this translate to robustness when things don't go exactly as planned?
Rosa: The paper suggests that by strategically selecting propagation methods, BBoE is able to frequently find solutions within a stipulated time in cluttered regions, showing improved reliability over planners that rely only on online sampling during the exploitation phase.
Dev: That means less time spent trying to guess the right path when you're already deep into the search; you’re using the precomputed knowledge smartly.
Taro: So it moves from just finding *a* path to finding a good, feasible path under tight time constraints, even when things get messy?
Rosa: It does. The core idea is that by using this bundle of edges and sequencing them correctly, you are essentially guiding the robot efficiently towards the goal rather than just blindly throwing random samples around.
Dev: Overall, BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning presents a solid framework for improving speed and success in kinodynamic motion planning in cluttered spaces.
Taro: It seems like a very practical tool for applications where time is critical, provided you can afford that initial setup cost to build the edge bundle.
Rosa: Right. The authors pointed out their limitations, saying that scaling this approach to cover high-DOF robots is a pressing challenge because of memory constraints on storing all those edges.
Dev: And they also mentioned that future work could involve enabling the planner to improve its initial solution and provide better ones until the best one is attained, which would be interesting for iterative refinement.
Taro: For my testing perspective, I’d want to see how they handle memory when we push these systems beyond simple unicycle models into something with more degrees of freedom.
Rosa: That’s definitely the next big hurdle for this kind of work. So that's what we have today on BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning.
The paper's summary: Rosa: So, BBoE is this new motion planner that uses precomputed robot motions—these edges—to plan paths bidirectionally in cluttered spaces, and it does this much faster than what we usually see.
Dev: It’s about using a bundle of edges to create a roadmap, which lets the planner explore and exploit the space more efficiently than just random sampling.
Rosa: The paper says it’s significant because it consistently finds low-cost solutions quickly, even when there are tons of obstacles in the way. It tackles that problem by combining exploration and exploitation guided by these precomputed trajectories instead of relying only on expensive online Monte Carlo propagations.
Dev: That upfront work of building the edge bundle—where random starting states are propagated with random control inputs—is what makes it work faster during the actual planning query.
Rosa: Exactly. They sort those edges based on distance to where you want to go, and then they select a set of biased edges that gives them a strong starting point for navigation.
Dev: And the results show this actually beats RRT and GBRRT in terms of planning time and success rate across many different scenarios, especially for unicycle robots.
Rosa: For the unicycle scenario, every planner succeeds one hundred percent of the time, but BBoE finds a solution within ten seconds of average planning time, which is about four times faster than RRT and GBRRT.
Dev: That speed reduction is huge for real-time systems because it cuts down on latency in the control loop.
Rosa: Now, looking at why this matters for us out there in the field, it means we can find feasible paths in obstacle-rich spaces much more reliably and quickly than we could before.
Dev: But what about when things get messy? The paper mentions that tuning a parameter called N—which controls how many edges you pick for the biased set—is important because if N is too small, nearby edges collide together and the success rate drops.
Rosa: So there’s a trade-off there between speed and accuracy when dealing with dense clutter. They found that choosing a moderate skip value of five hundred keeps convergence fast while maintaining high success rates.
Dev: That means the system is adaptive in how it uses those precomputed motions to navigate, switching between using biased edges for accurate tracing and randomized edges to probabilistically find narrow passages if needed.
Rosa: The implication for applications is that we can expect better performance when the world misbehaves, because this approach doesn't just throw random samples around during the exploitation phase.
Dev: It moves the system from guessing a path to efficiently using stored knowledge to converge towards a goal in time-critical situations.
Rosa: So BBoE gives us a framework that leverages precomputed motions to deliver faster, more reliable paths in complex environments, but they also flag that scaling this up for high degree of freedom robots is still a major challenge because of memory constraints.
The paper's improvements: Rosa: So, we're looking at how BBoE suggests we can improve the planner itself by making these edge selections more dynamic and responsive to the environment.
Dev: The authors are proposing a way for the system to decide between using those biased edges and randomized edges based on a probabilistic threshold called k bias.
Rosa: That means instead of sticking with one fixed set of biased edges, it can switch things up depending on whether that best edge undergoes a collision.
Dev: That’s interesting because it sounds like the system gets smarter about which paths are actually useful in real-time as new obstacles appear.
Rosa: It suggests an adaptive edge selection strategy, where the planner dynamically switches between biased and randomized edges to find narrow paths if things start getting congested.
Dev: And they're also looking at improving how the initial solution is found, suggesting that instead of just settling for the first good path it finds, it could keep searching until it has a really high quality one.
Rosa: That’s interesting because finding a truly optimal path takes time, so having the planner refine its own initial guess over time sounds like a good way to get better results without running an endless search.
Dev: From my side as someone who deals with real-time loops, that iterative improvement idea makes sense if we can manage the computational cost of that refinement within our strict latency requirements.
Rosa: It hints at a future where the planner isn't just a one-shot search but something that keeps improving its path quality until it hits the best possible solution for that specific moment.
Dev: So, it’s moving toward a system where the initial guess is quickly followed by continuous optimization, which is something we need to think about for safety cases.
Rosa: It really points toward a more robust system that can handle unexpected changes in the environment gracefully because it's always trying to get better as it goes.
Dev: It sounds like the next big step will be figuring out how to make that continuous refinement process fast enough for actual deployment on real hardware.
Conclusion: Rosa: So, BBoE is this paper that uses a bundle of precomputed robot motions to plan paths bidirectionally in cluttered spaces, and it shows how fast and successful it can be compared to older methods.
Dev: Essentially, they’re using a collection of robot movements as a roadmap instead of relying on slow online sampling when you need to find a path.
Rosa: It tackles the problem of finding low-cost solutions quickly in complex environments by combining exploration and exploitation guided by that precomputed data.
Dev: And the numbers are pretty solid for the unicycle scenario, showing it can be four times faster than RRT and GBRRT while maintaining a one hundred percent success rate.
Rosa: That means for anyone running real-time control loops, this planner could significantly reduce planning latency when things get crowded.
Dev: But we gotta remember that their method depends on precomputing those edges first, so you have to build that bundle before you can use it, which is the main setup cost.
Taro: I wonder about the scalability here; if we want to move this beyond unicycles to high-degree of freedom robots, storing all those edges sounds like a massive memory challenge.
Rosa: That’s exactly what they pointed out in their limitations—scaling this approach up for more complex robots is a big hurdle because of the memory needed for the edge bundle.
Dev: They also touched on future work where they want to enable the planner to improve its initial solution until it finds the absolute best one, which could be interesting for iterative refinement.
Rosa: So, BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional Motion Planning gives us a very fast and reliable way to get feasible paths through obstacles right now.
Dev: It’s a solid framework for cutting planning time by leveraging stored knowledge instead of constantly running expensive online propagations.
Taro: For real-world autonomy, it means we can expect better performance when the world misbehaves because the system has a smarter way of navigating the known obstacle regions.
Rosa: That’s what it boils down to: using precomputed motions to make planning faster and more reliable in cluttered spaces.
Srikrishna Bangalore Raghu, Alessandro Roncone
University of Colorado Boulder
cs.RO
Submitted: 2025-09-24
Updated: 2026-10-27
Comments: Accepted for publication in IEEE Robotics and Automation Letters (RA-L). Project Website: https://brsrikrishna.github.io/BBoE_RAL/
License: http://creativecommons.org/licenses/by-sa/4.0/
Importance score: 82/100
The gist: In this work, BBoE introduces a bidirectional, kinodynamic motion planner that leverages a precomputed bundle of edges to outperform existing baselines in key metrics like planning time and success…
Key concepts
- Edge Bundle
- This is a collection of precomputed robot motions (edges) generated by applying random control inputs over time to various starting states. This bundle acts as a roadmap, allowing the planner to navigate efficiently between states without needing extensive online sampling during the actual planning query.
- Edge Selection Strategy
- This involves sorting edges based on their distance to the target state and selecting a subset called $\beta_{biased}$. This subset includes the best edge ($e_0$) and every $N^{th}$ edge from the sorted list, creating a focused set of trajectories for more accurate tree expansion.
- Bidirectional Search Phases
- The planner operates in two phases: exploration and exploitation. During exploration, both search trees use only the biased edges to expand towards candidate states. In the exploitation phase, tracing the reverse tree guarantees goal convergence because its root is located within the goal region.
- Adaptive Edge Selection
- The system dynamically switches between using biased edges (for precise tracing) and randomized edges (to find narrow paths) based on whether the best edge ($e_0$) collides. This adaptive choice helps the planner efficiently converge towards the goal amidst clutter by adjusting its search strategy in real-time.
Terminology
Summary
In this work, BBoE introduces a bidirectional, kinodynamic motion planner that leverages a precomputed bundle of edges to outperform existing baselines in key metrics like planning time and success rate in cluttered environments <ref:2509. p. 6 CONCLUSION AND FUTURE WORK
In this work, we presented BBoE, a bidirectional approach
to kinodynamic motion planning that leverages a precomputed bundle of edges to outperform existing baselines in
a number of key metrics. Specifically, our method reduces
planning time, lowers solution costs and demonstrates a high
success rate in heavily cluttered environments. BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional
Motion Planning
Srikrishna Bangalore Raghu1
, and Alessandro Roncone1
Abstract— In this work, we introduce BBoE, a bidirectional,
kinodynamic, sampling-based motion planner that consistently
and quickly finds low-cost solutions in environments with
varying obstacle clutter. The algorithm combines exploration
and exploitation while relying on precomputed robot state
traversals, resulting in efficient convergence towards the goal.Where the paper says it
Where the paper says it
Core Methodology
BBoE is a bidirectional kinodynamic sampling-based motion planner that employs two trees rooted at the start and goal states and uses precomputed robot motions (i.e., edges) to navigate through obstacles <ref:2509. p. 1 BBoE employs two
trees rooted at the start and goal states and uses precomputed
robot motions (i. , edges) to navigate through obstacles. BBoE: Leveraging Bundle of Edges for Kinodynamic Bidirectional
Motion Planning
Srikrishna Bangalore Raghu1
, and Alessandro Roncone1
Abstract— In this work, we introduce BBoE, a bidirectional,
kinodynamic, sampling-based motion planner that consistently
and quickly finds low-cost solutions in environments with
varying obstacle clutter. The algorithm combines exploration
and exploitation while relying on precomputed robot state
traversals, resulting in efficient convergence towards the goal.Where the paper says it
Where the paper says it
Edge Bundle Concept
The edge bundle is formed when a set of random start states undergoes forward propagation by applying random control inputs for random time durations to result in final states <ref:2509.20333#pg2>. Once a motion planning query is initiated, the bundle of edges is utilized as a roadmap to accurately navigate a unidirectional tree from the start to the goal <ref:2509. p. 0 , as a bundle) before initiating the motion planning phase. Once the motion planner is queried by providing a start and
a goal state, the bundle of edges is utilized as a roadmap
to accurately navigate a unidirectional tree from the start
to the goal.Where the paper says it
Edge Selection Strategy
The strategy involves sorting edges based on the distance between their end state and the desired state, resulting in βnear sorted <ref:2509.20333#pg2>. A novel strategy is introduced where a user-defined number N is chosen such that the length of βnear sorted is an integral multiple (i. p. 2 Our strategy aims to maximize the reach towards the desired
state while minimizing the number of propagation attempts. To do so, we choose a user-defined number N, which is an
integer greater than 1 such that the length of βnear sorted is an
integral multiple (i. Additionally, introducing bidirectionality to BoE can help further reduce planning
time, resulting in higher success rates. Toward this goal, we present the Bidirectional Bundle of
arXiv:2509. 1b, we obtain
βbiased and attempt to propagate sequentially. Starting from
the set’s best edge e0 upto it’s worst edge eMN, we make
propagation attempts in order until one collision-free path
(i. We pick the best edge (i. ,
e0) and every Nth edge from the beginning of βnear sorted
(i.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Bidirectional Search Phases
BBoE has two phases: exploration and exploitation <ref:2509.20333#pg2>. During exploration, both the trees only use the set of biased edges (i. p. 3 During exploration, we randomly
sample candidate states to be pursued by the forward and
reverse trees. Both the trees only use the set of biased
edges (i. Both the trees only use the set of biased
edges (i. , βbiased) to expand towards the candidate states. In the exploitation phase, the reverse tree continues to
randomly explore its surroundings while the forward tree
attempts to follow the reverse tree in the opposite direction
until it reaches the goal. In this case, accurately tracing the
reverse tree guarantees goal convergence due to the root of
the tree being a subset of the goal region.Where the paper says it
Where the paper says it
Where the paper says it
Performance Evaluation
The results show that BBoE consistently outperforms RRT and GBRRT in multiple key metrics in all scenarios <ref:2509.20333#pg2>. For the Unicycle scenario, every planner has a 100% success rate, while all variants of BBoE are able to find the solution within 10 seconds of average planning time, approximately 4X faster than RRT and GBRRT <ref:2509. p. 6 4) Unicycle: For the unicycle scenario, every planner has
a 100% success rate. However, all variants of BBoE are able
to find the solution within 10 seconds of average planning
time, approximately 4X faster than RRT and GBRRT.Where the paper says it
Ablation Studies Insights
A smaller N value (i.e., 100) sacrifices both speed and success rate in cluttered environments, confirming that nearby edges frequently collide together <ref:2509. p. 6 As seen in Table I,
a smaller N value (i. e, 100) sacrifices both speed and successrate in cluttered environments, confirming that nearby edges
frequently collide together; larger skips (N = 1000) fare
better but identifying the sweet spot with a moderate skip
value (N = 500) ensures fast convergence with high success. As seen in Table I,
a smaller N value (i. e, 100) sacrifices both speed and successrate in cluttered environments, confirming that nearby edges
frequently collide together; larger skips (N = 1000) fare
better but identifying the sweet spot with a moderate skip
value (N = 500) ensures fast convergence with high success. BBoE 75% has an 80% success rate but took longer to find
solutions due to the overusage of βrandom during exploration. BBoE 85% tends to be the most balanced variant in terms of
its dependency with βrandom and βbiased.Where the paper says it
Where the paper says it
Where the paper says it
Future Directions
Future work can explore enabling the planner to improve its initial solution and provide better ones until the best one is attained <ref:2509.20333#pg2>. Scaling the approach to cover high-DOF robots is a pressing challenge, stemming from memory constraints <ref:2509. p. 7 Due to memory limitations, BBoE is
confined to robots with low degrees of freedom. Scaling the
approach to cover high-DOF robots is a pressing challenge,
stemming from memory constraints. Benchmrking and integrating BBoE with idb-A*
and idb-RRT is an interesting future trajectory. Combining
lazy search tactics with the edge sequencing strategy to
further optimize propagation in cluttered spaces as well as
improving the existing strategy to choose the optimal edges
more efficiently represents a promising direction for future
work.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Bidirectional motion planner leveraging a bundle of precomputed robot motions (edges) to provide low-cost solutions with reduced runtime and high success rate amidst clutter. This allows AI systems to find feasible paths in obstacle-rich spaces by combining exploration and exploitation phases guided by precomputed trajectories rather than relying solely on costly online Monte Carlo propagations.
-
Novel strategy to sort and sequentially select edges for accurate tree expansion towards desired states with minimal propagation attempts. By choosing between biased edges (betabiased) and randomized edges (betarandom) based on a probabilistic threshold (kbias), the system avoids redundant computation when new obstacles are introduced, leading to faster convergence towards the goal.
-
High success rate in heavily cluttered environments by strategically selecting propagation methods. The paper shows that
In cluttered regions, this approach is able to frequently find solutions within a stipulated time,
demonstrating improved reliability compared to planners that rely solely on online sampling during exploitation phases. -
Reduced planning time and solution cost through leveraging precomputed robot motions. By utilizing an extensive number of forward propagations (i.e., edges) stored in a bundle before querying, the planner avoids
unnecessary computation
during the online phase, resulting in lower planning times for complex kinodynamic problems like navigating obstacle-rich spaces. -
Adaptive edge selection based on environment density and desired state proximity. The system dynamically switches between using biased edges (for accurate tracing when necessary) and randomized edges (to probabilistically find narrow paths) depending on whether the
best edge e0 undergoes collision,
which guides the robot toefficiently converge towards the goal amidst clutter.
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 at least96% success on every system while attaining the lowest planning time on three of four.
Related papers
- Rethinking Actions: Continuity-Aware Priors for World-Model Planning
- MOSAIC: Modular Obstacle and Spatial-Aware Framework for Manipulation In Cluttered Scenes
- SAGAS: Semantic-Aware Graph-Assisted Stitching for Offline Temporal Logic Planning
- DexSeed: Expanding Human Hand-Object Interactions into Robot Demonstrations for Dexterous Policy Learning
- LaST0.5: A Generalist World Action Model with Interaction-Centric Latent Reasoning
- CIALLO: Learning Shared Intent Representations for Cross-Embodiment Manipulation