Research On Multi-UAV Task Allocation And Path Planning Based On Graph Partition

Unmanned aerial vehicles(UAVs)have attracted more and more attention from academia and industry due to their high mobility,flexible deployment,and low cost.For example,the use of drones to assist the Internet of Things for data collection.At the same time,the use of drones brings many challenges.One is that a single drone has insufficient real-time,completeness,and reliability when performing tasks,so multiple drones need to be dispatched to work together.Second,due to the requirements of timeliness,the task should be as short as possible it is completed within time,so how to design the optimal flight trajectory for each UAV is the key to obtaining UAV benefits.The trajectory design of the UAV includes two parts: task allocation and path planning.The key to the trajectory design is the task allocation algorithm,and the task allocation results obtained by traditional clustering methods are often inapplicable.Therefore,this paper adopts a task allocation and path planning algorithm based on graph partition to solve.The specific research content of this paper is as follows.Firstly,multiple drones are studied,starting from any data collection point to perform tasks.All data collection points are required to be allocated completely and without duplication.After the drones complete the data collection task,they must return to their respective starting points.Reasonable task allocation and path planning enable multiple drones to complete the target task in the shortest possible time.In the process of UAV data collection,the main occupancy time is the flight time of the UAV,especially when the distribution area of the sensors is relatively large,the data transmission time is negligible.Since the drone takes off at the same time,the flight time of the drone swarm depends on the drone with the longest flight time,and the length of the flight time is determined by the flight distance.That is,the goal is to minimize the maximum flight distance of the UAV.Since the min-max path planning is NP-hard,we transform this problem by replacing the minimum Hamiltonian cycle length of each UAV with the average cycle length.Through the use of a two-step iterative algorithm and a point transfer algorithm between Hamilton cycles complete non-repetitive balanced clustering of points,in which LKH software is used to write an external interface to achieve rapid path planning for points in each partition.The simulation results show that the algorithm in this paper is compared with the traditional number-based average to minimize the maximum compared with the k-means algorithm of flying distance,it has better performance.When the number of drones is the same,the performance is improved by an average of about 14%,and when the number of data collection points is the same,the performance is improved by an average of 12%.Secondly,since the UAV group is more inclined to start from a fixed starting point in real applications,the two scenarios in which the UAV all start from the same starting point and return to the same starting point are crossed and the paths are not crossed are further studied.The scenario where the UAV starts from the same starting point and does not return to the starting point and the scenario where the drones start from a different fixed starting point and return to their respective starting point and the scenario where the drones start from a different fixed starting point and do not return to the starting point.How to design these scenarios with reasonable task allocation and path planning algorithms that make it possible to minimize the maximum flight distance? It can be seen that these scenarios are very similar to the previously studied scenarios,so the algorithm is appropriately changed for different scenarios based on the previous algorithm.The simulation results for different scenarios are compared with the GA-mTSP algorithm or the GA-mTSP deformation algorithm.The simulation results show that the algorithm used is much better than the comparison algorithm and can solve the problems in the above scenarios.For example,in the scenario of a single fixed starting point and the drones returning to the starting point,when the number of drones is the same,the performance is increased by about 9% on average,and when the number of data collection points is the same,the performance is increased by 8.5% on average.