Journal of Astronautics ›› 2022, Vol. 43 ›› Issue (5): 675-684.doi: 10.3873/j.issn.1000-1328.2022.05.012

Previous Articles     Next Articles

Multi UAV Distributed Task Allocation with Precedence Constraints Driven by Deadlock free Contract Net Protocol

CAO Yan, LONG Teng, SUN Jingliang, XU Guangtong   

  1. 1. School of Aerospace Engineering, Beijing Institute of Technology, Beijing 100081, China; 2. Key Laboratory of Dynamics and Control of Flight Vehicle, Beijing 100081, China;3. Department of Precision Instrument, Tsinghua University, Beijing 100084, China
  • Received:2021-06-28 Revised:2021-10-09 Online:2022-05-15 Published:2022-05-15

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

CLC Number: