CN115525061A - Multi-unmanned aerial vehicle cooperative control method based on graph theory - Google Patents

Abstract

The invention discloses a multi-unmanned aerial vehicle cooperative control method based on graph theory, which comprises the following steps: s1, determining a communication network diagram of the multiple unmanned aerial vehicles according to communication relations among the unmanned aerial vehicles; s2, generating a multi-unmanned-vehicle control relation tree through a communication network diagram; s3, determining a reference point for controlling the relative motion of each unmanned aerial vehicle through the control relation tree generated in the S2; and S4, determining the control relation among all unmanned aerial vehicles, and realizing the cooperative control of the multiple unmanned aerial vehicles. And S5, when the unmanned aerial vehicles participating in the cooperative task are abnormal, the control relation tree changes, some reference points without relative motion control of the unmanned aerial vehicles are generated, and the control relation tree is reconstructed to regenerate to realize cooperative control. The spanning tree algorithm can automatically and quickly obtain the control structures of all unmanned aerial vehicles, and realizes the quick control of the unmanned aerial vehicle swarm and the quick re-control when a certain unmanned aerial vehicle breaks down or is abnormal.

Description

A Cooperative Control Method of Multi-UAV Based on Graph Theory

technical field

The invention relates to the technical field of unmanned aerial vehicles, in particular to a multi-unmanned aerial vehicle cooperative control method based on graph theory.

Background technique

The formation control methods of multi-UAVs include Leader-Followe, behavior-based methods, virtual structure methods, artificial potential field methods, distributed control, predictive control, and methods of knowledge analysis and design using graph theory, etc. Leader-Follower is the most widely used, and its structure is simple and easy to understand. However, since the behavior of the entire formation is only determined by the Leader, there is no formation feedback. When the Leader fails, the entire system may be paralyzed.

The most basic problem involved in the formation maintenance of multi-UAV formation has two aspects: one is the decision-making problem in formation maintenance, that is, to decide how to carry out formation maintenance according to the internal and external conditions of the entire formation. The second is the controller design in formation keeping, including close formation keeping control and large formation keeping control.

In the centralized control mode, formation maintenance needs to follow the UAV to quickly solve the optimal waypoint and respond to formation control instructions in real time. The formation control of two UAVs is studied, and the formation control structure adopts centralized control, that is, the leader-follow method. Taking the leader aircraft as a reference point, the formation maintenance controller is designed by using model predictive control, and the formation control is realized by controlling the following UAV.

Then it can be controlled by establishing the leading-following motion model of the two aircraft, and then it can be extended to multi-UAV cooperative control through the method of hierarchical reference. But how to make each UAV have one and only one reference point according to the communication network between UAVs is the focus of realizing the above-mentioned layered control structure, and it is an important step to realize the expansion from two-machine cooperative control to multi-machine cooperative control .

At the same time, because the area where UAVs fly in coordinated formation is a battlefield threat, how to generate a new control structure network should also be considered when UAVs may be attacked or encounter sudden failures.

The present invention is proposed aiming at the above-mentioned deficiencies existing in the prior art.

Contents of the invention

In view of the above problems, the object of the present invention is to provide a graph theory-based multi-UAV cooperative control method for the generation and reconstruction of the multi-UAV cooperative control structure using a related method of graph theory.

In order to realize the purpose of the invention of the present invention, the technical solution provided by the present invention is a kind of multi-unmanned aerial vehicle cooperative control method based on graph theory, comprising the following steps:

Step S1, determine the communication network diagram of the multi-UAV through the communication relationship between the various UAVs of the multi-UAV;

Step S2, generating a multi-UAV control relationship tree through the communication network diagram;

Step S3, by the control relationship tree that step S2 generates, determine the reference point of the relative motion control of each unmanned aerial vehicle;

Step S4, determining the control relationship among the various UAVs to realize the coordinated control of multiple UAVs.

Preferably, in the step S2, the generation of the control relationship tree adopts the breadth-first spanning tree algorithm, and the nodes are sequentially expanded to the extent close to the starting node. Before searching any node of the next layer, the search must be completed The nodes in this layer realize the transformation from the cooperative communication relationship of drones to the control relationship.

Preferably, the specific steps of the described breadth-first spanning tree algorithm are:

Step S21, set up two linked lists named as Open and Closed table, wherein Open represents the node that does not expand, and Closed represents the node that has expanded;

Step S22, taking the pilot UAV of the entire coordinated formation as the starting node and as the root of the control tree;

