CN-121995963-A - Multi-unmanned aerial vehicle city inspection task allocation method considering time-sensitive targets

CN121995963ACN 121995963 ACN121995963 ACN 121995963ACN-121995963-A

Abstract

The invention discloses a multi-unmanned aerial vehicle city inspection task allocation method considering a time-sensitive target, and relates to the technical field of task allocation. The invention considers the capacity and target characteristics of photoelectric effective load in actual city inspection, divides heterogeneous targets into point targets, line targets, plane targets and body targets, establishes a three-dimensional Dubin dynamic multi-vehicle path model considering time windows to reduce the difference between estimated paths and actual paths, thereby improving the feasibility and accuracy of task allocation in urban environment, designs destroying and repairing operators with time window constraint by adopting a dynamic priority strategy and combining a simulated annealing mechanism to avoid sinking into local optimum. In addition, a priority criterion strategy of the dynamic target is customized and integrated into the self-adaptive large neighborhood search framework, so that the target with the dynamic time window is processed in real time, and efficient planning of a scout task allocation scheme in a dynamic environment is realized.

Inventors

LONG TENG
LI CHENGEN
SUN JINGLIANG
LI JUNZHI
SONG YANG

Assignees

北京理工大学

Dates

Publication Date: 20260508
Application Date: 20260129

Claims (8)

