A Delay-Tolerant and Temporal-Ordering-Constrained Task Allocation Method for Multi-UAV Systems

现有的面向时序约束的多无人机任务分配方法大多假定任务执行是非延迟容忍的情况，这不仅降低了任务被执行的机会，而且极大地限制了多无人机的竞争与协作灵活度，从而影响任务完成率。为此，文章将提出一种面向延迟容忍的时序约束多无人机任务分配方法，并解决延迟容忍带来的任务执行效益时变性问题。具体而言，首先设计了一种动态时间窗机制，为无人机任务执行提供弹性空间，允许无人机在任务可执行初始时间之前到达进行悬停等待或在预计截止时间后超时执行任务，并基于此定义了随动态时间窗变化的任务执行收益。接着，构建强化学习模型以引导无人机进行任务选择，然后定义无人机与任务的匹配因子，设计根据匹配因子、悬停和超时情况解决任务选择冲突的共识机制。最后采用多智能体深度确定性策略梯度算法(MADDPG)对强化学习模型进行求解。实验结果表明，与现有方法相比，本文所提的方法在系统效益和任务完成率方面均表现出显著优势。The majority of existing multi-UAV task allocation approaches under temporal-ordering-constrained are based on the assumption of non-delay-tolerant task execution, which not only reduces the task execution chances but also greatly limits the competition and collaboration flexibility among multiple UAVs, thereby affecting the task completion rate. To address this problem, this paper will propose a delay-tolerant and temporal-ordering-constrained task allocation method, then solve the time-varying problem of task execution benefit related to delay tolerance. In this method, firstly, a dynamic time window mechanism is designed to provide an elastic space for UAV task execution, which allows UAVs to hover and wait for a task before its initial executable time and execute the task after its expected deadline and the time-varying task execution benefit related to the dynamic execution window is also defined; Secondly, a reinforcement learning model is constructed to guide the task selection of UAVs, a matching factor between task and UAVs is defined, and a consensus mechanism is provided to solve task selection conflicts between UAVs based on the matching factor, the waiting and delay time of UAVs. Finally, the multi-agent deep deterministic policy gradient algorithm is used to solve the reinforcement learning model. Experimental results show that, compared with existing methods, the method proposed in this paper exhibits significant advantages in terms of system benefit and task completion rate.