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

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

作　　者：曹严 龙腾[1,2] 孙景亮 徐广通 CAO Yan;LONG Teng;SUN Jingliang;XU Guangtong(School of Aerospace Engineering,Beijing Institute of Technology,Beijing 100081,China;Key Laboratory of Dynamics and Control of Flight Vehicle,Beijing 100081,China;Department of Precision Instrument,Tsinghua University,Beijing 100084,China)

机构地区：[1]北京理工大学宇航学院,北京100081 [2]飞行器动力学与控制教育部重点实验室,北京100081 [3]清华大学精密仪器系,北京100084

出　　处：《宇航学报》2022年第5期675-684,共10页Journal of Astronautics

基　　金：国家自然科学基金(51675047,62003036);中国航空科学基金(2019ZC072003);中国博士后科学基金(2019TQ0037)。

摘　　要：针对多无人机协同任务分配的时序约束问题,提出了基于非死锁合同网协议(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).

关 键 词：无人机 分布式任务分配 时序任务死锁 合同网协议 

分 类 号：V19[航空宇航科学与技术—人机与环境工程]