Step S23, put the node in the Open list;

Step S24, judging whether the length of the Closed list is the number of drones, if so, then terminate;

Step S25, move the node data in the Open table to the Closed table, use this node as the node of the control tree, the node of the next layer of the node pointed to by its pointer;

Step S26, expand the successor node of this node, if this node exists in the Closed list, then do not expand, if do not exist in the Closed list, then put to the end of the Open list, and provide the pointer that gets back to this node;

Step S27, return to step S24.

Preferably, step S5 is also included. When the UAVs participating in the cooperative task are abnormal, the control relationship tree changes, and some UAVs do not have reference points for relative motion control. At this time, the control relationship tree is regenerated by reconstructing Realize collaborative control.

Preferably, in the step S5, the specific processing method for the abnormality of the UAV in different positions includes:

S51, when the pilot drone of the entire formation is damaged, the pilot drone must be reselected, and the spanning tree algorithm is called to reconstruct the control relationship tree;

S52, when the unmanned aerial vehicle in the middle of the top of the control tree and the bottom layer fails, the unmanned aerial vehicle in the child node of the failed unmanned aerial vehicle can quickly find the unmanned aerial vehicle communicating with it, and use it as a child node of the unmanned aerial vehicle to Realize rapid reconstruction. If the UAV communicating with it cannot be found, the control relationship tree will be regenerated through the spanning tree algorithm in S51;

S53, when the UAV at the bottom of the control tree is damaged, the existing control relationship tree is not affected, and no processing is required.

The beneficial effects of the present invention include:

The UAV node of the present invention has and only one parent node in the UAV control relationship tree, which means that each UAV has and only has one reference UAV, except that the pilot UAV of the entire formation passes through the navigation In addition to the system tracking route, other drones can establish relative motion equations through their unique corresponding pilot drones, and then perform coordinated control to achieve multi-machine coordination. Because the time complexity of the spanning tree algorithm is only O(N), the control structure of all unmanned aerial vehicles can be obtained automatically and quickly through the above spanning tree algorithm of the present invention, so as to realize the rapid control of the unmanned aerial vehicle bee colony and in a certain Quick re-control in the event of drone failure or abnormality.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. Those skilled in the art can also obtain other drawings based on these drawings without creative work.

Fig. 1 is a schematic diagram of the storage structure of the multi-UAV communication network structure diagram;

Fig. 2 is a schematic diagram of the storage structure of the control relationship tree of the present invention;

Fig. 3 is the generation schematic diagram of the control relationship tree of the present invention

Fig. 4 is the flow chart of control relation tree generation of the present invention;

FIG. 5 is a schematic diagram of the reconstruction of the control relationship tree in the present invention.

detailed description

The technical solutions in the embodiments of the present application will be clearly and completely described below in conjunction with the accompanying drawings.

Before the present invention is specifically set forth in conjunction with accompanying drawing, at first various nouns mentioned herein are defined as follows:

Definition 1: Graph

A graph G generally consists of two sets: a non-empty node set V and a finite edge set E, where edges refer to unordered pairs of different nodes. If V={v ₁ ,v ₂ ,…,v _n } is a set of n nodes, E={e ₁ ,e ₂ ,…,e _n } is a set of m edges, each edge Both are binary subsets {v _i , v _j } of the set V, where the cardinality n of the set V(G) represents the order of the graph, and the cardinality m of the set E(G) represents the scale of the graph. When the nodes in the set v _i and v _j form {v _i , v _j }∈E(G), or {v _i , v _j } is the edge of graph G, the node v _i and v _j are called adjacent, otherwise they are called non-adjacent.

Definition 2: Directed graph

When the edge set of a graph G is composed of ordered pairs of different nodes, the graph is called a directed graph.

Definition 3: Connected and Disconnected Graphs

When an undirected graph G is reachable between any two vertices, the graph G is called a connected graph, otherwise it is called a disconnected graph.

Definition 3: Tree

A graph is said to be acyclic if none of its subgraphs is a cycle. A connected acyclic graph is called a tree.

Definition 4: Spanning Tree

Assuming that graph G=(V,E) is a connected graph, when traversing graph G from any vertex in the graph, the edge set E(G) is divided into two sets A(G) and B(G). Among them, A(G) is the set of edges passed when traversing the graph, and B(G) is the set of edges not passed when traversing the graph. Obviously G ₁ =(V,A) is the spanning tree of the connected graph.

