Research On Information Exchange Topology Optimization Problem Of UAV Formation During Formation Keeping

The formation flight of unmanned aerial vehicles （UAV） is currently a hot research topic in the field of UAV, which has a widespread application prospect in both military and civilian fields such as target reconnaissance, target search, target tracking, target attack, UAV aerial refueling and so on. It can effectively expand the reconnaissance and search range of UAV formation, improve the recognition rate of the target, improve the positioning accuracy of the target, improve the damage to the target, reduce the fuel consumption of UAV formation, and lay a solid foundation for the UAV aerial refueling technology, so it has very important theoretical and practical significance.At present, the research of UAV formation flight is still in the stage of exploration and development, and there are many key theoretical and technical problems to besolved. This dissertation is devoted to solving the information exchange topology optimization problem of UAV formation during formation keeping in them. Based on the models and methods of network optimization in operations research, this dissertation makes a deep study of this problem. This dissertation firstly decomposes and models this complex problem from several different perspectives, and then focuses on three key sub problems in them. The main completed work and innovation points are as follows:（1） The information exchange topology optimization problem of UAV formation during formation keeping is analyzed profoundly.The relevant important elements of the problem are analyzed, and the corresponding formal description models are established. The definition of this optimization problem is given, in which the constraints of this optimization problem are classified as the constraint of formation control methods, the constraint of formation leaders and the constraint of faults. From the perspective of the formation control method used by the UAV formation, this optimization problem is decomposed into six sub problems: the information exchange topology optimization problem of leader-follower formation during formation keeping, the information exchange topology optimization problem of consensus-based formation during formation keeping, the information exchange topology optimization problem of rigid formation during formation keeping, the information exchange topology optimization problem of persistent formation during formation keeping, the information exchange topology optimization problem of virtual structure formation during formation keeping, and the information exchange topology optimization problem of behavioral formation during formation keeping. Moreover, the first two sub problems are modeled as the minimum cost arborescence （MCA） model,the middle two sub problems are modeled as the optimal persistent graph （OPG） model,and the last two sub problems are modeled as the Traveling salesman problem （TSP）model. From the perspective of whether the UAV formation encounters some faults during formation keeping, this optimization problem is decomposed into two sub problems: the information exchange topology optimization problem of UAV formation during formation keeping under the condition of no fault, and the information exchange topology optimization problem of UAV formation during formation keeping under the condition of fault. Moreover, from the perspective of whether or not to allow the UAV position reconfiguration, the latter sub problem is further decomposed into the information exchange topology reconfiguration problem of UAV formation during formation keeping under the condition of fault, and the information exchange topology re-optimization problem of UAV formation during formation keeping under the condition of fault.（2） The information exchange topology optimization problem of leader-follower formation during formation keeping is researched systematically.Aiming at the information exchange topology optimization problem of leader-follower formation under the condition of no fault, an information exchange topology optimization algorithm based on MCA is proposed, and the correctness of this algorithm is proved theoretically. Compared with the existing algorithms, this algorithm can choose the most suitable formation shape position for each UAV, can automatically select the most appropriate UAV as the formation leader, can ensure that the formation communication cost of the information exchange topology is the smallest, and has a lower time complexity. Aiming at the information exchange topology optimization problem of leader-follower formation under the condition of fault, three algorithms are proposed. Firstly, an information exchange topology reconfiguration algorithm based on MCA is proposed. Compared with the existing algorithms, this algorithm can deal with more types of faults, can ensure that the formation communication cost of the reconfigured information exchange topology is the smallest, and has a lower time complexity. Secondly, an information exchange topology re-optimization algorithm based on UAV position reconfiguration and MCA （PR_MCA） is proposed. Compared with the existing algorithms, this algorithm can get the global optimal re-optimized information exchange topology for small-scale UAV formation, can be applied to any type of UAV formation shape. Finally, a heuristic information exchange topology re-optimization algorithm is proposed, which can get a sub optimal re-optimized information interaction topology in a short time to meet the computational time requirements of large-scale UAV formation.（3） The information exchange topology optimization problem of two-dimensional（2D） persistent formation during formation keeping is researched systematically.Aiming at the information exchange topology optimization problem of 2D persistent formation under the condition of no fault, an information exchange topology optimization algorithm based on 2D optimal persistent graph （2DOPG） is proposed, and the correctness of this algorithm is proved theoretically. Compared with the existing algorithms, this algorithm can choose the most suitable formation shape position for each UAV, can automatically select the most appropriate UAV as the formation leader,can ensure that the formation communication cost of the information exchange topology is the smallest, and has a lower time complexity. Aiming at the information exchange topology optimization problem of 2D persistent formation under the condition of fault,which has no relevant research literatures at present, three algorithms are proposed.Firstly, an information exchange topology reconfiguration algorithm based on 2DOPG is proposed. This algorithm can get the optimal reconfigured information exchange topology quickly. Secondly, an information exchange topology re-optimization algorithm based on UAV position reconfiguration and 2DOPG （PR₂DOPG） is proposed. This algorithm can get the global optimal re-optimized information exchange topology for small-scale UAV formation, can be applied to any type of UAV formation shape. Finally, a heuristic information exchange topology re-optimization algorithm is proposed, which can get a sub optimal re-optimized information interaction topology in a short time to meet the computational time requirements of large-scale UAV formation.（4） The information exchange topology optimization problem of three-dimensional（3D） persistent formation during formation keeping is researched systematically.Aiming at the information exchange topology optimization problem of 3D persistent formation under the condition of no fault,an information exchange topology optimization algorithm based on 3D optimal persistent graph （3DOPG） is proposed, and the correctness of this algorithm is proved theoretically. Compared with the existing algorithms, this algorithm can choose the most suitable formation shape position for each UAV, can automatically select the most appropriate UAV as the formation leader,can ensure that the formation communication cost of the information exchange topology is the smallest, and has a lower time complexity. Aiming at the information exchange topology optimization problem of 3D persistent formation under the condition of fault,which has no relevant research literatures at present, three algorithms are proposed.Firstly, an information exchange topology reconfiguration algorithm based on 3DOPG is proposed. This algorithm can get the optimal reconfigured information exchange topology quickly. Secondly, an information exchange topology re-optimization algorithm based on UAV position reconfiguration and 3DOPG （PR₃DOPG） is proposed. This algorithm can get the global optimal re-optimized information exchange topology for small-scale UAV formation, can be applied to any type of UAV formation shape. Finally, a heuristic information exchange topology re-optimization algorithm is proposed, which can get a sub optimal re-optimized information interaction topology in a short time to meet the computational time requirements of large-scale UAV formation.