Research status and prospect of distributed optimization for multiple aircraft

JIANG Xia; ZENG Xianlin; SUN Jian; CHEN Jie

doi:10.7527/S1000-6893.2020.24551

ACTA AERONAUTICAET ASTRONAUTICA SINICA >

2021 , Vol. 42 >Issue 4: 524551 - 524551

DOI: https://doi.org/10.7527/S1000-6893.2020.24551

Review

Research status and prospect of distributed optimization for multiple aircraft

JIANG Xia ,
ZENG Xianlin ,
SUN Jian ,
CHEN Jie

Expand

1. School of Automation, Beijing Institute of Technology, Beijing 100081, China;
2. Beijing Institute of Technology Chongqing Innovation Center, Chongqing 401120, China;
3. School of Electronic and Information Engineering, Tongji University, Shanghai 200082, China

Received date: 2020-07-17

Revised date: 2020-08-15

Online published: 2020-10-10

Supported by

National Natural Science Foundation of China (62073035,61925303,62088101); National Key Research and Development Program of China (2018YFB1700100)

Fold

Abstract

In the aviation field, practical tasks such as coordinated search and rescue, area monitoring, and formation control of multiple aircraft are conducted by many individuals with distributed information and complex task objectives. Distributed optimization is an important guarantee for the effective coordination of multiple aircraft in the above tasks, having significant theoretical and practical value. A brief introduction to classical distributed optimization tasks in the field of aviation is presented, and a research overview of distributed optimization work is conducted from three perspectives: problem models, research frameworks and classical algorithms of optimization problems. According to the optimization problems, the classical research works in the field of distributed optimization are summarized from four aspects: unconstrained distributed optimization, distributed optimization with set constraints, distributed optimization with inequality constraints, and distributed non-convex optimization. In addition, common difficulties in distributed optimization study and the future research directions of distributed optimization work are also discussed.

Key words： multiple aircraft; distributed optimization; control and decision; collaboration; trade-off between communication and computation

Cite this article

