基于D-NSGA-Ⅲ算法的无人机群高维多目标任务分配方法

doi:10.12305/j.issn.1001-506X.2021.05.11

系统工程与电子技术 ›› 2021, Vol. 43 ›› Issue (5): 1240-1247.doi: 10.12305/j.issn.1001-506X.2021.05.11

基于D-NSGA-Ⅲ算法的无人机群高维多目标任务分配方法

周晶^1,²(), 赵晓哲¹(), 许震³(), 林众²(), 张晓盼^3,*()

1. 大连理工大学经济管理学院, 辽宁大连 116024
2. 海军大连舰艇学院作战软件与仿真研究所
3. 武汉理工大学计算机科学与技术学院, 湖北武汉 430074

收稿日期:2020-05-28 出版日期:2021-05-01 发布日期:2021-04-27
通讯作者: 张晓盼 E-mail:zj_0562@163.com;zj_0562@sina.com;thginWalker@whut.edu.cn;skymoon_001@163.com;tom_xp@whut.edu.cn
作者简介:周晶(1981—), 男, 博士研究生, 主要研究方向为系统建模与仿真、模式识别与智能系统。E-mail: zj_0562@163.com|赵晓哲(1963—), 男, 教授, 博士研究生导师, 博士，主要研究方向为指挥控制与信息系统工程。E-mail: zj_0562@sina.com|许震(1996—), 男, 硕士研究生, 主要研究方向为多智能体系统。E-mail: thginWalker@whut.edu.cn|林众(1975—), 男, 助理研究员，硕士, 主要研究方向为系统仿真与建模。E-mail: skymoon_001@163.com|张晓盼(1975—), 男, 副教授, 博士, 主要研究方向为复杂系统分析与优化。E-mail: tom_xp@whut.edu.cn
基金资助:
国家自然科学基金(71701208)

Many-objective task allocation method based on D-NSGA-Ⅲ algorithm for multi-UAVs

Jing ZHOU^1,²(), Xiaozhe ZHAO¹(), Zhen XU³(), Zhong LIN²(), Xiaopan ZHANG^3,*()

1. School of Management and Economics, Dalian University of Technology, Dalian 116024, China
2. Institute of Operation Software and Simulation, Dalian Naval Academy, Dalian 116018, China
3. School of Computer Science and Technology, Wuhan University of Technology, Wuhan 430074, China

Received:2020-05-28 Online:2021-05-01 Published:2021-04-27
Contact: Xiaopan ZHANG E-mail:zj_0562@163.com;zj_0562@sina.com;thginWalker@whut.edu.cn;skymoon_001@163.com;tom_xp@whut.edu.cn

摘要/Abstract

摘要：

随着人工智能技术的快速发展, 种类繁多的无人机在军事领域得到了广泛应用。受单平台资源配备和执行能力限制, 大多数复杂任务需由多个无人机协同完成, 最优任务分配是其中需解决的重点和难点问题之一。最优任务分配方案求解问题已被证明是一个NP难问题, 针对多无人机系统的组织架构, 将非支配排序遗传算法与岛屿模型、主从模型结合, 构建一种分布式高维多目标演化算法D-NAGA-Ⅲ并对实际应用场景中4个目标进行优化, 并引入迁移策略和贪心算法对任务分配方案进行局部提升, 提高算法寻优能力和解质量。实验结果表明: 该方法在求解高维多目标的分布式无人机任务分配问题方面具有一定的效果。

关键词: 分布式演化算法, 任务分配, 高维多目标优化算法, 迁移策略

Abstract:

With the rapid development of artificial intelligence technology, a variety of unmanned aerial vehicles (UAVs) have been widely used in the military field. Due to the limitation of resource allocation and executive capability of single platform, most of complex tasks should be accomplished by the cooperation of multiple UAVs. Optimal task allocation is one of the critical and difficult problems to be solved, and it has been proven to be an NP-hard problem. Considering the organization architecture of multi-UAVs system, the non-dominated genetic algorithm is combined with island model and master-slave model. A distributed many-objective evolutionary algorithm, named D-NAGA-Ⅲ, is built to optimize four objects in a real application, and a migration strategy and greedy algorithm are proposed to improve the optimization ability and enhance the solution quality. Experimental results show that the proposed method is effective in solving distributed many-objective task allocation problems in UAVs systems.

Key words: distributed evolutionary algorithm, task allocation, many-objective optimization algorithm, migration strategy

中图分类号:

周晶, 赵晓哲, 许震, 林众, 张晓盼. 基于D-NSGA-Ⅲ算法的无人机群高维多目标任务分配方法[J]. 系统工程与电子技术, 2021, 43(5): 1240-1247.

Jing ZHOU, Xiaozhe ZHAO, Zhen XU, Zhong LIN, Xiaopan ZHANG. Many-objective task allocation method based on D-NSGA-Ⅲ algorithm for multi-UAVs[J]. Systems Engineering and Electronics, 2021, 43(5): 1240-1247.

