Abstract: To solve the precedence constraint problem of multi UAV cooperative task allocation, a distributed task allocation method with precedence constraints based on deadlock free contract net protocol(DF CNP) is proposed to avoid task deadlock theoretically and improve the optimality of the allocation results. The deadlock criterion for precedence tasks is defined under local information. By detecting the cycle state and vertex reachability of the precedence task subgraph, the global deadlock status of allocation results can be determined effectively to generate feasible results. The nearest neighbor depth first search algorithm is customized to prioritize the nearest neighbor task in CNP. Combined with the recursive backtracking of deadlock criterion, a task sequence subject to the deadlock constraints is generated in parallel under the distributed framework, and the optimality of the allocation results is improved. The simulation comparison results show that DF CNP can significantly save computational time compared with the target bundled genetic algorithm(TB GA), and the optimality of DF CNP results is apparently better than that of consensus based bundle algorithm with task coupling constraints(CBBA TCC).

Key words: Unmanned aerial vehicle, Distributed task allocation, Precedence task deadlock, Contract net protocol