Research map / Video / Video segmentation and tracking
BaB-ND: Long-Horizon Motion Planning with Branch-and-Bound and Neural Dynamics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BaB-ND, a GPU-accelerated branch-and-bound planner that optimizes action sequences over learned neural dynamics models using specialized branching, CROWN-based bounding adapted for planning, and CEM-based searching.
Problem
Long-horizon motion planning for contact-rich manipulation over non-linear learned neural dynamics models; sampling and gradient methods get stuck in sub-optima and MIP does not scale to large networks.
Approach
Adapt neural-network-verification branch-and-bound (CROWN bounding, alpha-CROWN style) for planning rather than verification: branch with heuristics that favor finding good feasible solutions, use early-stopped bound propagation with empirical intermediate bounds from sampling, and interleave CEM search in each subdomain.
Key results
- On the synthetic non-convex function, BaB-ND reaches optimality on 98 to 100 of 100 dimensions at d=100, outperforming GD, MPPI, and CEM.
- In scalability tests, MIP gives optimal solutions in only 6 of 36 settings and finds no solution in the rest within 300 s, while BaB-ND scales to horizon H=20 with models over 500K parameters.
- In object sorting, BaB-ND achieves similar median performance to CEM with noticeably lower variance; MPPI underperforms CEM on this discrete-action task.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BaB-ND instead of GD, MPPI, or CEM | long-horizon planning on the synthetic function · Synthetic function, input dimensions up to d=100 | best objective | Helped |
| Use BaB-ND instead of sampling-based baselines | Pushing with Obstacles and Object Merging · Pushing with Obstacles and Object Merging | open-loop objective | Helped |
| Use BaB-ND instead of MPPI or CEM | rope-routing planning · Rope Routing | open-loop objective | No clear effect |
| Use BaB-ND instead of CEM | object-sorting planning · Object Sorting | open-loop objective | Helped |
| Use BaB-ND instead of MPPI | object-sorting planning · Object Sorting | open-loop objective | Helped |
| Scale BaB-ND to larger models and longer horizons | Pushing with Obstacles planning · Pushing with Obstacles, H=20 | scalability: over 500K parameters | Helped |
| Use MIP for the tested model-size and planning-horizon settings | Pushing with Obstacles planning · Pushing with Obstacles, varying model sizes and horizons | solutions found within 300 seconds: 6 optimal solutions, 3 sub-optimal solutions, and fails to find any solution for the remaining within 300 seconds | Hurt |
Surprising findings
- MPPI performs worse than CEM on the object sorting task because it is better suited to continuous action sequences.
Limitations
- Planning performance depends on neural dynamics model prediction errors, causing sim-to-real mismatch.
- Optimality is influenced by the underlying sampling-based searching algorithm.
- Branching heuristics may not always select the optimal axis to split and may need generalization.
Experimental setup
Datasets: robot interaction data from simulation and real-world pushing, merging, rope routing, and sorting tasks
Benchmarks: synthetic non-convex function (up to d=100) pushing with obstacles object merging rope routing object sorting
Metrics: best objective (open-loop) final step cost (closed-loop) success rate runtime
Baselines: GD MPPI CEM MIP
Builds on: CROWN alpha-CROWN CEM MIP-based planning with ReLU dynamics
Closest papers by meaning
- GraphMP: Graph Neural Network-based Motion Planning with Efficient Graph Search (NeurIPS 2023 · similarity 0.87)
- Efficient Robotic Policy Learning via Latent Space Backward Planning (ICML 2025 · similarity 0.85)
- FLIP: Flow-Centric Generative Planning as General-Purpose Manipulation World Model (ICLR 2025 · similarity 0.85)
- Generative Trajectory Stitching through Diffusion Composition (NeurIPS 2025 · similarity 0.85)
- Potential Based Diffusion Motion Planning (ICML 2024 · similarity 0.85)
- RoboCerebra: A Large-scale Benchmark for Long-horizon Robotic Manipulation Evaluation (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.