Long-horizon motion planning with branch-and-bound and neural dynamics

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Yu, Jiangwei

Contributors dc:contributor

• Li, Yunzhu

• Branch-and-bound
• Motion Planning

Statement dc:rights

• Copyright 2024 Jiangwei Yu

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/127400

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F127400