图/表 6

图1

图2

图3

表1

图4

图5

参考文献 27

1	黄远灿. 国内外军用机器人产业发展现状[J]. 机器人技术与应用, 2009, (2): 25- 31.
	HUANG Y C . Development status of military robot industry at home and abroad[J]. Robot technology and Application, 2009, (2): 25- 31.
2	胡雄超. 集中式多类型无人机编队任务分配方法研究[D]. 西安: 西安电子科技大学, 2013.
	HU X C. Research on task allocation method of centralized multi type UAV formation[D]. Xi'an: Xidian University, 2013.
3	王友发. 面向智能制造的多机器人系统任务分配研究[D]. 南京: 南京大学, 2016.
	WANG Y F. Research on task allocation of multi robot system for intelligent manufacturing[D]. Nanjing: Nanjing University, 2016.
4	欧建军, 钟麟. 基于多智能体的编队协同空战战术规划[J]. 电光与控制, 2010, 17 (2): 35- 38.
	OU J J , ZHONG L . Tactical planning for cooperative air combat of formation based on multi-agent system[J]. Electronics Optics & Control, 2010, 17 (2): 35- 38.
5	钱善华, 葛世荣, 王永胜, 等. 救灾机器人的研究现状与煤矿救灾的应用[J]. 机器人, 2006, 28 (3): 350- 354. doi: 10.3321/j.issn:1002-0446.2006.03.021
	QIAN S H , GE S R , WANG Y S , et al. Research status of the disaster rescue robot and its applications to the mine rescue[J]. Robot, 2006, 28 (3): 350- 354. doi: 10.3321/j.issn:1002-0446.2006.03.021
6	MURPHY R R , TADOKORO S , NARDI D , et al. Search and rescue robotics[J]. Springer handbook of robotics, 2008, 1151- 1173.
7	JAYMODI P , SHEN W , TAMBE M , et al. Adopt: asynchronous distributed constraint optimization with quality guarantees[J]. Artificial Intelligence, 2005, 161 (1): 149- 180.
8	PETCU A, FALTINGS B. DPOP: a scalable method for multiagent constraint optimization[C]//Proc. of the 19th International Joint Conference Artificial Intelligence, 2005: 266-271.
9	MAILLER R, LESSER V. Solving distributed constraint optimization problems using cooperative mediation[C]//Proc. of the 3rd International Joint Conference Autonomous Agents and Multiagent Systems, 2004: 438-445.
10	MACARTHUR K S, STRANDERS R, RAMCHURN S, et al. A distributed anytime algorithm for dynamic task allocation in multi-agent systems[C]//Proc. of the 25th AAAI Conference on Artificial Intelligence, 2011: 701-706.
11	XIE B, CHEN J, SHEN L C. Cooperation algorithms in multi-agent systems for dynamic task allocation: brief overview[C]//Proc. of the 37th Chinese Control Conference, 2018: 6776-6781.
12	FITZPATRICK S , MEETRENS L . Distributed sensor networks: a multi-agent perspective[M]. Boston: Kluwer Academic Publishers, 2003.
13	CHAPMAN A C, MICILLO R A, KOTA R, et al. Decentralised dynamic task allocation: a practical game-theoretic approach[C]//Proc. of the 8th International Conference on Autonomous Agents and Multiagent Systems, 2009.
14	FITZPATRICK S , MEERTENS L . Distributed coordination through anarchic optimization[M]. Boston: Springer, 2003.
15	YEDIDSION H , ZIVAN R , FARINELLI A . Applying max-sum to teams of mobile sensing agents[J]. Engineering Applications of Artificial Intelligence, 2018, 71, 87- 99. doi: 10.1016/j.engappai.2018.02.017
16	ZHANG Q , LI H . MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans.on Evolutionary Computation, 2007, 11 (6): 712- 731. doi: 10.1109/TEVC.2007.892759
17	SHEHORY O , KRAUS S . Methods for task allocation via agent coalition formation[J]. Artificial Intelligence, 1998, 101 (1): 165- 200.
18	RAHWAN T , JENNINGS N R . An algorithm for distributing coalitional value calculations among cooperating agents[J]. Artificial Intelligence, 2007, 171 (8/9): 535- 567.
19	CAO Y C , YU W W , REN W , et al. An overview of recent progress in the study of distributed multi-agent coordination[J]. IEEE Trans.on Industrial informatics, 2013, 9 (1): 427- 438. doi: 10.1109/TII.2012.2219061
20	DEB K , JAIN H . An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints[J]. IEEE Trans.on Evolutionary Computation, 2014, 18 (4): 577- 601. doi: 10.1109/TEVC.2013.2281535
21	ZHOU J , ZHAO X Z , ZHANG X P , et al. Task allocation for multi-agent systems based on distributed many-objective evolutionary algorithm and greedy algorithm[J]. IEEE Access, 2020, 8, 19306- 19318. doi: 10.1109/ACCESS.2020.2967061
22	ZHOU J, ZHAO X Z, ZHAO D D, et al. Task allocation in multi-agent systems using many-objective evolutionary algorithm NSGA-Ⅲ[C]//Proc. of the International Conference on Machine Learning and Intelligent Communications, 2019: 677-692.
23	GONG Y J , CHEN W N , ZHAN Z H , et al. Distributed evolutionary algorithms and their models: a survey of the state-of-the-art[J]. Applied Soft Computing, 2015, 34 (C): 286- 300.
24	FERREIRA P R , DOS SANTOS F , BAZZAN A L C , et al. RoboCup rescue as multiagent task allocation among teams: experiments with task interdependencies[J]. Autonomous Agents and Multi-Agent Systems, 2010, 20 (3): 421- 443. doi: 10.1007/s10458-009-9087-8
25	CHIANG T C. NSGA3CPP: a C++ implementation of NSGA-Ⅲ[EB/OL]. [2019-02-28]. https://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm?tdsourcetag=s_pcqq_aiomsg.
26	GAO Y, ZHANG Y Z, ZHU S R, et al. Multi-UAV task allocation based on improved algorithm of multi-objective particle swarm optimization[C]//Proc. of the International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, 2018: 443-4437.
27	COELLO C A C, LECHUGA M S. MOPSO: a proposal for multiple objective particle swarm optimization[C]//Proc. of the Congress on Evolutionary Computation, 2002: 1051-1056.

