Multi-UAV Task Assignment Problem Using An Improved Estimation of Distribution Algorithm

Today, with the advancement of communication technology, the field of multi-UAV systems is evolving towards clustering, autonomy, and intelligence. Unlike single UAV systems, multi-UAV systems can meet diverse mission requirements with information sharing and complementary capabilities. In this paper, the task allocation problem in multi-UAV systems is addressed by considering two subproblems: task allocation to UAVs and path planning of UAV execution. To achieve an optimal solution that satisfies the requirements and capabilities of tasks, a task allocation algorithm using an improved Estimation of Distribution Algorithm is designed and proposed. First, the problem is introduced and formulated as a mixed-integer programming model based on the multi-traveling salesman problem. Next, a probability model is designed that takes into account task priority constraints, where a task allocation and path planning scheme that meets the constraints can be obtained by sampling the probability model. In addition, two local search methods based on problem knowledge are developed to enhance global search capability and improve solution performance. To evaluate the performance of the proposed algorithm, a series of simulation experiments using existing datasets is carried out. The effectiveness of the probability model and the local search operations is validated, respectively. Furthermore, the simulation results demonstrate that the proposed algorithm outperforms existing algorithms in terms of distance and time cost.