Deadlock-Free Consecutive Task Assignment of Multiple Heterogeneous Unmanned Aerial Vehicles

Abstract

This paper presents an integrated approach based on graph theory for solving the deadlock problem in the cooperative task assignment of multiple heterogeneous unmanned aerial vehicles, which is concerned with the cooperative decision making and control. Because of heterogeneity, one task cannot be performed by arbitrary vehicles in the heterogeneous group. A vehicle that performs multiple tasks on targets needs to change its path, waiting for others if another vehicle that executes a former or simultaneous task has not finished or arrived. This creates risks of deadlock. Two or more vehicles may fall into a situation of infinite waiting due to shared resources and precedence constraints among various tasks. In this work, a task-precedence graph of solutions is constructed and analyzed for detecting deadlocks. And transposing operations are used to unlock solutions that involved in deadlocks. In addition, the topological sort of tasks is used in the path elongation of vehicles. Thus, deadlock-free solutions are obtained, and the path coordination is done. Computational experiments are conducted to check the performance of the approach, and the results validate the effectiveness.