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

Keyi Shen1*, Jiangwei Yu1*, Huan Zhang1, Yunzhu Li2
1University of Illinois Urbana-Champaign, 2Columbia University
* Equal Contribution
Paper arXiv Video Code


BaB-ND employs branch-and-bound method to plan long-horizon trajectories using neural dynamics model.

Main Contributions

Our work addresses the problem of effective motion planning over learned neural dynamics models. Existing sampling-based or gradient-descent-based approaches often fail when the planning scenario is difficult due to the underlying optimization difficulty arising from a highly nonconvex neural network dynamics model. Our main contributions are:
  • Branch-and-Bound-Based Planning Framework: We propose a widely applicable branch-and-bound (BaB) framework for effective long-horizon motion planning over neural dynamics models. Our algorithm systematically searches the action space and outperforms existing search algorithms such as MPPI/CEM on challenging planning tasks.
  • Neural Network Verification-Inspired Algorithm Design: Our framework's key algorithm is inspired by a successful neural network verifier α,β-CROWN. We provide a novel adaptation of the neural network verification procedures for robotic planning tasks with neural dynamics models. Our work connects the efforts in both the robotics and verification communities.
  • Demonstrated Effectiveness in Real-world Experiments: We showcase our framework's effectiveness across a range of complex planning problems in the real world, including contact-rich manipulation, handling deformable objects, and managing object piles. We utilize diverse neural dynamics model architectures, including multilayer perceptrons (MLPs) and graph neural networks (GNNs).

Video

Method Overview

We propose a branch-and-bound framework for long-horizon planning, involving branching, bounding, and searching.
  • The branching procedure systematically divides the search space with a heuristic.
  • The bounding procedure efficiently evaluates the lower bounds of objectives.
  • The searching procedure can find high-quality solutions to objectives in sub-domains.

Tasks

We evaluate our framework on four complex robotic manipulation tasks involving non-smooth objectives, non-convex feasible regions and requiring long action sequences. Different architectures of neural dynamics like MLP and GNN are leveraged for different scenarios.

Execution under Disturbances

Acknowledgments

This work is supported by Toyota Research Institute (TRI). We thank Jose Barreiros, Hongkai Dai, Aykut Onol and Mengchao Zhang for their constructive suggestions on the paper manuscript. We also thank Mingtong Zhang, Haozhe Chen, Baoyu Li and Binghao Huang for their help with real-world experiments and simulation environment development. This article reflects solely the opinions and conclusions of its authors, not those of TRI or any other Toyota entity.

BibTeX

@misc{shen2024babndlonghorizonmotionplanning,
      title={BaB-ND: Long-Horizon Motion Planning with Branch-and-Bound and Neural Dynamics}, 
      author={Keyi Shen and Jiangwei Yu and Huan Zhang and Yunzhu Li},
      year={2024},
      eprint={2412.09584},
      archivePrefix={arXiv},
      primaryClass={cs.RO},
      url={https://arxiv.org/abs/2412.09584}, 
    }