Task Assignment for Multiple Multi-purpose Unmanned Aerial Vehicles Using Greedy Algorithm

doi:10.1007/s42405-024-00726-4

Return

Task Assignment for Multiple Multi-purpose Unmanned Aerial Vehicles Using Greedy Algorithm

2024-05-04

PRE

Ha-Min Jeon

Jae-Woo Lim

Chang-Kyung Ryoo *

DOI：10.1007/s42405-024-00726-4

Original

Original request for help

Save

Abstract

En 中文

Unmanned aerial vehicle fleets demand effective task assignment since the task scope of each vehicle depends on the task-specific equipment it carries. Here, we propose real-time task assignment for multiple multipurpose unmanned aerial vehicles using a greedy algorithm. The greedy algorithm does not require complex mathematical modeling and can respond to real-time situational changes due to its fast computation. The proposed algorithm uses the total flight time of all unmanned aerial vehicles as the objective function so that each vehicle completes all tasks within its available battery level. To increase the diversity of solutions, the algorithm is dually computed in the forward and backward directions from the starting and destination points, respectively. We apply the algorithm to water resource management and compare the results with those of mixed integer linear programming and the genetic algorithm. While the flight-time cost is similar across algorithms, computation is 3-8 times faster for the proposed algorithm than for the genetic algorithm. This advantage increases as the number of tasks and/or unmanned aerial vehicles increases. The proposed algorithm's consideration of remaining battery levels when selecting randomly unmanned aerial vehicles also results in a higher average remaining battery level than the other algorithms. These results suggest that the proposed algorithm shows promise and feasibility for application to real-time task assignment scenarios for multiple multipurpose unmanned aerial vehicles.

Keywords:

Task assignment

Greedy algorithm

Mixed integer linear programming

Genetic algorithm

Multipurpose unmanned aerial vehicle

Water resource management