Distributed and certifiable optimization for multi-robot systems
Abstract/Contents
- Abstract
- This thesis addresses two key challenges in applying optimization methods to multi-robot systems. First, the need for distributed optimization arises in unstructured and remote environments in which centralized coordination is impractical or infeasible. Second, the nonconvexity of many relevant problems necessitates certifiable optimization, which provides provable bounds on the quality of a solution. We present new techniques for both distributed optimization and certifiable optimization, as well as a unified framework for distributed and certifiable multi-robot optimization. Several tools presented in this thesis enable robots to achieve system-wide coordination through pairwise communication. The ability to cooperatively solve optimization problems through distributed robot-to-robot communication is a crucial component of multi-robot autonomy. We introduce a communication-efficient general-purpose distributed optimization method, Separable Optimization Variable ADMM, and demonstrate its scalability and robustness. Additionally, an optimization-based approach to distributed estimation replicates the performance of the centralized Kalman Filter. We prove that our Distributed Rolling-Window Tracking algorithm maintains consistent estimates without communicating covariance matrices as alternative methods require. Our approach to certifiable optimization considers a broad class of synchronization problems that admit a semidefinite relaxation. We present a novel reformulation of the distance-based localization problem, showing for the first time that it belongs to this same class of certifiable optimization problems. Compared to other distance-based localization algorithms, our method recovers good solutions over a range of problem instantiations. Finally, we present a new approach to distributed certifiable optimization. Our technique for solving a decomposition of a sparse semidefinite program introduces a novel "dualized agreement" constraint. This formulation allows networked robots to iteratively solve for their individual components in a large semidefinite program. Together, these contributions provide a general framework for fully distributed and provably optimal multi-robot coordination.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2023; ©2023 |
| Publication date | 2023; 2023 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Halsted, Trevor Neill |
|---|---|
| Degree supervisor | Kennedy, Monroe |
| Degree supervisor | Schwager, Mac |
| Thesis advisor | Kennedy, Monroe |
| Thesis advisor | Schwager, Mac |
| Thesis advisor | Pilanci, Mert |
| Degree committee member | Pilanci, Mert |
| Associated with | Stanford University, School of Engineering |
| Associated with | Stanford University, Department of Mechanical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Trevor Halsted. |
|---|---|
| Note | Submitted to the Department of Mechanical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/vp445pw4013 |
Access conditions
- Copyright
- © 2023 by Trevor Neill Halsted
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...