一种分布式异构多AUV任务分配鲁棒拍卖算法

doi:10.13700/j.bh.1001-5965.2020.0655

北京航空航天大学学报 ›› 2022, Vol. 48 ›› Issue (5): 736-746.doi: 10.13700/j.bh.1001-5965.2020.0655

一种分布式异构多AUV任务分配鲁棒拍卖算法

李鑫滨, 郭力争, 韩松

燕山大学电气工程学院, 秦皇岛 066004

收稿日期:2020-11-24 发布日期:2022-05-30
通讯作者: 韩松 E-mail:hansong@ysu.edu.cn
基金资助:
国家自然科学基金(61873224，62003295，41976182)；河北省自然科学基金(F2020203037，F2019203031)；河北省高等学校科学技术研究项目(QN2020301)；河北省博士后项目(B2019003019)

A robust auction algorithm for distributed heterogeneous multi-AUV task assignment

LI Xinbin, GUO Lizheng, HAN Song

Institute of Electrical Engineering, Yanshan University, Qinhuangdao 066004, China

Received:2020-11-24 Published:2022-05-30
Supported by:
National Natural Science Foundation of China (61873224，62003295，41976182);S&T Program of Hebei (F2020203037，F2019203031);Science and Technology Research Project of Universities in Hebei (QN2020301);Science Foundation for Postdoctoral of Hebei (B2019003019)

摘要/Abstract

摘要： 为了解决异构多自主式水下航行器(AUV)的任务分配问题，提出了一种分布式鲁棒拍卖算法。建立了异构多AUV任务分配分布式拍卖模型，包括任务分配系统(拍卖商)的优化模型及AUV的优化模型。针对现有拍卖算法忽略拍卖商的利益，不符合市场规律的问题，引入任务奖励反馈机制，任务分配系统通过多轮试探拍卖市场，自适应地调整任务奖励，达到保证AUV效用的同时，有效降低任务分配系统成本的目的，促进了任务分配系统参与拍卖。针对水下洋流对任务分配模型产生的不确定性因素，提出了一种鲁棒优化算法对抗不确定性因素，提高了多AUV任务分配系统应对复杂水下环境的能力。仿真结果证明了所提算法的鲁棒性和有效性。

关键词: 异构多自主式水下航行器(AUV), 任务分配, 分布式, 拍卖算法, 鲁棒优化

Abstract: In order to solve the task assignment problem of multiple heterogeneous autonomous underwater vehicle (AUV), a distributed robust auction algorithm is proposed. First, a heterogeneous multi-AUV task assignment distributed auction model is established, including the task assignment system (auctioneer) optimization model and the AUV optimization model. Second, in view of the existing auction algorithms that ignore the interests of the auctioneer and do not conform to the market rules, we introduce task reward feedback mechanism, and the task assignment system, through several rounds of testing the auction market, adaptively adjusts the task rewards, which effectively reduces the cost of task assignment system when guaranteeing AUV utility at the same time, for the purpose of promoting the task assignment system to participate in the auction. Finally, a robust optimization algorithm is proposed to deal with the uncertainties caused by underwater ocean currents, which improves the ability of multi-AUV task assignment system to deal with complex underwater environment . Simulation results show the robustness and effectiveness of the proposed algorithm.

Key words: heterogeneous multi-autonomous underwater vehicle (AUV), task assignment, distributed, auction algorithm, robust optimization

中图分类号:

李鑫滨, 郭力争, 韩松. 一种分布式异构多AUV任务分配鲁棒拍卖算法[J]. 北京航空航天大学学报, 2022, 48(5): 736-746.