1. A multi-unmanned aerial vehicle city inspection task distribution method considering time-sensitive targets is characterized by comprising the following steps: S1, constructing an unmanned plane kinematics model and an unmanned plane three-dimensional Dubin inspection track model, and establishing a multi-unmanned plane inspection task allocation problem as an optimization problem of minimum inspection time considering time window constraint; wherein, unmanned aerial vehicle three-dimensional Dubins inspection track model is: Wherein, the Is the origin of coordinates; 、 Respectively a starting point and a finishing point of the unmanned aerial vehicle; 、 The starting point speed and the end point speed of the unmanned aerial vehicle are respectively; 、 The radius of the starting circle and the radius of the ending circle are respectively; 、 The initial turning angle and the final turning angle are respectively; Is that Is a vector of the direction of (2); the optimization problem of the minimum inspection time is as follows: The time window constraint is: ; ; Wherein the edge The track from the target i to the target j of the unmanned aerial vehicle is calculated by the three-dimensional Dubin tour-inspection track model; Along the edge of unmanned plane Time of flight; for the target node Is a patrol time of the (a); And Is a decision variable, if unmanned plane Inspection target node Then Otherwise If unmanned aerial vehicle Along the edge Flying, then Otherwise ; For adjusting the coefficient, the system is used for balancing the overall search time and the single-machine task load; 、 The appearance time and the disappearance time of the target j are respectively; Is unmanned plane Reaching the target point Is a time point of (2); S2, solving an optimization problem of minimum inspection time by adopting an improved self-adaptive large neighborhood search algorithm, wherein the method specifically comprises the following steps of: s21, starting from an empty solution by adopting a nearest neighbor algorithm, gradually adding target nodes closest to the current position for each unmanned aerial vehicle, and checking whether the target nodes meet corresponding time window constraint and fuel capacity constraint or not to obtain an initial patrol target node set of each unmanned aerial vehicle; s22, performing iterative optimization on the initial inspection target node set by adopting a self-adaptive large neighborhood search algorithm, and adopting a simulated annealing criterion to accept a solution generated by a destruction/repair operator in the iterative process to obtain the final inspection target node set of each unmanned aerial vehicle.
2. The method of claim 1, wherein, in S22, The destruction operator includes: Randomly destroying an operator randomly from a current set of inspected target nodes according to a discrete uniform distribution Is removed from The inspected targets; Destroying an operator from a current set of inspected target nodes in a minimum time After deleting one target, calculating the total time saved for removing the target, arranging the saved time for removing each inspected target in descending order, and removing the target nodes with less saved time through a roulette mechanism; similarity-destroying operator for calculating current inspected target node set The similarity values of any two target nodes are arranged in ascending order, the smaller the similarity value is, the higher the similarity of the two target nodes is, and then the target nodes with high similarity are removed through a roulette mechanism; the course change rate destroys an operator from the current set of inspected target nodes Removing the target node with the maximum range change rate, wherein the target node The range change rate of (1) is that the unmanned aerial vehicle is from the target node To the next target node Is the course of (1) and from the last target node To the target node The difference between the ranges of (a) is the ratio; The repair operator includes: A shortest time greedy repair operator that restores non-inspected objects Inserted to a position where the total time of flight increment is minimal; the minimum time regret value repair operator, which first regresses the non-inspected target Traversing and inserting the unmanned aerial vehicle into the unmanned aerial vehicle path, calculating the flight time increment of each insertion position, arranging the flight time increment according to ascending order, and then selecting the remorse value The maximum position, the remorse value is , wherein, Representing objects Inserted into the above arrangement Time increment of each location; Minimum time window violation greedy repair operator that will not patrol targets Inserting the minimum number of violations into all target time windows; Minimum time window violation regret value restoration operator, which first restores target nodes which are not inspected Traversing and inserting the time window violation degrees of all insertion positions into an unmanned plane path, calculating the time window violation degrees of all insertion positions, arranging the time window violation degrees in ascending order, and then selecting the position with the largest repentance value, wherein the repentance value is , wherein, Representing a target node Insert the first After each position, the target number of time windows is violated.
3. The method of claim 2, wherein, in the similarity-breaking operator, a target And Similarity value between The calculation is as follows: (18) Wherein, the 、、 Is a weight coefficient and ; Representing unmanned aerial vehicle slave target To the point of Is a time of flight of (2); Representing objects And Is a time window difference value of (2); Is a variable which is 0 to 1, Representing objects And The inspection is carried out by the same unmanned aerial vehicle, The opposite is true.
4. The method of claim 1, wherein in S22, the simulated annealing algorithm utilizes temperature parameters To control the probability of acceptance if the solution produced by the destruction/repair operator Superior to the current solution Then Must be accepted, and the resulting solution Inferior to the current solution When solve Is the probability of acceptance of (a) Calculated from formula (24): (24) Wherein: Representation solution A corresponding objective function value; Designing temperature parameters by taking maximum calculation time as stopping criterion of algorithm The update rule of (2) is: (25) Wherein: Is the initial temperature; the current calculation time is calculated; is the maximum calculated time.
5. The method according to claim 1, wherein S21 comprises the following sub-steps: s21.1, initializing a non-patrol target node set of the 1 st unmanned aerial vehicle, namely In the time-course of which the first and second contact surfaces, ; S21.2 checking the current unmanned aerial vehicle , Whether or not to meet If yes, the process proceeds to S21.3, and if not, the process proceeds to S21.10. S21.3 updating unmanned plane Is not a patrol of the target node set If (1) Then If (1) Still remain in ; S21.4 unmanned aerial vehicle From the current target node Starting from a set of non-patrol target nodes Selecting the target node closest to the target node i Forming a node combination Initially, taking the initial position of the unmanned aerial vehicle k as a target node i; s21.5 judging the target node combination Whether the target time window constraint is met, if yes, executing S21.6, if not, returning to S21.4, and collecting the target nodes from the non-patrol Selecting the next nearest target node to target node i Forming a node combination ; S21.6, judging the target node combination Whether the fuel capacity constraint of the unmanned aerial vehicle is satisfied, if yes, S21.8 is executed, and if no, S21.7 is executed. S21.7 inspection unmanned plane Target node for forward reconnaissance If the sum of the ranges reaching the target and covering the target is the shortest, if so, S21.10 is executed, if not, S21.5 is returned, and the next distance target node is selected Nearest target node Forming a node combination ; S21.8, destination node Unmanned aerial vehicle is added Is a set of inspected target nodes Will target node Unmanned aerial vehicle shifts out Is not a patrol of the target node set At the same time node Updating to a node ; S21.9 judging unmanned aerial vehicle Is not a patrol of the target node set If not, executing S21.10, and if not, executing S21.4 to continue constructing the initial allocation sequence of the current unmanned aerial vehicle; s21.10 order S21.3, calculating an initial allocation sequence of the next unmanned aerial vehicle; s21.11, after the algorithm is finished, outputting an initial patrol target node set of all unmanned aerial vehicles 。
6. The method of claim 1, wherein in S2, the target priority criteria is first designed based on the target threat level information and the time window, the entire planning time domain is then calculated Divided into a limited number of discrete inspection cycles At each inspection cycle The emergency level of the original target and the newly added target is updated at the beginning, and the target with lower priority can be deferred until the next inspection period And in each inspection period h, obtaining an inspection target node set of each unmanned aerial vehicle in the inspection period h in a mode of S21 and S22.
7. The method of claim 6, wherein, at each inspection cycle Initially, the unmanned aerial vehicle collects information about surrounding targets, and the collected information set is expressed as (26) Wherein, the Indicating the number of targets that can be reached by the drone, And Respectively represent the targets Threat level and time window of (a); the urgency value of each target is determined by equation (27): (27) The emergency degree values of the targets are arranged in ascending order, and the priority of the targets is graded according to the distribution of emergency scores.
8. The method of claim 1, wherein in S1, the target nodes are divided into a point target, a line target, a plane target, and a volume target; the inspection time of the line target, the surface target and the body target is divided by the unmanned plane speed; the entry point of the point target is the target point, and the direction is consistent with the specified inspection direction; the entry points of the line targets are two end points of the line segments, the inspection path flies along the central line of the long side of the line targets, and the direction is along the direction of the extension line of the line segments or the direction of the reverse extension line; the entry points of the surface target are four starting points of the surface target, the inspection path is a grating track covering the surface target, and the direction is vertical to the short side of the surface target and inwards; the entry point of the body target is 4 vertexes right above the body target, the inspection path is a cylindrical spiral track covering the body target, and the direction is tangential to the spiral and is divided into clockwise and anticlockwise.

