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 |
| Summary: | 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. |
|---|