Because when UAVs perform cooperative target tracking tasks, if UAVs are required to have a decentralized control capability, there should be a certain amount of information exchange and sharing between UAVs, so as to facilitate autonomous cooperation of UAVs, and also That is, there is a certain communication relationship within the drone. Then, the communication network diagram represents the information exchange and sharing relationship between the drones, so that each drone in the system is a node in the communication network diagram, and the information sharing relationship between drones is an edge in the communication network graph.

Assuming that the communication system of the UAV constitutes a communication network graph G, then G(V,E) is a directed graph, and the edge V={v ₁ ,v ₂ ,…,v _n } represents the cooperative UAV node, E={e ₁ ,e ₂ ,…,e _n } indicates the communication relationship between them, {v _i ,v _j } indicates that there is information transmission between robot i and drone j, and the direction of the arrow is the direction of information direction of transmission. Because the scale is not large, the graph can be stored in a 0-1 matrix, where 0 indicates that there is no communication relationship between the two drones, and 1 indicates that there is a communication relationship between the two drones. As shown in Figure 1, the left picture in Figure 1 is a communication network structure diagram between UAVs, and the right picture in Figure 1 is a matrix representing the communication relationship.

The cooperative control structure of UAVs generally adopts a hierarchical structure, and a tree is a better choice to represent the hierarchical structure, so the control relationship between UAV clusters can be represented by a tree, that is, through UAV control Relationship tree to describe the control relationship between drones. In general, the structure of the tree may be represented by a double linked list, as shown in Figure 2.

After the above description, the specific implementation steps of the present invention are described as follows:

A kind of multi-UAV cooperative control method based on graph theory of the present invention comprises the following steps:

Step S1, determine the communication network diagram of the multi-UAV through the communication relationship between the various UAVs of the multi-UAV;

Step S2, generate a multi-UAV control relationship tree through the communication network diagram; refer to Figure 3;

In the step S2, the generation of the control relationship tree adopts the breadth-first spanning tree algorithm, and the nodes are sequentially expanded to the degree close to the starting node. Before searching any node of the next layer, the search must be completed The node realizes the transformation from the cooperative communication relationship of UAVs to the control relationship.

Specifically: the specific steps of the spanning tree algorithm are (refer to Figure 4):

Step S21, set up two linked lists named as Open and Closed table, wherein Open represents the node that does not expand, and Closed represents the node that has expanded;

Step S22, taking the pilot UAV of the entire coordinated formation as the starting node and as the root of the control tree;

Step S23, put the node in the Open list;

Step S24, judging whether the length of the Closed list is the number of drones, if so, then terminate;

Step S25, move the node data in the Open table to the Closed table, use this node as the node of the control tree, the node of the next layer of the node pointed to by its pointer;

Step S26, expand the successor node of this node, if this node exists in the Closed list, then do not expand, if do not exist in the Closed list, then put to the end of the Open list, and provide the pointer that gets back to this node;

Step S27, return to step S24.

Step S3, by the control relationship tree that step S2 generates, determine the reference point of the relative motion control of each unmanned aerial vehicle;

Step S4, determining the control relationship among the various UAVs to realize the coordinated control of multiple UAVs.

Step S5, when the UAVs participating in the cooperative task are abnormal, the control relationship tree changes, and some UAVs do not have reference points for relative motion control. At this time, the control relationship tree is regenerated to realize cooperative control.

Referring to Fig. 5, in step S5, the specific processing methods for abnormalities of drones in different positions include:

S51, when the pilot drone of the entire formation is damaged, the pilot drone must be reselected, and the spanning tree algorithm is called to reconstruct the control relationship tree;

S52, when the unmanned aerial vehicle in the middle of the top of the control tree and the bottom layer fails, the unmanned aerial vehicle in the child node of the failed unmanned aerial vehicle can quickly find the unmanned aerial vehicle communicating with it, and use it as a child node of the unmanned aerial vehicle to Realize rapid reconstruction. If the UAV communicating with it cannot be found, the control relationship tree will be regenerated through the spanning tree algorithm in S51;

S53, when the UAV at the bottom of the control tree is damaged, the existing control relationship tree is not affected, and no processing is required.

The cooperative control method of multi-UAV through the above steps, its cooperative consistency is proved as follows:

The consistency of multi-UAS means that multi-UAS can complete the mission as a whole rather than some individual ones. Although there are conflicts and competitions among various UAVs, the system can meet the requirements of the overall control goal after a period of coordination.

There is a basic theorem for the consistency convergence problem of the robot network: the necessary and sufficient condition for the multi-robot system to achieve the global consistency convergence of information flow is if and only if its communication network graph has a spanning tree.

