CN-122022264-A - Multi-frame large unmanned aerial vehicle task allocation method based on WI-CBBA algorithm

CN122022264ACN 122022264 ACN122022264 ACN 122022264ACN-122022264-A

Abstract

The invention belongs to the technical field of fixed wing unmanned aerial vehicle task planning, and relates to a task allocation method for a plurality of large unmanned aerial vehicles based on a WI-CBBA algorithm. The method comprises the steps of establishing a mathematical model of task allocation problems, then considering that an unmanned aerial vehicle executes tasks in an edge environment, filling a plurality of factors which influence task allocation benefits such as environmental mutation, change of situation and the like, improving a traditional consistency outsourcing algorithm, providing a weight time interval consistency wrapping algorithm, introducing an online task weight coefficient into a benefit function to represent the weight of the unmanned aerial vehicle to execute the tasks, and comprehensively considering two factors of distance and benefit by the task weight coefficient. The average value of the objective function solved by the improved CBBA algorithm is larger, and the convergence time is shorter. The method solves the task allocation problem in the multi-task scenario of the cooperative execution of the series of unmanned aerial vehicles, and realizes the rapid and accurate solution of the multi-unmanned aerial vehicle cooperative task allocation problem by utilizing an improved algorithm.

Inventors

WANG WEI
FU YANG
GAO CHI
LIU HUI
LIU YAN
ZHU ZIXUAN

Assignees

中国航空工业集团公司成都飞机设计研究所

Dates

Publication Date: 20260512
Application Date: 20251230

Claims (8)

