Long-horizon motion planning with branch-and-bound and neural dynamics
Yu, Jiangwei
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/127400
Description
Title
Long-horizon motion planning with branch-and-bound and neural dynamics
Author(s)
Yu, Jiangwei
Issue Date
2024-12-09
Director of Research (if dissertation) or Advisor (if thesis)
Li, Yunzhu
Department of Study
Siebel School Comp & Data Sci
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Branch-and-Bound
Motion planning
Abstract
Neural-network-based dynamics models, learned from observational data, have demonstrated strong predictive capabilities for scene dynamics in robotic manipulation tasks. However, their inherent non-linearity poses significant challenges for effective planning, particularly in long-horizon motion planning tasks involving complex contact events. Current planning methods, often rely on extensive sampling or local gradient descent, struggle to efficiently handle these complexities.
In this thesis, a GPU-accelerated branch-and-bound (BaB) framework is presented for motion planning in manipulation tasks that require trajectory optimization over neural dynamics models. This approach introduces a specialized branching heuristic to partition the search space into manageable sub-domains and applies a modified bound propagation method—drawing inspiration from the state-of-the-art neural network verifier α,β-CROWN to efficiently estimate objective bounds within these sub-domains. The branching process effectively guides the planning, while the bounding process strategically reduces the search space.
My framework achieves superior planning performance, generating high-quality state-action trajectories and outperforming 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, the framework supports various neural network architectures, ranging from simple multilayer perceptrons to advanced graph neural dynamics models, and scales efficiently with different model sizes.
The contributions of this thesis are threefold: (1) the development of a novel BaB framework tailored for motion planning over neural dynamics models; (2) the introduction of an adapted branch, bound, and search method for efficient optimization; and (3) extensive experimental validation demonstrating the framework's effectiveness and scalability in complex manipulation tasks. This work advances the field of robotic motion planning by providing a practical solution for planning over non-linear neural dynamics models, paving the way for more sophisticated and capable robotic systems.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
