非死锁合同网协议驱动的多机分布式时序任务分配

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

针对多无人机协同任务分配的时序约束问题,提出了基于非死锁合同网协议(DF-CNP)的分布式时序任务分配方法,从理论上避免任务死锁,提升分配结果最优性。定义了局部信息条件下时序任务死锁判据,通过检测时序任务图环路状态与顶点可达性,判定分配方案的全局死锁状态,保证分配结果的可行性。定制了最近邻-深度优先混合搜索算法,在合同网排序过程中优先选择最近邻任务,并结合死锁判据递归回溯,在分布式架构下并行生成满足死锁约束的任务排序方案,提升分配结果的最优性。仿真对比结果表明:相比于非死锁遗传算法(TB-GA),DF-CNP在求解效率方面具有显著优势;与耦合约束一致性束算法(CBBA-TCC)相比,DF-CNP结果最优性明显提升。

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).