LIU Huaxian, LIU Feng, ZHANG Xuejun, GUAN Xiangmin, CHEN Jun. A Formation Reconfiguration Algorithm for Multi-UAVs Based on Distributed Cooperative Coevolutionary with an Adaptive Grouping Strategy[J]. Chinese Journal of Electronics, 2020, 29(5): 841-851. doi: 10.1049/cje.2020.07.006
Citation: LIU Huaxian, LIU Feng, ZHANG Xuejun, GUAN Xiangmin, CHEN Jun. A Formation Reconfiguration Algorithm for Multi-UAVs Based on Distributed Cooperative Coevolutionary with an Adaptive Grouping Strategy[J]. Chinese Journal of Electronics, 2020, 29(5): 841-851. doi: 10.1049/cje.2020.07.006

A Formation Reconfiguration Algorithm for Multi-UAVs Based on Distributed Cooperative Coevolutionary with an Adaptive Grouping Strategy

doi: 10.1049/cje.2020.07.006
Funds:  This work is supported by the National Natural Science Foundation of China (No.U1933130, No.U1533119, No.71731001) and the Major Project of Technological Innovation (No.2018AAA0100800).
More Information
  • Corresponding author: ZHANG Xuejun (corresponding author) was born in 1971. He received the B.E. degree in electronic engineering from Beihang University. He is a professor of Beihang University. His research interests include air traffic management and unmanned aircraft system operation. (
  • Received Date: 2018-08-01
  • Rev Recd Date: 2020-03-27
  • Publish Date: 2020-09-10
  • The Formation reconfiguration problem plays a crucial role in the implementation of complex tasks for multiple unmanned aerial vehicles, which attracted increasing attention in the past decade. Taking into consideration the control parameters and time discretization of the multi-UAVs in the 3 Dimensional (3-D) space, the formation reconfiguration problem can be formulated as a large-scale combinatorial optimization problem with complex constraints and tight couplings between variables. The problem results in the reduction in efficiency and effectiveness using classic bio-inspired algorithms. In this paper, a formation reconfiguration method based on cooperative coevolutionary algorithm is proposed along with a new decomposition strategy to improve the optimization capability and prevent premature convergence. In the proposed approach, variables of multi-UAV are divided into several sub-groups based on an adaptive grouping strategy. The proposed strategy groups the variables in order to better deal with the tight coupling among them, taking into account the variables' variance and multi-UAVs characteristics of the formation reconfiguration problem. Therefore, each subgroup can adopt the Self-adaptive differential evolution strategy with neighborhood search (SaNSDE) with the aim to optimize the UAV's control inputs using multithreaded programming. SaNSDE contributes to calculating the results in a fully distributed and paralleled manner. Optimal solution is then obtained through cooperation and coordination with all subcomponents. Simulation results based on extreme scenarios adopted by previous researches demonstrate that the proposed algorithm outperformed the existing approaches including Particle swarm optimization (PSO), Differential evolution (DE), and the cooperative coevolution algorithms with different well-known grouping strategies.
  • loading
  • FAN Bangkui, LI Yun, ZHANG Ruiyu, et al., "Review on the technological development and application of UAV systems", Chinese Journal of Electronics, Vol.29, No.2, pp.199-207, 2020.
    XIONG Wei, CHEN Zongji and ZHOU Rui, "Optimization of multiple flight vehicle formation reconfiguration using hybrid genetic algorithm", Acta Aeronautica et Astronautica Sinica, Vol.29, pp.209-214, 2008.
    K. L. Teo, C. J. Goh, K. H. Wong, et al., "A unified computational approach to optimal control problems", Harlow:Longman Scientific and Technical, 1991.
    Y. D. Lee, B. H. Lee and H. G. Kim, "An evolutionary approach for time optimal trajectory planning of a robotic manipulator", Information Sciences, Vol.113, No.3, pp.245-260, 1999.
    Y. Chen and Z. Wang, "Formation control:A review and a new consideration", IEEE/RSJ International Conference on Intelligent Robots & Systems, pp.3181-3186, 2005.
    W. Lin, "Distributed UAV formation control using differential game approach", Aerospace Science and Technology, Vol.35, No.1, pp.54-62, 2014.
    M. Radmanesh and M. Kumar, "Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming", Aerospace Science and Technology, Vol.50, pp.149-160, 2016.
    Z. Chao, L. Ming, Z. Shaolei, et al., "Collision-free UAV formation flight control based on nonlinear MPC", International Conference on Electronics, Communications and Control, pp.11-18, 2011.
    F. Augugliaro, A. P. Schoellig and D. R. Andrea, "Generation of collision-free trajectories for a quadcopter fleet:A sequential convex programming Approach", Proc. of IEEE International Conference on Intelligent Robots and Systems, pp.1917-1922, 2012.
    Alonso Mora, J. S. Baker and D. Rus, "Multi-robot navigation in formation via sequential convex programming", IEEE International Conference on Intelligent Robots and Systems, pp.4634-4641, 2015.
    ZHUGE Chengchen, CAI Yunfei and TANG Zhenmin, "A novel dynamic obstacle avoidance algorithm based on collision time histogram", Chinese Journal of Electronics, Vol.26, No.3, pp.522-529, 2017.
    L. Zhu, X. Cheng and F. G. Yuan, "A 3D collision avoidance strategy for UAV with physical constraints measurement", Journal of the International Measurement Confederation, Vol.77, pp.40-49, 2016.
    T. Furukawa, "Time-subminimal trajectory planning for discrete non-linear systems", Engineering Optimization, Vol.34, pp.219-243, 2002.
    K. Y. Lee and G. Dissanayake, "Numerical solution for a near minimum time trajectory for two coordinated manipulators", Engineering Optimization, Vol.30, pp.227-247, 1998.
    T. Furukawa, H. F. Durrant-Whyte, F. Bourgault, et al., "Time-optimal coordinated control of the relative formation of multiple vehicles", Proc. of IEEE International Symposium on Computational Intelligence in Robotics and Automation, Kobe, Japan, pp.259-264, 2003.
    T. Simeon, S. Leroy and J. P. Lauumond, "Path coordination for multiple mobile robots:A resolution-complete algorithm", IEEE Transactions on Robotics and Automation, Vol.18, pp.42-49, 2002.
    R. F. Saber, W. B. Dunbar and R. M. Murray, "Cooperative control of multi-vehicle systems using cost graphs and optimization", Proc. of American Control Conference, Denver, USA, pp.2217-2222, 2003.
    DUAN Haibin, GUAN Junma and LUO Delin, "Optimal formation reconfiguration Control of multiple UCAVs using improved particle swarm optimization", Journal of Bionic Engineering, Vol.5, No.4, pp.340-347, 2008.
    H. Duan, Q. Luo, Y. Shi, et al., "Hybrid particle swarm optimization and genetic algorithm for multi-UAV formation reconfiguration", IEEE Comp. Int. Mag, Vol.8, No.3, pp.16-27, 2013.
    J. K. Archibald, J. C. Hill, N. A. Jepsen, et al., "A satisficing approach to aircraft conflict resolution", IEEE Trans. Syst., Man, Cybern. C, Appl. Rev., Vol.38, No.4, pp.510-521, 2008.
    J. Kosecka, C. Tomlin, G. Pappas, and S. Sastry, "Generation of conflict resolution maneuvers for air traffic management", Proc. of IEEE/RSJ Int. Conf. Intell. Robots Syst., Grenoble, France, Vol.3, pp.1598-1603, 1997.
    X. J. Zhang, X. M. Guan, I. Hwang, et al., "A hybrid distribut-ed-centralized conflict resolution approach for multi-aircraft based on cooperative co-evolutionary", Science China Information Sciences, Vol.56, No.12, pp.1-16, 2013.
    R. L. Lv, X. M. Guan, X. Y. Li, et al., "A large-scale ight multi-objective assignment approach based on multi-island parallel evolution algorithm with cooperative coevolutionary", Science China Information Scienes, Vol.59, No.7, pp.1-17, 2016.
    X. M. Guan, X. J. Zhang, R. L. Lv, et al., "A large-scale multi-objective flights conflict avoidance approach supporting 4D trajectory operation", Science China Information Scienes, Vol.60, Article No.112202, 2017.
    DING Weiping, WANG Jiandong and GUAN Zhijin, "A novel minimum attribute reduction algorithm based on hierarchical elitist role model combining competitive and cooperative co-evolution", Chinese Journal of Electronics, Vol.22, No.4, pp.677-682, 2013.
    D. Sofge, K. D. Jong and A. Schultz, "A blended population approach to cooperative coevolution for decomposition of complex problems", Proc. of Congress on Evolutionary Computation, pp.413-418, 2012.
    T. Ray and X. Yao, "A cooperative coevolutionary algorithm with correlation based adaptive variable partitioning", Proc. of the Eleventh Congress on Evolutionary Computation, pp.983-989, 2009.
    M. N. Omidvar, X. D. Li and X. Yao, "Cooperative coevolution with delta grouping for large scale non-separable function optimization", Proc. of the IEEE Congress on Evolutionary Computation, pp.1762-1769, 2010.
    Y. Wang, B. Li and X. X. Lai, "Variance priority based cooperative co-evolution differential evolution for large scale global optimization", Proc. of IEEE Congress On Evolutionary Computation, pp.1232-1239, 2012.
    R. Storn and K. Price, "Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces", Journal of Global Optimization, Vol.11, No.4, pp.341-359, 1997.
    QI Wen, YANG Liang, CAI Yuncan, et al., "A survey of differential evolution algorithms", Pattern Recognition and Artificial Intelligence, Vol.21, No.4, pp.506-513, 2008.
    A. K. Qin and P. N. Suganthan, "Self-adaptive differential evolution algorithm for numerical optimization", Proc. of IEEE Congress on Evolutionary Computation, Vol.2, pp.1785-1791, 2005.
    P. N. Suganthan, N. Hansen, J. J. Liang, et al., "Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization", Technical Report, Nanyang Technological University, Singapore, 2005.
    YANG Zhenyu, TANG Ke and YAO Xin, "Large scale evolutionary optimization using cooperative coevolution", Information Sciences, Vol.178, pp.2985-2999, 2008.
  • 加载中


    通讯作者: 陈斌,
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (160) PDF downloads(92) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint