Decentralized chance-constrained finite-horizon
This paper considers finite-horizon optimal control for multi-agent systems subject to additive Gaussian-distributed stochastic disturbance and a chance constraint. The problem is particularly difficult when agents are coupled through a joint chance constraint, which limits the probability of constr...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/66244 https://orcid.org/0000-0002-1057-3940 |
| _version_ | 1811069124196958208 |
|---|---|
| author | Williams, Brian Charles Ono, Masahiro |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Williams, Brian Charles Ono, Masahiro |
| author_sort | Williams, Brian Charles |
| collection | MIT |
| description | This paper considers finite-horizon optimal control for multi-agent systems subject to additive Gaussian-distributed stochastic disturbance and a chance constraint. The problem is particularly difficult when agents are coupled through a joint chance constraint, which limits the probability of constraint violation by any of the agents in the system. Although prior approaches can solve such a problem in a centralized manner, scalability is an issue. We propose a dual decomposition-based algorithm, namely Market-based Iterative Risk Allocation (MIRA), that solves the multi-agent problem in a decentralized manner. The algorithm addresses the issue of scalability by letting each agent optimize its own control input given a fixed value of a dual variable, which is shared among agents. A central module optimizes the dual variable by solving a root-finding problem iteratively. MIRA gives exactly the same optimal solution as the centralized optimization approach since it reproduces the KKT conditions of the centralized approach. Although the algorithm has a centralized part, it typically uses less than 0.1% of the total computation time. Our approach is analogous to a price adjustment process in a competitive market called tatonnement or Walrasian auction: each agent optimizes its demand for risk at a given price, while the central module (or the market) optimizes the price of risk, which corresponds to the dual variable. We give a proof of the existence and optimality of the solution of our decentralized problem formulation, as well as a theoretical guarantee that MIRA can find the solution. The empirical results demonstrate a significant improvement in scalability. |
| first_indexed | 2024-09-23T08:06:05Z |
| format | Article |
| id | mit-1721.1/66244 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:06:05Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/662442022-09-30T07:29:31Z Decentralized chance-constrained finite-horizon Williams, Brian Charles Ono, Masahiro Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Williams, Brian Charles Williams, Brian Charles Ono, Masahiro This paper considers finite-horizon optimal control for multi-agent systems subject to additive Gaussian-distributed stochastic disturbance and a chance constraint. The problem is particularly difficult when agents are coupled through a joint chance constraint, which limits the probability of constraint violation by any of the agents in the system. Although prior approaches can solve such a problem in a centralized manner, scalability is an issue. We propose a dual decomposition-based algorithm, namely Market-based Iterative Risk Allocation (MIRA), that solves the multi-agent problem in a decentralized manner. The algorithm addresses the issue of scalability by letting each agent optimize its own control input given a fixed value of a dual variable, which is shared among agents. A central module optimizes the dual variable by solving a root-finding problem iteratively. MIRA gives exactly the same optimal solution as the centralized optimization approach since it reproduces the KKT conditions of the centralized approach. Although the algorithm has a centralized part, it typically uses less than 0.1% of the total computation time. Our approach is analogous to a price adjustment process in a competitive market called tatonnement or Walrasian auction: each agent optimizes its demand for risk at a given price, while the central module (or the market) optimizes the price of risk, which corresponds to the dual variable. We give a proof of the existence and optimality of the solution of our decentralized problem formulation, as well as a theoretical guarantee that MIRA can find the solution. The empirical results demonstrate a significant improvement in scalability. Boeing Company (grant MIT-BA-GTA-1) 2011-10-13T16:54:57Z 2011-10-13T16:54:57Z 2010-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-7745-6 0743-1546 http://hdl.handle.net/1721.1/66244 Ono, Masahiro, and Brian C. Williams. “Decentralized Chance-constrained Finite-horizon Optimal Control for Multi-agent Systems.” 49th IEEE Conference on Decision and Control (CDC). Atlanta, GA, USA, 2010. 138-145. © 2011 IEEE https://orcid.org/0000-0002-1057-3940 en_US http://dx.doi.org/10.1109/CDC.2010.5718144 49th IEEE Conference on Decision and Control (CDC), 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Williams, Brian Charles Ono, Masahiro Decentralized chance-constrained finite-horizon |
| title | Decentralized chance-constrained finite-horizon |
| title_full | Decentralized chance-constrained finite-horizon |
| title_fullStr | Decentralized chance-constrained finite-horizon |
| title_full_unstemmed | Decentralized chance-constrained finite-horizon |
| title_short | Decentralized chance-constrained finite-horizon |
| title_sort | decentralized chance constrained finite horizon |
| url | http://hdl.handle.net/1721.1/66244 https://orcid.org/0000-0002-1057-3940 |
| work_keys_str_mv | AT williamsbriancharles decentralizedchanceconstrainedfinitehorizon AT onomasahiro decentralizedchanceconstrainedfinitehorizon |