JIANG Xia , ZENG Xianlin , SUN Jian , CHEN Jie . Research status and prospect of distributed optimization for multiple aircraft[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021 , 42(4) : 524551 -524551 . DOI: 10.7527/S1000-6893.2020.24551

References

[1] 贾永楠,田似营,李擎. 无人机集群研究进展综述[J]. 航空学报, 2020, 41(S1):723738. JIA Y N, TIAN S Y, LI Q. The development of unmanned aerial vehicle swarms[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S1):723738(in Chinese).
[2] 衣鹏, 洪奕光. 分布式合作优化及其应用[J]. 中国科学, 2016(10):1547-1564. YI P, HONG Y G. Distributed cooperative optimization and its applications[J]. Scientia Sinica Mathematica, 2016(10):1547-1564(in Chinese).
[3] ZHONG M, CASSANDRAS C G. Distributed coverage control and data collection with mobile sensor networks[J]. IEEE Transactions on Automatic Control, 2011, 56(10):2445-2455.
[4] LIN Z J, LIU H H T. Topology-based distributed optimization for multi-UAV cooperative wildfire monitoring[J]. Optimal Control Applications and Methods, 2018, 39(4):1530-1548.
[5] RAFFARD R L, TOMLIN C J, BOYD S P. Distributed optimization for cooperative agents:Application to formation flight[C]//2004 43rd IEEE Conference on Decision and Control (CDC). Piscataway:IEEE Press, 2004:2453-2459.
[6] 吴宇, 梁天骄. 基于改进一致性算法的无人机编队控制[J]. 航空学报, 2020, 41(9):323848. WU Y, LIANG T J. Improved consensus-based algorithm for unmanned aerial vehicle formation control[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(9):323848(in Chinese).
[7] HUO M, FAN Z, QI N, et al. Fast cooperative trajectory optimization and test verification for close-range satellite formation using finite fourier series method[J]. Chinese Journal of Aeronautics, 2020, 33(8):2224-2229.
[8] RABBAT M, NOWAK R. Distributed optimization in sensor networks[C]//In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks. Piscataway:IEEE Press, 2004:20-27.
[9] 钟日进, 陈琪锋. 利用集群内测距和对目标测向的协同定位方法[J]. 航空学报, 2020, 41(S1):723768. ZHONG R J, CHEN Q F. Cooperative positioning method using distance measurement within a cluster and direction finding of a target[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S1):723768(in Chinese).
[10] ZHANG H, WEI J Q, YI P, et al. Projected primal-dual gradient flow of augmented Lagrangian with application to distributed maximization of the algebraic connectivity of a network[J]. Automatica, 2018, 98:34-41.
[11] YANG T, YI X, WU J, et al. A survey of distributed optimization[J]. Annual Review in Control, 2019, 47:278-305.
[12] 王东, 王泽华, 刘洋, 等. 基于事件触发的异构多智能体最优包含控制[J]. 航空学报, 2020, 41(S1):723775. WANG D, WANG Z H, LIU Y, et al. Event-triggered optimal containment control for heterogeneous multi-agent systems[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S1):723775(in Chinese).
[13] NEDIC A, OZDAGLAR A, PARRILO P A. Constrained consensus and optimization in multi-agent networks[J]. IEEE Transactions on Automatic Control, 2010, 55(4):922-938.
[14] FAN J, ZHOU W. A distributed resource allocation algorithm in multiservice heterogeneous wireless networks[C]//International Wireless Internet Conference. Berlin:Springer, 2013:34-43.
[15] MIRI M, DARMANI Y, MOHAMEDPOUR K, et al. DRAGON:A dynamic distributed resource allocation algorithm for wireless networks[J]. IEEE Communications Letters, 2020, 24(8):1780-1783.
[16] YI P, LEI J, HONG Y. Distributed resource allocation over random networks based on stochastic approximation[J]. Systems & Control Letters, 2018, 114:44-51.
[17] DOAN T T, BECK C L, SRIKANT R. On the convergence rate of distributed gradient methods for finite-sum optimization under communication delays[C]//Proceedings of the ACM on Measurement & Analysis of Computing Systems, 2017:1-27.
[18] HATANAKA T, CHOPRA N, ISHIZAKI T, et al. Passivity-based distributed optimization with communication delays using PI consensus algorithm[J]. IEEE Transactions on Automatic Control, 2018, 63(12):4421-4428.
[19] YAN J X, YU H. Distributed optimization of multiagent systems in directed networks with time-varying delay[J]. Journal of Control Science and Engineering, 2017:1687-5249.
[20] ZHOU Z, MERTIKOPOULOS P, BAMBOS N, et al. Distributed stochastic optimization with large delays[EB/OL].[2020-06-26]. https://pdfs.semanticscholar.org/bb9b/75105fe7e1395ed174ccb3882a218683322f.pdf.
[21] BOYD S, VANDENBERGHE L. Convex optimization[M]. Beijing:World Publishing Corporation, 2004.
[22] NEDIC A, OZDAGLAR A. Distributed subgradient methods for multi-agent optimization[J]. IEEE Transactions on Automatic Control, 2009, 54(1):48-61.
[23] SUNDHAR R S, NEDIC A, VEERAVALLI V V. Distributed stochastic subgradient projection algorithms for convex optimization[J]. Journal of Optimization Theory & Applications, 2008, 147(3):516-545.
[24] NEDIC A, OLSHEVSKY A, SHI W. Achieving geometric convergence for distributed optimization over time-varying graphs[J]. SIAM Journal on Optimization, 2017, 27(4):2597-2633.
[25] XU J, ZHU S, SOH Y C, et al. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes[C]//IEEE Conference on Decision & Control. Piscataway:IEEE Press, 2015:2055-2060.
[26] XU J, ZHU S, SOH Y C, et al. Convergence of asynchronous distributed gradient methods over stochastic networks[J]. IEEE Transactions on Automatic Control, 2018, 63(2):434-448.
[27] NEDIC A, OLSHEVSKY A, SHI W, et al. Geometrically convergent distributed optimization with uncoordinated step-sizes[C]//American Control Conference IEEE. Piscataway:IEEE Press, 2017:3950-3955.
[28] PAKAZAD S K, HANSSON A, ANDERSEN M S. Distributed interior-point method for loosely coupled problems[C]//IFAC Proceedings Volumes, 2014, 47(3):9587-9592.
[29] SHI Q, HONG M. Penalty dual decomposition method for nonsmooth nonconvex optimization-Part I:Algorithms and convergence analysis[J]. IEEE Transactions on Signal Processing, 2020, 68(1):4242-4257.
[30] FALSONE A, MARGELLOS K, GARATTI S, et al. Distributed constrained convex optimization and consensus via dual decomposition and proximal minimization[C]//2016 IEEE 55th Conference on Decision and Control (CDC). Piscataway:IEEE Press, 2016:1889-1894.
[31] LEI J, CHEN H F, FANG H T. Primal-dual algorithm for distributed constrained optimization[J]. Systems & Control Letters, 2016(96):110-117.
[32] YUAN D, XU S, ZHAO H. Distributed primal-dual subgradient method for multiagent optimization via consensus algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2011, 41(6):1715-1724.
[33] YUAN D, HO D W C, XU S. Regularized primal-dual subgradient method for distributed constrained optimization[J]. IEEE Transactions on Cybernetics, 2015, 46(9):2109-2118.
[34] CHANG T H, HONG M, LIAO W C, et al. Asynchronous distributed ADMM for large-scale optimization-Part I:Algorithm and convergence analysis[J]. IEEE Transactions on Signal Processing, 2016, 64(12):3118-3130.
[35] MOTA J F C, XAVIER J M F, AGUIAR P M Q, et al. D-ADMM:A communication-efficient distributed algorithm for separable optimization[J]. IEEE Transactions on Signal Processing, 2013, 61(10):2718-2723.
[36] HONG M. A distributed, asynchronous and incremental algorithm for nonconvex optimization:An ADMM based approach[J]. IEEE Transactions on Control of Network Systems, 2018, 5(3):935-945.
[37] SHI W, LING Q, WU G, et al. EXTRA:An exact first-order algorithm for decentralized consensus, optimization[J]. SIAM Journal on Optimization, 2014, 25(2):944-966.
[38] ZENG J, YIN W. On nonconvex decentralized gradient descent[J]. IEEE Transactions on Signal Processing, 2018, 66(11):2834-2848.
[39] LI B, CEN S, CHEN Y, et al. Communication-efficient distributed optimization in networks with gradient tracking and variance reduction[DB/OL]. arXiv preprint:1909.05844,2019.
[40] VARAGNOLO D, ZANELLA F, CENEDESE A, et al. Newton-Raphson consensus for distributed convex optimization[J]. IEEE Transactions on Automatic Control, 2016, 61(4):994-1009.
[41] LIU Q, WANG J. A second-order multi-agent network for bound-constrained distributed optimization[J]. IEEE Transactions on Automatic Control, 2015, 60(12):3310-3315.
[42] STELLA L, THEMELIS A, PATRINOS P. Newton-type alternating minimization algorithm for convex optimization[J]. IEEE Transactions on Automatic Control, 2019, 64(2):697-711.
[43] TANG Y, LI N. Distributed zero-order algorithms for nonconvex multi-agent optimization[C]//2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2019:781-786.
[44] PANG Y, HU G. Exact convergence of gradient-free distributed optimization method in a multi-agent system[C]//2018 IEEE Conference on Decision and Control (CDC). Piscataway:IEEE Press, 2018:5728-5733.
[45] DING J, YUAN D, JIANG G, et al. Distributed quantized gradient-free algorithm for multi-agent convex optimization[C]//2017 29th Chinese Control and Decision Conference (CCDC), 2017:6431-6435.
[46] SHI W, LING Q, WU G, et al. A proximal gradient algorithm for decentralized composite optimization[J]. IEEE Transactions on Signal Processing, 2015, 63(22):6013-6023.
[47] MOKHTARI A, RIBEIRO A. DSA:Decentralized double stochastic averaging gradient algorithm[C]//2015 49th Asilomar Conference on Signals, Systems and Computers, 2015:406-410.
[48] CHEN A I, OZDAGLAR A. A fast distributed proximal-gradient method[C]//2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2012:601-608.
[49] JAKOVETIC D, XAVIER J, MOURA J M F. Fast distributed gradient methods[J]. IEEE Transactions on Automatic Control, 2014, 59(5):1131-1146.
[50] QU G, LI N. Accelerated distributed Nesterov gradient descent[J]. IEEE Transactions on Automatic Control, 2020, 65(6):2566-2581.
[51] CAI Z, WANG L, ZHAO J, et al. Virtual target guidance-based distributed model predictive control for formation control of multiple UAVs[J]. Chinese Journal of Aeronautics, 2020, 33(3):293-312.
[52] LU J, TANG C Y. Zero-gradient-sum algorithms for distributed convex optimization:The continuous-time case[J]. IEEE Transactions on Automatic Control, 2012, 57(9):2348-2354.
[53] ZENG X, YI P, HONG Y, et al. Distributed continuous-time algorithms for nonsmooth extended monotropic optimization problems[J]. SIAM Journal on Control and Optimization, 2018, 56(6):3973-3993.
[54] LIN P, REN W, FARRELL J A. Distributed continuous-time optimization:Nonuniform gradient gains, finite-time convergence, and convex constraint set[J]. IEEE Transactions on Automatic Control, 2017, 62(5):2239-2253.
[55] HANNA S, YAN H, CABRIC D. Distributed UAV placement optimization for cooperative line-of-sight MIMO communications[C]//2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Piscataway:IEEE Press, 2019:4619-4623.
[56] JOHANSSON B, RABI M, JOHANSSON M. A randomized incremental subgradient method for distributed optimization in networked systems[J]. SIAM Journal on Optimization, 2009, 20(3):1157-1170.
[57] NEDIC A, BERTSEKAS D P, BORKAR V S. Distributed asynchronous incremental subgradient methods[J]. Studies in Computational Mathematics, 2001, 8:381-407.
[58] WANG J, ELIA N. A control perspective for centralized and distributed convex optimization[C]//2011 50th IEEE Conference on Decision and Control and European Control Conference. Piscataway:IEEE Press, 2011:3800-3805.
[59] YAO L, YUAN Y, SUNDARAM S, et al. Distributed finite-time optimization[C]//2018 IEEE 14th International Conference on Control and Automation (ICCA). Piscataway:IEEE Press, 2018:147-154.
[60] NECOARA I, DUMITRACHE I, SUYKENS J A K. Fast primal-dual projected linear iterations for distributed consensus in constrained convex optimization[C]//49th IEEE Conference on Decision and Control (CDC). Piscataway:IEEE Press, 2010:1366-1371.
[61] NIU Y, WANG H, WANG Z, et al. Primal-dual stochastic distributed algorithm for constrained convex optimization[J]. Journal of the Franklin Institute, 2019, 356(16):9763-9787.
[62] GU C, WU Z, LI J. Regularized dual gradient distributed method for constrained convex optimization over unbalanced directed graphs[J]. Numerical Algorithms, 2020, 84(1):91-115.
[63] SANEI F S. A gradient-based alternating minimization approach for optimization of the measurement matrix in compressive sensing[J]. Signal Processing, 2012, 92(4):999-1009.
[64] BERTIZZOLO L, DORO S, FERRANTI L, et al. Swarm-control:An automated distributed control framework for self-optimizing drone networks[DB/OL]. arXiv preprint:2005.09781,2020.
[65] BOYD S, PARIKH N, CHU E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations & Trends in Machine Learning, 2010, 3(1):1-122.
[66] WEI E, OZDAGLAR A. On the O(1/k) convergence of asynchronous distributed alternating direction method of multipliers[C]//IEEE Global Conference on Signal and Information Processing. Piscataway:IEEE Press, 2013:551-554.
[67] LIU C L, LIN C Y, TOMIZUKA M. The convex feasible set algorithm for real time optimization in motion planning[J]. SIAM Journal on Control & Optimization, 2018, 56(4):2712-2733.
[68] JAVIER A M, EDUARDO M, TOBIAS N, et al. Distributed multi-robot formation control in dynamic environments[J]. Autonomous Robots, 2019(43):1079-1100.
[69] SRIVASTAVA K, NEDIC A. Distributed asynchronous constrained stochastic optimization[J]. IEEE Journal of Selected Topics in Signal Processing, 2011, 5(4):772-790.
[70] LOU Y, SHI G, JOHANSSON K H, et al. Approximate projected consensus for convex intersection computation:Convergence analysis and critical error angle[J]. IEEE Transactions on Automatic Control, 2014, 59:1722-1736.
[71] ZHU M, MARTINEZ S. On distributed convex optimization under inequality and equality constraints[J]. IEEE Transactions on Automatic Control, 2012, 57(1):151-164.
[72] DAI R. Three-dimensional aircraft path planning based on nonconvex quadratic optimization[C]//2014 American Control Conference. Piscataway:IEEE Press, 2014:4561-4566.
[73] ZHU Z, LI Q, YANG X, et al. Distributed low-rank matrix factorization with exact consensus[C]//Advances in Neural Information Processing Systems, 2019, 32:8422-8432.
[74] SWENSON B, MURRAY R, KAR S, et al. Distributed stochastic gradient descent and convergence to local minima[DB/OL]. arXiv preprint:2003.02818,2020.
[75] ZHOU F, CONG G. On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization[C]//Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018:3219-3227.
[76] WANG W R, SREBRO N. Stochastic nonconvex optimization with large minibatches[DB/OL]. arXiv preprint:1709.08728,2017.
[77] HUO Z Y, HUANG H. Asynchronous stochastic gradient descent with variance reduction for non-convex optimization[DB/OL]. arXiv preprint:1604.03584,2016.
[78] LIAN X, ZHANG C, ZHANG H, et al. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent[C]//Advances in Neural Information Processing Systems, 2017:5330-5340.
[79] ZHANG J, YOU K. Decentralized stochastic gradient tracking for non-convex empirical risk minimization[DB/OL]. arXiv preprint:1909.02712,2019.
[80] HONG M. Decomposing nonconvex problems using a proximal primal-dual approach:Algorithms, convergence, and applications[DB/OL]. arXiv preprint:1604.00543,2016.
[81] BOLTE J, SABACH S, TEBOULLE M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems[J]. Mathematical Programming, 2014, 2:459-494.
[82] POCK T, SABACH S. Inertial proximal alternating linearized minimization (IPALM) for nonconvex and nonsmooth problems[J]. SIAM Journal on Imaging Sciences, 2016, 9(4):1756-1787.
[83] DRIGGS D, TANG J, LIANG J, et al. Spring:A fast stochastic proximal alternating method for non-smooth non-convex optimization[DB/OL]. arXiv preprint:2002.12266,2020.
[84] PAN T, LIU J, WANG J. D-SPIDER-SFO:A decentralized optimization algorithm with faster convergence rate for nonconvex problems[C]//The Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020:1619-1626.
[85] SU W, BOYD S, CANDES E J. A differential equation for modeling Nesterov's accelerated gradient method:Theory and insights[J]. Advances in Neural Information Processing Systems, 2015, 3(1):2510-2518.
[86] SCIEUR D, ROULET V, BACH F, et al. Integration methods and optimization algorithms[C]//Advances in Neural Information Processing Systems, 2017:1109-1118.
[87] LABORDE M, OBERMAN A M. A Lyapunov analysis for accelerated gradient methods:From deterministic to stochastic case[DB/OL]. arXiv preprint:1908.07861,2019.
[88] CHEN R J, YANG T, CHAI T Y. Distributed accelerated optimization algorithms:Insights from an ODE[J]. Science China Technological Sciences, 2020, 63:1647-1655.
[89] ZHANG J, URIBE C A, MOKHTARI A, et al. Achieving acceleration in distributed optimization via direct discretization of the heavy-ball ODE[C]//2019 American Control Conference (ACC), 2019.
[90] XU J, TIAN Y, SUN Y, et al. Accelerated primal-dual algorithms for distributed smooth convex optimization over networks[DB/OL]. arXiv preprint:1910.10666,2019.
[91] ZENG X, LEI J, CHEN J. Dynamical primal-dual accelerated method with applications to network optimization[DB/OL]. arXiv preprint:1912.03690,2019.
[92] XIN R, KHAN U A, KAR S. Variance-reduced decentralized stochastic optimization with accelerated convergence[DB/OL]. arXiv preprint:1912.04230,2019.
[93] LEI J, YI P, CHEN J, et al. A communication-efficient linearly convergent algorithm with variance reduction for distributed stochastic optimization[C]//2020 European Control Conference (ECC), 2020:1250-1255.
[94] LEI J, YI P, CHEN J, et al. Linearly convergent algorithm with variance reduction for distributed stochastic optimization[DB/OL]. arXiv preprint:2002.03269,2020.
[95] NEDIC A, OLSHEVSKY A. Distributed optimization over time-varying directed graphs[J]. IEEE Transactions on Automatic Control, 2014, 60(3):601-615.
[96] SUN Y, SCUTARI G, PALOMAR D. Distributed nonconvex multiagent optimization over time-varying networks[C]//2016 50th Asilomar Conference on Signals, Systems and Computers, 2016:788-794.
[97] ROGOZIN A, URIBE C A, GASNIKOV A V, et al. Optimal distributed convex optimization on slowly time-varying graphs[J]. IEEE Transactions on Control of Network Systems, 2020, 7(2):829-841.
[98] SCOY B V, LESSARD L. A distributed optimization algorithm over time-varying graphs with efficient gradient evaluations[C]//8th IFAC Workshop on Distributed Estimation and Control in Networked Systems, 2019:357-362.
[99] LORENZO P D, SCUTARI G. NEXT:In-network nonconvex optimization[J]. IEEE Transactions on Signal and Information Processing over Networks. 2016, 2(2):120-136.
[100] BERTSEKAS D P, TSITSIKLIS J N. Parallel and distributed computation:Numerical methods[M]. Nashua:Athena Scientific, 2015:425-568.
[101] SRIVASTAVA K, NEDIC A. Distributed asynchronous constrained stochastic optimization[J]. Selected Topics in IEEE Journal of Signal Processing, 2011, 5(4):772-790.
[102] WU T Y, KUN Y, QING L, et al. Decentralized consensus optimization with asynchrony and delays[J]. IEEE Transactions on Signal and Information Processing over Networks, 2018, 4(2):293-307.
[103] AGARWAL A, DUCHI J C. Distributed delayed stochastic optimization[C]//2012 IEEE 51st IEEE Conference on Decision and Control (CDC). Piscataway:IEEE Press, 2012:5451-5452.
[104] NEDIC A, OLSHEVSKY A, RABBAT M G. Network topology and communication-computation tradeoffs in decentralized optimization[J]. Proceedings of the IEEE, 2018, 106(5):953-976.
[105] GAUTAM A, VELUVOLU K C, SOH Y C. Communication-computation tradeoff in distributed consensus optimization for MPC-based coordinated control under wireless communications[J]. Journal of the Franklin Institute, 2017, 354(9):3654-3677.

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

References