Description

Multi-unmanned aerial vehicle city inspection task allocation method considering time-sensitive targets Technical Field The invention relates to the technical field of task allocation, in particular to a multi-unmanned aerial vehicle city inspection task allocation method considering a time-sensitive target. Background The multi-unmanned aerial vehicle system has fast and continuous development in low cost and high performance, and is widely applied to the scenes of inspection, monitoring and the like. However, due to the complex terrain constraints and high dynamic characteristics of urban environments, multi-drone urban inspection tasks remain challenging. Dense buildings and complex streets limit the inspection efficiency of photoelectric loads and also put high requirements on track planning. Along with the rapid development of intelligent and autonomous collaborative technologies of clusters, an intelligent cluster consisting of small fixed-wing unmanned aerial vehicles provides a new means for urban inspection tasks. Compared with a single unmanned aerial vehicle carrying limited load, the unmanned aerial vehicle cluster can execute more complex inspection tasks in urban environments by virtue of flexibility and quantity advantages, and has great potential. Task allocation is one of key technologies for realizing intelligent autonomous cooperation of multiple unmanned aerial vehicles, and the overall efficiency of the unmanned aerial vehicle cluster is improved to the greatest extent by calculating task allocation decision information of each unmanned aerial vehicle. The multi-unmanned aerial vehicle inspection task is distributed to each individual of the multi-unmanned aerial vehicle system to distribute a plurality of inspection targets, and the total range or cost is minimized under the condition that constraint conditions such as unmanned fuel limitation, inspection load and the like are met. The existing multi-unmanned aerial vehicle city inspection task allocation research is mainly focused on the aspects of unmanned aerial vehicle kinematics, target heterogeneous characteristics, environment uncertainty and the like, but ignores the inspection load capacity and the urban environment characteristics. The dense buildings reduce the feasible area of path planning in the inspection task, so that the collision probability of the unmanned aerial vehicle is high and the path is roundabout. Furthermore, the inspection task involves time-sensitive targets whose time windows tend to change throughout the inspection period, and the time coupling between these targets increases the difficulty of task allocation. However, current researches often ignore the path planning problem and dynamic time-sensitive targets in the routing task allocation, and cannot be effectively applied to urban scenes. Therefore, it is needed to provide a multi-unmanned aerial vehicle city inspection task allocation method considering time-sensitive targets. Disclosure of Invention In view of the above, the invention provides a multi-unmanned aerial vehicle city inspection task allocation method considering a time-sensitive target, which considers an unmanned aerial vehicle kinematic model and a dynamic city environment, establishes a multi-unmanned aerial vehicle city inspection task allocation model with heterogeneous target characteristics and latest discovery time constraint, effectively explores a solving space through random operation and a heuristic mechanism, obtains an optimal task allocation result in the maximum allowable calculation time, and improves the collaborative inspection task capacity of unmanned aerial vehicle clusters in a real city scene. The invention relates to a time-sensitive target-considered multi-unmanned aerial vehicle city inspection task distribution method, which comprises the following steps: S1, constructing an unmanned plane kinematics model and an unmanned plane three-dimensional Dubin inspection track model, and establishing a multi-unmanned plane inspection task allocation problem as an optimization problem of minimum inspection time considering time window constraint; wherein, unmanned aerial vehicle three-dimensional Dubins inspection track model is: Wherein, the Is the origin of coordinates;、 Respectively a starting point and a finishing point of the unmanned aerial vehicle; 、 The starting point speed and the end point speed of the unmanned aerial vehicle are respectively; 、 The radius of the starting circle and the radius of the ending circle are respectively; 、 The initial turning angle and the final turning angle are respectively; Is that Is a vector of the direction of (2); the optimization problem of the minimum inspection time is as follows: The time window constraint is: ; ; Wherein the edge The track from the target i to the target j of the unmanned aerial vehicle is calculated by the three-dimensional Dubin tour-inspection track model; Along the edge of unmanned plane Time of