1. A task distribution method for a plurality of large unmanned aerial vehicles based on WI-CBBA algorithm is characterized in that firstly, a mathematical model of task distribution problem is established, a weight time interval consistency package algorithm is provided, an online task weight coefficient is introduced into a benefit function to represent the weight of the unmanned aerial vehicle to execute tasks, the task weight coefficient comprehensively considers two factors of distance and benefit, the average value of an objective function solved by an improved CBBA algorithm is larger, and the convergence time is shorter.
2. The method of claim 1, comprising the steps of: s1, initializing task set parameters and unmanned aerial vehicle set information; s2, modeling a task allocation scene based on graph theory knowledge, establishing an objective function and constraint conditions thereof, and establishing a task allocation mathematical model; s3, judging a winner list set And winner bid sets Whether the task package set number is changed or not exceeds the maximum task number which can be executed by the unmanned aerial vehicle, if the task package set number is unchanged or reaches the maximum task number which can be executed by the unmanned aerial vehicle, the algorithm is proved to reach the convergence requirement, the result is directly output, and otherwise, the step S4 is skipped; S4, constructing a task package, and circularly traversing each unmanned aerial vehicle to select tasks; S5, conflict resolution is carried out, whether a plurality of unmanned aerial vehicles execute the same task exists or not is checked, if so, the unmanned aerial vehicle with the highest bid is selected to execute the task, and other unmanned aerial vehicles release the task and the subsequent tasks in the task package, and then the process returns to S4.
3. The method according to claim 2, wherein in S1, there is the following sub-steps: S11, defining the type, the number and the speed range of the unmanned aerial vehicle Fuel consumption Maximum number of tasks that can be performed And maximum range ; S12, defining the type, the number and the benefit of the tasks Discount factor And task time consumption 。
4. The method according to claim 2, wherein in S2, there is the following sub-steps: s21, assuming a task scene graph G is a square area of m multiplied by m, wherein n tasks to be executed are arranged in the G, and the union set of the n tasks is recorded as ; S22, use Indicating the execution order of tasks as tasks To task , Wherein (a) Indicating the execution order as Otherwise, 0; s23, defining edge sets Wherein Expressed in terms of task points And a task point Is a line segment of an endpoint of (a); S24, using task inclusion sets Representing greedy task based selection as a drone Distribution task of order, path list Is unmanned plane Order of execution of tasks, winning unmanned list Is that Corresponding winning drone number in (c); Is along a path list Unmanned plane According to the total income value of the execution task; S25, use Representative unmanned aerial vehicle To the target task point And define a new task revenue function as: , S26, use Representative task And uses Representative unmanned aerial vehicle Executing tasks At the cost of: , s27, according to the benefit function and the cost function, establishing an objective function as follows: , , S28, according to the maximum principle of the objective function, the established objective function and the constraint conditions thereof are as follows: ,, Wherein, the Representation unmanned aerial vehicle Completing a task The time required for this is set up and, Is unmanned plane From the previous task point to the next task point Is used for the time-critical period of (a), Is unmanned plane Executing tasks Time; Representation unmanned aerial vehicle Slave tasks Time of departure of previous task point, and unmanned aerial vehicle is limited Performing the task of meeting the time window constraint.
5. The method of claim 2, wherein in S4, there is the sub-step of: S41, iterating the last moment to obtain a data structure, and enabling the unmanned aerial vehicle to be A winning bid set, a task path set and a winning unmanned aerial vehicle set are used as the initial data of the iteration; , , , , S42, when the number of tasks in the task package is smaller than the upper limit of tasks executed by the unmanned aerial vehicle, starting circulation, and calculating the unmanned aerial vehicle Executing tasks Is the benefit value of (2) The potential new task is retrieved and verified for compliance with the assignment to the drone If meeting the conditions, and adding tasks Can give unmanned aerial vehicle The additional benefit is a task The highest bid value in the current task sequence, then the task is to Add to unmanned aerial vehicle Is a task sequence of (1); S43, if the unmanned aerial vehicle successfully bid on the task, arranging a new task at the optimal position of the task sequence through calculation; S44, updating a data structure comprising the unmanned aerial vehicle Is a task sequence of the shared vector; S45, when the number of tasks in the task package is equal to the upper limit of the tasks executed by the unmanned aerial vehicle, the cycle is ended, and a conflict resolution stage is entered.
6. The method according to claim 2, wherein in S5, there is the sub-step of: S51, detecting conflicts, namely determining any conflicts existing in task allocation, such as resource competition or task overlapping; S52, conflict analysis, namely analyzing the detected conflict, and determining the root cause of the conflict and the possibility of a solution; The method comprises the steps of S53, generating a proper solution based on a result of conflict analysis to eliminate or reduce task conflicts, excluding invalid and conflicting candidate tasks when screening tasks through a communication shared task information structure by the unmanned aerial vehicle, ensuring that a final task distribution result is not interfered, transmitting vectors of a winner list, a bid list and a timestamp between the unmanned aerial vehicles so as to cooperate with each other in a task distribution process, introducing a timestamp vector at the stage, recording the latest information updating time after information communication between the unmanned aerial vehicles, and using the latest information updating time as a vector stored in the distribution process by the unmanned aerial vehicle, wherein an updating formula of the timestamp vector is as follows: , In the formula, A time stamp vector representing an update after unmanned plane i communicates with unmanned plane k, where Representing the information reception time; indicating whether the unmanned aerial vehicle i and the unmanned aerial vehicle k can communicate, wherein the condition that the communication link can be established is equal to 1, and the condition that the communication link cannot be established is equal to 0; A timestamp vector which indicates that communication can be performed between the unmanned aerial vehicle i and the unmanned aerial vehicle m, and is updated after the unmanned aerial vehicle m and the unmanned aerial vehicle k communicate; s54, in the conflict resolution stage, when the unmanned aerial vehicle Receiving unmanned plane Information transmitted, among them At the time of, unmanned aerial vehicle Will utilize the known To determine which unmanned aerial vehicle's information is considered the most current information for the task.
7. The method of claim 6, wherein, for a task Unmanned aerial vehicle Three different operations may be selected: 1) Updating: , 2) Resetting , 3) Leave from , Unmanned plane Upon receiving the unmanned aerial vehicle Related tasks After the information of the table is obtained, corresponding actions are taken based on a consensus mechanism shown in the table, wherein the values of the first two columns in the table are respectively unmanned aerial vehicles And (3) with Evaluating a bid task identified The third column represents the unmanned aerial vehicle Actions that should be performed, wherein the default action is leave; if unmanned aerial vehicle A kind of electronic device And After negotiation by a consensus mechanism based on the following table, updating occurs, and then the task sequences of all unmanned aerial vehicles are dealt with And path order set In (1) And The affected task after the value update and the subsequent tasks are released and reset.
8. The method of claim 7, wherein after S55 the unmanned cluster agrees with the current task allocation scheme, the algorithm jumps to S4 again, adds the task released in the conflict resolution stage to the unmanned local task package, and loops the two stages until And No further changes occur.