As a special case of the multi-robot system, the multi-UAV system is also applicable to the above theorem. For the above extension method, as long as the original communication network diagram has a spanning tree, then the conversion from the communication network diagram to the control tree can be realized. The generated control relationship tree itself is a tree, and it is its own spanning tree, so after conversion, it obviously also meets the convergence requirements of coordination and consistency. Therefore, for the multi-UAV system with its own communication network that has coordination and consistency convergence, the new control relationship tree generated by the above method still meets the global consistency convergence.

The effectiveness analysis of the multi-UAV cooperative control method through the above steps is as follows:

After the above expansion, the drone node has one and only one parent node in the drone control relationship tree, which means that each drone has one and only one reference drone, except for the pilot drone of the entire formation In addition to tracking the route through the navigation system, other UAVs can establish relative motion equations through their unique corresponding pilot UAVs, and then perform coordinated control to achieve multi-machine coordination. Because the time complexity of the spanning tree algorithm is only O(N), the control structure of all UAVs can be automatically and quickly obtained through the above tree generation algorithm.

The described embodiments are only some of the embodiments of the present application, not all of them. Based on the embodiments in this application, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the scope of protection of this application.

Claims (5)

1. A multi-unmanned aerial vehicle cooperative control method based on graph theory is characterized by comprising the following steps:

s1, determining a communication network diagram of the multiple unmanned aerial vehicles according to communication relations among the unmanned aerial vehicles;

s2, generating a multi-unmanned-vehicle control relation tree through a communication network diagram;

s3, determining a reference point for controlling the relative motion of each unmanned aerial vehicle through the control relation tree generated in the S2;

and S4, determining the control relation among all unmanned aerial vehicles, and realizing the cooperative control of the multiple unmanned aerial vehicles.

2. The method according to claim 1, wherein in step S2, the control relationship tree is generated by a breadth-first spanning tree algorithm, the nodes are sequentially expanded to a degree close to the starting node, and before any node in the next layer is searched, the node in the current layer must be searched, so that the conversion from the communication relationship of the unmanned aerial vehicle cooperation to the control relationship is realized.

3. The method for cooperative control of multiple unmanned aerial vehicles based on graph theory according to claim 2, wherein the breadth-first spanning tree algorithm comprises the following specific steps:

step S21, establishing two linked lists named as Open and Closed lists, wherein Open represents an unexpanded node, and Closed represents an expanded node;

s22, taking the piloted unmanned aerial vehicle of the whole cooperative formation as an initial node and as a root of a control tree;

step S23, the node is put in an Open table;

step S24, judging whether the length of the Closed table is the number of the unmanned aerial vehicles, and if so, terminating;

step S25, moving the node data in the Open table to the Closed table, taking the node as the node of the control tree, and the node of the next layer of the node pointed by the pointer;

step S26, expanding the successor node of the node, if the node exists in the Closed table, not expanding, if the node does not exist in the Closed table, placing the successor node to the end of the Open table, and providing a pointer returning to the node;

step S27, return to step S24.

4. The method for cooperative control of multiple unmanned aerial vehicles based on graph theory according to claim 3,

and S5, when the unmanned aerial vehicle participating in the cooperative task is abnormal, the control relation tree changes, some reference points without relative motion control of the unmanned aerial vehicle are generated, and the control relation tree is reconstructed to regenerate to realize cooperative control.

5. The method for cooperative control of multiple unmanned aerial vehicles based on graph theory according to claim 4, wherein in the step S5, the specific processing method for the abnormality of the unmanned aerial vehicles at different positions comprises:

s51, when the piloting unmanned aerial vehicles of the whole formation are damaged, the piloting unmanned aerial vehicles need to be reselected, and a spanning tree algorithm is called to reconstruct a control relation tree;

s52, when the unmanned aerial vehicle in the middle of the top end and the bottom layer of the control tree breaks down, the unmanned aerial vehicle in the sub-node of the broken unmanned aerial vehicle can quickly find the unmanned aerial vehicle communicated with the broken unmanned aerial vehicle and serve as the sub-node of the unmanned aerial vehicle to realize quick reconstruction, and if the unmanned aerial vehicle communicated with the broken unmanned aerial vehicle cannot be found, the control relation tree is regenerated through the spanning tree algorithm in S51;

s53, when the unmanned aerial vehicle at the bottom layer of the control tree is damaged, the existing control relation tree is not influenced, and processing is not needed.

Images