BaB-ND: Long-Horizon Motion Planning with Branch-and-Bound and Neural Dynamics

Neural-network-based dynamics models learned from observational data have shown strong predictive capabilities for scene dynamics in robotic manipulation tasks. However, their inherent non-linearity presents significant challenges for effective planning. Current planning methods, often dependent on extensive sampling or local gradient descent, struggle with long-horizon motion planning tasks involving complex contact events. In this paper, we present a GPU-accelerated branch-andbound (BaB) framework for motion planning in manipulation tasks that require trajectory optimization over neural dynamics models. Our approach employs a specialized branching heuristics to divide the search space into subdomains, and applies a modified bound propagation method, inspired by the state-of-the-art neural network verifier α,β-CROWN, to efficiently estimate objective bounds within these subdomains. The branching process guides planning effectively, while the bounding process strategically reduces the search space. Our framework achieves superior planning performance, generating high-quality state-action trajectories and surpassing existing methods in challenging, contact-rich manipulation tasks such as non-prehensile planar pushing with obstacles, object sorting, and rope routing in both simulated and real-world settings. Furthermore, our framework supports various neural network architectures, ranging from simple multilayer perceptrons to advanced graph neural dynamics models, and scales efficiently with different model sizes. Project page: https://robopil.github.io/bab-nd/ . * Equal contribution. 1 Published as a conference paper at ICLR 2025 T acke Ne al D a ic BaB Pla e R b Ne al D a ic BaB Pla e Pla e W ld Ne al D a ic Obser ation State, Action Ne State Action Better Branch & Bound Planner Queued Pruned Split Split Queued Pushing w/ Obstacles Object Merging Rope Routing Object Sorting (a) Planning with BaB-ND (b) Benchmark tasks Published as a conference paper at ICLR 2025 To simplify notation, we can substitute all constraints on xt+1 into the objective recursively, and further simplify the problem as a constrained optimization problem min u∈C f (u) (Eq. 1). Here f is our final objective, a scalar function that absorbs the neural network f dyn and the cost function summed in all H steps. u = u t0:t0+H ∈ C is the action sequence and C ⊂ R d is the entire input space with dimension d = kH. We also flatten u as a vector containing actions for all time steps, and use u j to denote a specific dimension. Our goal is to then find the optimal objective value f * and its corresponding optimal action sequence u * .