Distributed optimization for cooperative agents: application to formation flight
Authors:
- C.J. TomlinCTC.J. Tomlin
- S.P. BoydSBS.P. Boyd
- 1 January 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3 (01912216) , 2453-2459 Vol.3
Abstract
We present a simple decentralized algorithm to solve optimization problems involving cooperative agents. Cooperative agents share a common objective and simultaneously pursue private goals. Furthermore, agents are constrained by limited communication capabilities. The algorithm is based on dual decomposition techniques and appears to be very intuitive. It solves the dual problem of an artificially decomposed version of the primal problem, replacing one large computationally intractable problem with many smaller tractable problems. It returns a feasible solution to the primal problem as well as an upper bound on the distance between this solution and the global optimum. Both convex and nonconvex examples are presented, the complexity of the convex case is analyzed, and the savings in complexity are demonstrated for both examples. Finally, by showing that there is no duality gap in these examples, optimality is certified.Keywords
This publication has 12 references indexed in Scilit:
- Decentralized overlapping control of a formation of unmanned aerial vehiclesAutomatica, 2004
- Distributed control design for spatially interconnected systemsIEEE Transactions on Automatic Control, 2003
- Decentralized optimization, with application to multiple aircraft coordination2003
- Coordination of groups of mobile autonomous agents using nearest neighbor rulesIEEE Transactions on Automatic Control, 2003
- Flutter Suppression for High Aspect Ratio Flexible Wings Using Microflaps2002
- A geometric study of duality gaps, with applicationsMathematical Programming, 2001
- Stochastic inclusion principle applied to decentralized automatic generation controlInternational Journal of Control, 1999
- Decentralized controllers for unmanned aerial vehicle formation flight1996
- Minimization Methods for Non-Differentiable Functions1985
- Estimates of the Duality Gap in Nonconvex OptimizationMathematics of Operations Research, 1976