Description

Multi-frame large unmanned aerial vehicle task allocation method based on WI-CBBA algorithm Technical Field The invention belongs to the technical field of fixed wing unmanned aerial vehicle task planning, and relates to a task allocation method for a plurality of large unmanned aerial vehicles based on a WI-CBBA algorithm. Background With the continuous progress of technology, unmanned plane technology has developed rapidly. The unmanned aerial vehicle plays an important role in tasks such as reconnaissance, monitoring and target positioning as a middle-high-altitude and long-endurance integrated unmanned aerial vehicle, has the advantages of long range, long endurance time, large countermeasure radius, strong load capacity and the like, and can execute diversified tasks in a complex environment. In order to improve the countermeasure efficiency, a plurality of unmanned aerial vehicles are often required to cooperate together to finish complex tasks. The task allocation of the multiple unmanned aerial vehicles is a key link for realizing cooperative coordination, and the goal is to reasonably allocate the multiple tasks to the multiple unmanned aerial vehicles, so that the whole unmanned aerial vehicle cluster can finish the tasks in an optimal mode, the task execution efficiency and success rate are improved, and the cost and risk are reduced. Therefore, how to efficiently solve the optimal task distribution curve by using the optimization algorithm aiming at the task distribution of the cooperative countermeasure of a plurality of unmanned aerial vehicles is a very popular research direction in recent years. Generally, the task allocation algorithm mainly comprises two major categories, one is a centralized task allocation method, such as a graph search algorithm, a traditional optimization algorithm and a heuristic algorithm, however, when the method faces a large-scale unmanned aerial vehicle cluster and a complex task scene, the calculation load of a central node is too heavy, so that the calculation efficiency is low, and the real-time requirement is difficult to meet. Moreover, once the central node fails, the task execution of the entire drone cluster will be affected. Another is a distributed task allocation method such as a distributed group intelligence algorithm, a contractual network algorithm, an auction algorithm, and the like. In the distributed method, each unmanned aerial vehicle independently generates a task allocation scheme according to self-perception information, and then obtains a global solution of the multi-unmanned aerial vehicle system through communication negotiation, so that the distributed task allocation method has strong robustness and fault tolerance, and is suitable for the problem of multi-unmanned aerial vehicle collaborative task allocation in an edge scene. Notably, the distributed task allocation algorithm still suffers from the following disadvantages: (1) The convergence speed of the algorithm is slow. When a traditional distributed task allocation algorithm is used for solving a large-scale problem, more iteration times are often needed to find the optimal solution, so that the convergence rate is low, and more computational resources are occupied; (2) The algorithm has slow solving speed. In each iteration, each unmanned aerial vehicle needs to communicate and negotiate with other unmanned aerial vehicles, and updates own task allocation conditions until global convergence is achieved. Under the conditions of more tasks and complex constraint conditions, the iteration process needs a large number of iteration times to obtain a stable result, so that the solving speed is low. (3) The algorithm is low in adaptation degree. In practice, when a plurality of unmanned aerial vehicles execute tasks, the tasks are executed in an edge environment, a plurality of factors which affect task allocation income like environmental mutation and change of situation of the opposite sides are filled, and when the conditions occur, the unmanned aerial vehicles as intelligent agents need to comprehensively consider a plurality of factors and then construct task packages and resolve conflicts, so that the overall income value is maximum. It is therefore necessary to consider the suitability of the algorithm in such an environment. Disclosure of Invention Object of the Invention The invention aims to overcome the defects of the prior art, and provides a multi-frame large unmanned aerial vehicle task allocation method based on a WI-CBBA algorithm, which is used for establishing an unmanned aerial vehicle task allocation model under the constraint of a range constraint, a time window constraint and a task package, introducing an online task weight coefficient into a benefit function to represent the weight of an unmanned aerial vehicle to execute a task, and comprehensively considering two factors of distance and benefit to reduce a search space by a clustering and branch-and-delimitati