基于顺序扩展一致性包算法的多无人机分布式任务分配

以异构多无人机协同执行复杂的耦合多任务为背景,提出一种求解分布式任务分配问题非死锁的顺序扩展一致性包算法.首先,建立考虑任务载荷资源、任务时序、威胁区等约束条件的时序多任务分配模型;其次,对一致性包算法的任务包构建过程和冲突消解规则进行扩展,并设计一种基于有向图深度优先搜索的方法进行任务方案的死锁检测和修正,以实现无冲突和无死锁的任务分配;然后,将关联任务之间的时序约束转化为软时间窗约束,利用顺序分层的策略进行求解;最后,为了提高任务分配结果的可靠性,采用Dubins曲线路径将航路规划耦合到任务分配中.仿真实验表明,所提出的算法能够快速有效地求解异构多无人机分布式耦合多任务分配问题,具备良好的最优性和时效性.

Distributed task allocation of multiple UAVs based on sequential extended consensus based bundle algorithm

Based on the background of complex coupled multiple tasks executed by heterogeneous multiple unmanned aerial vehicles(UAVs), a deadlock-free sequentially extended consensus based bundle algorithm is presented to solve the distributed task allocation problem. Firstly, a timing multi-task allocation model is established in consideration of the constraints of task load resources, task sequence and threat regions. Secondly, the task bundle construction and conflict resolution rules of the consensus based bundle algorithm are extended, and then a deadlock detection and correction method of the task scheme based on digraph depth-first search is designed to achieve conflict-free and deadlock-free task allocation. Furthermore, the timing constraints between related tasks are transformed into soft time window constraints, and the sequential hierarchical strategy is utilized to solve the problem. Finally, the Dubins curve path is employed to integrate the route planning into the task allocation in order to improve the reliability of the task allocation result. Simulation results show that the proposed algorithm can tackle the distributed coupled multi-task allocaiton problem of heterogeneous multiple UAVs quickly and efficiently, and possesses satisfactory optimality and timeliness..