基于改进最小边际代价算法的多USV多AUV任务分配  

Task assignment for multiple USVs and AUVs based on improved minimum marginal cost algorithm

作　　者：白小山 佘桉奇 郑心泉 吴宗泽 BAI Xiao-shan;SHE An-qi;ZHENG Xin-quan;WU Zong-ze(College of Mechatronics and Control Engineering,Shenzhen University,Shenzhen 518000,China;College of Electrical Engineering,Yanshan University,Qinhuangdao 066004,China)

机构地区：[1]深圳大学机电与控制工程学院,广东深圳518000 [2]燕山大学电气工程学院,河北秦皇岛066004

出　　处：《控制与决策》2025年第1期119-127,共9页Control and Decision

基　　金：国家自然科学基金项目(62373255,62003217);国家重大科研仪器研制项目(62327808);广东省基础与应用基础研究重大专项项目(2023B0303000009);广东省自然科学基金项目(2024A1515011204);深圳市自然科学基金稳定支持计划项目(20220809175803001);大数据系统计算技术国家工程实验室开放基金项目(SZU-BDSC-OF2024-15)。

摘　　要：随着自主水下机器人(AUV)和无人水面艇(USV)在民用和军事领域的应用不断扩展, USV与AUV协同完成相关任务的作业模式受到了广泛关注.针对多USV和多AUV协同访问多目标点的任务分配问题进行研究,旨在最小化多USV和AUV系统访问所有目标点的总旅行距离.首先,建立考虑通信约束和AUV最大航程约束的多USV多AUV协同多点访问任务分配问题的数学模型,并对问题的NP-hard属性进行分析.其次,提出一个两阶段任务分配算法:1)先利用最小边际代价算法构建各USV访问完所有水面目标点的路径,再采用最近插入策略分配水下目标点;2)通过多个邻域搜索算子对初始解进行优化,得到可行最终解.相对于已有流行的自组织映射算法,仿真实验表明所提出任务分配算法能在较短计算时间内得到质量较优的任务分配方案.With the rapid development of autonomous underwater vehicles(AUVs)and unmanned surface vessels(USVs)in both civil and military domains,the collaboration between USVs and AUVs for performing certain tasks has attracted widespread attention.This paper focuses on the task assignment problem for multiple USVs and AUVs to visit multiple target locations,aiming to minimize the total travel distance for multiple USVs and AUVs to visit all target locations.Firstly,a mathematical model for the studied task assignment problem is established,considering the AUVs’communication constraints and the maximum travel distance,and the NP-hard of the problem is analyzed.Secondly,a two-stage task assignment algorithm is proposed:1)the initial routes of the USVs to visit all the surface target locations are first constructed using the minimum marginal-cost algorithm,and the nearest insertion strategy is adopted to assign underwater target locations;2)the initial assignment solution is improved through several neighborhood search operators.Simulation results show that the proposed algorithm can obtain a better assignment solution within a shorter running time than the existing popular self-organizing map algorithm.

关 键 词：任务分配 USV-AUV协同 启发式算法 协同控制 邻域搜索 通讯约束 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]