参数名称	取值/方式
交叉算子	模拟二进制交叉
交叉概率	0.9
交叉因子	0.5
变异概率	1.0
变异方法	多项式变异
变异分布索引	20
迭代次数	250
贪婪精度参数ε	0.001
Island数量	4

[1]	岳程斐, 薛正华, 姚蔚然, 曹喜滨. 基于机群关系特征的多机协同作战任务分配[J]. 系统工程与电子技术, 2022, 44(6): 1897-1906.
[2]	尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.
[3]	李翰, 张洪海, 张连东, 刘皞. 城市区域多物流无人机协同任务分配[J]. 系统工程与电子技术, 2021, 43(12): 3594-3602.
[4]	王坚浩, 张亮, 史超, 车飞, 张鹏涛. 装备保障任务分配建模与DLS-BCIWBA算法求解[J]. 系统工程与电子技术, 2018, 40(9): 1979-1985.
[5]	林君灿, 贾高伟, 侯中喜. 异构UAV编队反雷达作战中任务分配方法[J]. 系统工程与电子技术, 2018, 40(9): 1986-1992.
[6]	崔亚妮, 任佳, 杜文才. 战场环境下多无人机时敏任务动态分配算法[J]. 系统工程与电子技术, 2016, 38(4): 828-835.
[7]	孙小雷1, 齐乃明1, 董程2, 姚蔚然1. 无人机任务分配与航迹规划协同控制方法[J]. 系统工程与电子技术, 2015, 37(12): 2772-2776.
[8]	姚佩阳1，万路军1,2，孙鹏1，周翔翔3. 基于RHP-IVFSA的多智能体编组#br# 任务分配动态优化[J]. 系统工程与电子技术, 2014, 36(7): 1309-1319.
[9]	毕晓君，王珏，李博. 基于混合生物地理学优化的多目标优化算法[J]. 系统工程与电子技术, 2014, 36(1): 179-186.
[10]	江建清，朱晓敏，伍国华，贺川，吴朝波. 面向应急对地观测任务的多飞艇协同分配方法[J]. Journal of Systems Engineering and Electronics, 2013, 35(2): 317-325.
[11]	万路军，姚佩阳，孙鹏. 有人/无人作战智能体分布式任务分配方法[J]. Journal of Systems Engineering and Electronics, 2013, 35(2): 310-316.
[12]	刘跃峰，张安. 有人机/无人机编队协同任务分配方法[J]. Journal of Systems Engineering and Electronics, 2010, 32(3): 584-587.
[13]	梁晓龙，胡俊华，荆献勇，刘安，冯金富. 近空间多武器平台对地攻击多阶段模型及算法[J]. Journal of Systems Engineering and Electronics, 2010, 32(12): 2618-2622.
[14]	唐苏妍，朱一凡，李群，雷永林. 多Agent系统任务分配方法综述[J]. Journal of Systems Engineering and Electronics, 2010, 32(10): 2155-2161.
[15]	李为相, 张广明, 李帮义. 一种多属性的MAS任务分配机制研究[J]. Journal of Systems Engineering and Electronics, 2009, 31(5): 1113-1116.

基于D-NSGA-Ⅲ算法的无人机群高维多目标任务分配方法

Many-objective task allocation method based on D-NSGA-Ⅲ algorithm for multi-UAVs

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 27

相关文章 15

编辑推荐

Metrics

本文评价