LI Xinbin, GUO Lizheng, HAN Song. A robust auction algorithm for distributed heterogeneous multi-AUV task assignment[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(5): 736-746.

参考文献

[1] CAO X,YU A.Multi-AUV cooperative target search algorithm in 3-D underwater workspace[J].The Journal of Navigation,2017,70(6):1293-1311.
[2] ZHU D,LIU Y,SUN B.Task assignment and path planning of a multi-AUV system based on a Glasius bio-inspired self-organising map algorithm[J].The Journal of Navigation,2018,71(2):482-496.
[3] CHEN Y,YANG D,YU J.Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm[J].IEEE Transactions on Aerospace and Electronic Systems,2018,54(6):2853-2872.
[4] CHOUDHURY B B,BISWAL B B.Alternative methods for multi-robot task allocation[J].Journal of Advanced Manufacturing Systems,2009,8(2):163-176.
[5] DARRAH M,NILAND W,STOLARIK B.Multiple UAV dynamic task allocation using mixed integer linear programming in a SEAD mission[C]//Infotech@Aerospace,2005:7164.
[6] GERKEY B P.On multi-robot task allocation[D].Los Angeles:University of Southern California,2003.
[7] WANG J F,JIA G W,LIN J C,et al.Cooperative task allocation for heterogeneous multi-UAV using multi-objective optimization algorithm[J].Journal of Central South University,2020,27(2):432-448.
[8] XU G,LONG T,WANG Z,et al.Target-bundled genetic algorithm for multi-unmanned aerial vehicle cooperative task assignment considering precedence constraints[J].Proceedings of the Institution of Mechanical Engineers,Part G:Journal of Aerospace Engineering,2020,234(3):760-773.
[9] LI J,ZHANG R B.Multi-AUV distributed task allocation based on the differential evolution quantum bee colony optimization algorithm[J].Polish Maritime Research,2017,24(s3):65-71.
[10] KIM M H,BAIK H,LEE S.Response threshold model based UAV search planning and task allocation[J].Journal of Intelligent and Robotic Systems,2014,75(3-4):625-640.
[11] PARKER L E.ALLIANCE:An architecture for fault-tolerant multi-robot cooperation[J].IEEE Transactions on Robotics and Automation,1998,14(2):220-240.
[12] SHI J,YANG Z,ZHU J.An auction-based rescue task allocation approach for heterogeneous multi-robot system[J].Multimedia Tools and Applications,2020,79(21):14529-14538.
[13] 费爱国,张陆游,丁前军.基于拍卖算法的多机协同火力分配[J].系统工程与电子技术,2012,34(9):1829-1833.FEI A G,ZHANG L Y,DING Q J.Multi-machine cooperative fire distribution based on auction algorithm[J].Systems Engineering and Electronic Technology,2012,34(9):1829-1833(in Chinese).
[14] TANG J,ZHU K,GUO H,et al.Using auction-based task allocation scheme for simulation optimization of search and rescue in disaster relief[J].Simulation Modelling Practice and Theory,2018,82:132-146.
[15] LEE D H,ZAHEER S A,KIM J H.A resource-oriented,decentralized auction algorithm for multirobot task allocation[J].IEEE Transactions on Automation Science and Engineering,2014,12(4):1469-1481.
[16] CHENG Q,YIN D,YANG J,et al.An auction-based multiple constraints task allocation algorithm for multi-UAV system[C]//2016 International Conference on Cybernetics,Robotics and Control (CRC).Piscataway:IEEE Press,2016:1-5.
[17] 于大海.弱通信条件下的多水下机器人任务分配方法研究[D].哈尔滨:哈尔滨工程大学,2013.YU D H.Research on task assignment method of multiple underwater vehicles under weak communication condition[D].Harbin： Harbin Engineering University,2013(in Chinese).
[18] QTTE M,KUHLMAN M J,SOFGE D.Auctions for multi-robot task allocation in communication limited environments[J].Autonomous Robots,2020,44(3):547-584.
[19] CHAN H,NAN Y,YANG Y,et al.Multi-UAV reconnaissance task assignment for heterogeneous targets based on modified symbiotic organisms search algorithm[J].Sensors,2019,19(3):734.
[20] YANG K,WU Y,HUANG J,et al.Distributed robust optimization for communication networks[C]//IEEE INFOCOM 2008-the 27th Conference on Computer Communications.Piscataway:IEEE Press,2008:1157-1165.
[21] CHEN M,ZHU D.A workload balanced algorithm for task assignment and path planning of inhomogeneous autonomous underwater vehicle system[J].IEEE Transactions on Cognitive and Developmental Systems,2018,11(4):483-493.

一种分布式异构多AUV任务分配鲁棒拍卖算法

A robust auction algorithm for distributed heterogeneous multi-AUV task assignment

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	田磊, 赵启伦, 董希旺, 李清东, 吕金虎, 任章. 拒止环境下基于“忠诚僚机”的护航策略[J]. 北京航空航天大学学报, 2021, 47(5): 1058-1067.
[2]	丁超, 魏瑞轩, 周凯. 基于时域映射的多无人机系统给定时间分布式最优集结[J]. 北京航空航天大学学报, 2021, 47(2): 315-322.
[3]	李桂亮, 毕海洋, 洪雪健, 金琳乘. 基于DE-DPSO-GT-SA算法的协同多任务分配[J]. 北京航空航天大学学报, 2021, 47(1): 90-96.
[4]	刘帅, 赵国荣, 曾宾, 高超. 数据丢包和量化约束下的分布式滚动时域估计[J]. 北京航空航天大学学报, 2020, 46(8): 1485-1493.
[5]	杨静, 魏若愚. 星座分布式自主定轨中信息融合方法比较研究[J]. 北京航空航天大学学报, 2020, 46(7): 1345-1353.
[6]	贾正荣, 卢发兴, 王航宇. 基于解耦优化和环流APF的多平台协同攻击任务规划[J]. 北京航空航天大学学报, 2020, 46(6): 1142-1150.
[7]	韩旭, 赵国荣, 王康. 基于线性编码补偿方法的非固定丢包率下的分布式融合估计器[J]. 北京航空航天大学学报, 2020, 46(6): 1229-1236.
[8]	叶文, 刘艳红, 王博, 蔡晨光, 李建利. 基于最小二乘拟合法的分布式POS全局估计方法[J]. 北京航空航天大学学报, 2020, 46(5): 862-869.
[9]	侯岳奇, 梁晓龙, 何吕龙, 刘流. 未知环境下无人机集群协同区域搜索算法[J]. 北京航空航天大学学报, 2019, 45(2): 347-356.
[10]	宋鑫, 郑冠男, 杨国伟, 姜倩. 几何不确定性区间分析及鲁棒气动优化设计[J]. 北京航空航天大学学报, 2019, 45(11): 2217-2227.
[11]	孟祥曦, 张凌, 郭皓明, 郭黎敏, 夏乾臣, 吕江花, 马世龙. 一种面向工业互联网的云存储方法[J]. 北京航空航天大学学报, 2019, 45(1): 130-140.
[12]	魏政磊, 赵辉, 黄汉桥, 王骁飞, 周瑞. 基于SAGWO算法的UCAVs动态协同任务分配[J]. 北京航空航天大学学报, 2018, 44(8): 1651-1664.
[13]	朱创创, 梁晓龙, 张佳强, 何吕龙, 刘流. 无人机集群编队控制演示验证系统[J]. 北京航空航天大学学报, 2018, 44(8): 1739-1747.
[14]	徐小明, 张武翔, 丁希仑. 基于模块化的缠绕机设计方法[J]. 北京航空航天大学学报, 2018, 44(4): 746-758.
[15]	李兆铭, 杨文革, 丁丹, 廖育荣. 多星对合作目标的分布式协同导航滤波算法[J]. 北京航空航天大学学报, 2018, 44(3): 462-469.