改进自组织映射的多无人机协同任务分配方法_孙亚男.pdf

2023-05-10计算机应用,Journal of Computer Applications2023,43(5):1551-1556ISSN 1001-9081CODEN JYIIDUhttp：/改进自组织映射的多无人机协同任务分配方法孙亚男，吴杰宏*，石峻岭，高利军（沈阳航空航天大学 计算机学院，沈阳 110136）（通信作者电子邮箱）摘要：针对现有算法对多无人机（UAV）协同进行多任务分配时存在负载均衡和执行效率方面的不足，提出一种改进的自组织映射（ISOM）算法。该算法根据飞行时间和任务执行时间设计了UAV的负载均衡度，以提升任务完成的效率；还设计了新的非线性变化的学习率和邻域函数保证ISOM算法的稳定性和快速收敛。然后，在不同任务环境对ISOM算法进行了有效性验证。实验结果表明，与结合遗传算法的粒子群优化（GA-PSO）、Gurobi和ORTools算法相比，ISOM 算法的任务完成时间可分别减少 15.5%、12.7%和 7.3%；在 TSPLIB 数据集的实例 KroA100、KroA150、KroA200上进行航迹长度减小的有效性验证时，与杂草优化（IWO）算法、改进的单亲遗传算法（IPGA）和蚁群单亲遗传算法（AC-PGA）的对比结果表明，ISOM算法在无人机数量为2、3、4、5、8时，均获得了最小的航迹长度。由此可见，ISOM算法在解决多UAV协同多任务分配问题时效果显著。关键词：多无人机；任务分配；自组织映射；负载均衡；执行效率中图分类号：TP301.6 文献标志码：AMulti-UAV collaborative task assignment method based on improved self-organizing mapSUN Yanan，WU Jiehong*，SHI Junling，GAO Lijun（School of Computer Science，Shenyang Aerospace University，Shenyang Liaoning 110136，China）Abstract:To deal with the deficiencies in load balancing and execution efficiency of existing algorithms for cooperative multi-task assignment of multi-Unmanned Aerial Vehicle（UAV），an Improved Self-Organizing Map（ISOM）algorithm was proposed.In the algorithm，the load balancing degree of UAVs was designed according to the flight time and task execution time in order to improve the efficiency of the task completion.And a novel non-linearly changing learning rate and neighborhood function were designed to ensure the stability and fast convergence of ISOM algorithm.Then，the validity of ISOM algorithm was verified in different task environments.Experimental results show that compared with Particle Swarm Optimization combined with Genetic Algorithm（GA-PSO），Gurobi and ORTools algorithms，the proposed algorithm has the task completion time reduced by 15.5%，12.7%and 7.3%respectively.When the effectiveness of track length reduction was verified on KroA100，KroA150，and KroA200 examples of TSPLIB dataset，comparison results with Invasive Weed Optimization（IWO）algorithm，Improved Partheno Genetic Algorithm（IPGA）and Ant Colony-Partheno Genetic Algorithm（AC-PGA）show that ISOM algorithm has the minimum track length when the number of UAVs is 2，3，4，5，8.It can be seen that ISOM algorithm has a significant effect on solving the problem of multi-UAV cooperative multi-task assignment.Key words:multi-Unmanned Aerial Vehicle(UAV);task assignment;Self-Organizing Map(SOM);load balancing;execution efficiency0 引言 无人机（Unmanned Aerial Vehicle，UAV）具有低成本、高机动性、强隐蔽性等特点，在很多方面得到了应用，例如：勘探1、区域搜索与救援2-3、货物运输4等。由于任务环境的复杂性，单个无人机逐渐不能满足高难度任务的需求，多架无人机协同工作受到了学者的关注5-7。多无人机协同能够扩大任务范围，减少任务完成时间，提高任务的完成率。协同任务分配问题作为无人机协同工作的基础，在求解时需要考虑任务规模、无人机的数量以及执行任务的能力等多种因素，是 一 个 非 确 定 性 多 项 式 完 全 问 题（Non-deterministic Polynomial Complete problem，NPC）8。对于多无人机协同任务分配问题的研究，首先需要将实际问题进行数学建模，使用合适的数学模型准确表示实际问题。现阶段的研究中，描述该问题常使用的数学模型包括多旅行商问题（Multiple Travelling Salesman Problem，MTSP）、车辆路径问题（Vehicle Routing Problem，VRP）、混合整数线性文章编号：1001-9081（2023）05-1551-06DOI：10.11772/j.issn.1001-9081.2022040592收稿日期：2022-04-27；修回日期：2022-06-22；录用日期：2022-06-24。基金项目：国防基础科研项目（JH2021010）；国家自然科学基金资助项目（61902261）。作者简介：孙亚男（1996），女，辽宁朝阳人，硕士研究生，主要研究方向：无人机系统路径规划和任务分配；吴杰宏（1971），女，黑龙江齐齐哈尔人，教授，博士，CCF高级会员，主要研究方向：无人机系统协同控制、安全通信；石峻岭（1989），女，辽宁沈阳人，讲师，博士，主要研究方向：车载网络、无人机网络；高利军（1977），男，辽宁沈阳人，教授，博士，主要研究方向：信息安全、人工智能攻防对抗算法。第 43 卷计算机应用规划（Mixed Integer Linear Programming，MILP）、协同多任务分配问题。其中应用最广泛的是 MTSP，作为旅行商问题（Travelling Salesman Problem，TSP）9的一个变体，能弥补其不能解决大规模问题的缺陷，且模型原理简单、可扩展性强，能充分发挥多无人机协同合作的优势。解决MTSP主要分为精确法和启发式的方法。最著名的精确算法是分支定界法，首先被提出来求解大规模对称MTSP10。精确算法有严格的数学基础，但算法解决问题的能力完全取决于问题的大小，当规模太大时，问题无法在可接受的时间内得到解，甚至无法解决。为了解决上述计算困难的问题，越来越多的学者将研究的重点转移到启发式算法上来，因为能够容易得到MTSP的最优解或者次优解。Jiang等11针对MTSP，将单亲遗传算法与蚁群算法相结合，提出了蚁群单亲遗传算法（Ant Colony-Partheno Genetic Algorithm，AC-PGA），在大规模 MTSP 求解上具有足够的有效性，且性能优于已有的算法；Zhou等12为了解决具有多个仓库的最小 MTSP，提出了单亲遗传算法（Partheno Genetic Algorithm，PGA）与改进的单亲遗传算法（Improved Partheno Genetic Algorithm，IPGA），在TSPLIB数据集上的实验结果表明，IPGA在求解MTSP上具有较高的优越性；胡士娟等13针对MTSP，提出了一种模糊C均值聚类单亲遗传算法，实验结果表明它在求解大规模问题时性能良好，收敛更快；张瑞鹏等14针对多无人机协同任务分配问题，提出了考虑航迹长度、任务收益以及完成时间的混合粒子群任务分配算法，提升了算法求解速度，还具有不断跳出局部收敛的能力。上述启发式算法虽然可以取得较好的效果，但在处理多无人机协同任务分配时，存在容易陷入局部最优、自适应能力较差的情况。自组织映射（Self-Organizing Map，SOM）神经网络可以避免陷入局部最小值的情况，并且快速收敛，提升任务分配方案的精度。SOM神经网络是一种竞争网络，由Kohonen教授在20世纪80年代提出15，而后进行了扩展16。近年来，很多学者将SOM 算法应用在多机器人系统中。Zhu等17使用一个启发自组织的图算法，安排一组自主水下航行器（Autonomous Underwater Vehicle，AUV）访问所有指定的目标位置；同时该团队利用SOM神经网络对水下机器人的任务分配与路径规划问题进行了一系列的研究18-20。Zhu 等21利用基于 SOM神经网络的算法将多机器人系统的任务分配与路径规划结合进行求解，使机器人能够在目的地确定之前就开始移动；但该方法容易导致机器人在多个目标之间迂回，且未考虑机器人自身约束条件。Yi等22提出了一种基于SOM的研究方法解决三维动态环境下的机器人群的任务分配问题，但没有考虑机器人系统完成任务的整体效率。有关SOM神经网络的研究大多针对多机器人的任务分配和控制，大多数方法仅考虑了机器人与任务之间的距离约束，并未考虑机器人资源、任务约束等。本文在多无人机协同任务分配时考虑了无人机的航迹长度和执行任务的时间，提出了改进的 SOM（Improved Self-Organizing Map，ISOM）算法，保证了无人机之间的负载均衡，减少了任务完成的时间，降低了资源消耗。1 模型建立 设定任务区域内的任务点分布在地面，UAV在执行任务时始终保持在同一高度对地面进行观测。本文将UAV进行抽象化处理，假定无人机均是相同的，具备导航、位置识别等基本功能，重点关注如何降低无人机的能量消耗、提升执行任务的效率。1.1无人机模型本文将多无人机协同执行任务分配问题建模为多旅行商问题，其中旅行商代表 UAV，城市代表任务区域内的任务。UAV集合U=U1，U2，UN，N表示UAV数量，为了更好地描述UAV，通过四元组表示：Un=(st，post，v，ct)。st表示t时刻Un的状态，如式（1）所示：st=|0，空闲1，飞行2，执行任务（1）其中：post=(xt，yt，zt)表示Un在t时刻的位置；v表示无人机的飞行速度；ct 0，1表示t时刻Un的任务完