基于改进拍卖算法灾后救援多无人机任务分配

Multi-UAV Task Assignment for Post-disaster Rescue Based on Improved Auction Algorithm

为提高灾后无人机(UAV)救援的效率,本文研究多无人机灾后侦察任务分配问题。考虑无人机续航时间、灾区地形以及是否遇到飞行障碍等因素,以无人机执行任务总时间最小为优化目标建立多无人机侦察任务分配模型,设计了混合动态规划的改进拍卖算法(hybrid dynamic programming auction, HDPA)求解模型。首先将无人机执行任务所需时间价值化,以单无人机执行任务所获收益最大为优化目标,设计动态规划算法获得单无人机执行任务最优序列作为初始投标方案,以防止拍卖算法陷入局部最优、提高算法的收敛速度;其次设计价格更新机制,解决投标任务之间的冲突,最终获得多无人机侦察任务分配最佳方案。实验结果表明,各无人机执行任务较为均衡,完成任务的总时间与传统的拍卖算法、遗传算法、海洋捕食者算法(marine predators algorithm, MPA)相比平均缩短了3.5%、5.6%、4.75%。

In order to improve the efficiency of post-disaster UAV rescue,the distribution of multi-UAV post-disaster reconnaissance tasks is studied.Considering factors such as UAV life time,disaster area terrain,and presence of obstacles in flight,the optimized objective is to minimize total time spent on UAV missions to establish multi-UAV reconnaissance task assignment model.An improved auction algorithm(hybrid dynamic programming auction,HDPA)is proposed to solve the model.First,the time spent on UAVs'tasks is valued.Next,the optimized objective is to maximize the benefits from a single UAV's tasks.Finally,a dynamic programming algorithm is created to determine the best order in which a single UAV should perform tasks as the first bid strategy to prevent the auctions algorithm falling into the local optimum and accelerating convergence.After resolving conflicts between competing tasks with the price update process,the optimal option for allocating multi-UAV reconnaissance tasks is obtained.The experimental results show that the tasks performed by each UAV are relatively balanced.The total time spent completing the task is reduced by an average of 3.5%,5.6%,and 4.75%compared with the traditional auction algorithm,genetic algorithm,and marine predator algorithm.