{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/127400"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/127400","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Long-horizon motion planning with branch-and-bound and neural dynamics","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-12-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-12-01","abstract_has_math":false,"creators":["Yu, Jiangwei"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Li, Yunzhu"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-12-09","date_published":"2024-12-09","updated_at":"2026-07-22T22:25:04Z","subjects":["Branch-and-bound","Motion Planning"],"languages":["en","eng"],"rights":["Copyright 2024 Jiangwei Yu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/127400","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Li, Yunzhu"]},{"key":"dc:creator","label":"Author","values":["Yu, Jiangwei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-12-09","2024-12"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Branch-and-bound","Motion Planning"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2024 Jiangwei Yu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/127400"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-12-01","The student, Jiangwei Yu, accepted the attached license on 2024-12-04 at 17:50.","The student, Jiangwei Yu, submitted this Thesis for approval on 2024-12-04 at 18:05.","This Thesis was approved for publication on 2024-12-09 at 10:32.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21506 on 2025-03-28 at 14:44:44","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Long-horizon motion planning with branch-and-bound and neural dynamics"]}]}],"canonical_facts":{"dc:contributor":["Li, Yunzhu"],"dc:creator":["Yu, Jiangwei"],"dc:date":["2024-12-09","2024-12"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-12-01","The student, Jiangwei Yu, accepted the attached license on 2024-12-04 at 17:50.","The student, Jiangwei Yu, submitted this Thesis for approval on 2024-12-04 at 18:05.","This Thesis was approved for publication on 2024-12-09 at 10:32.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21506 on 2025-03-28 at 14:44:44","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/127400"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Jiangwei Yu"],"dc:subject":["Branch-and-bound","Motion Planning"],"dc:title":["Long-horizon motion planning with branch-and-bound and neural dynamics"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:04Z"}