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

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

Abstract

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

CLC Number:

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.

Figures/Tables 6

Fig.1

Fig.2

Fig.3

Table 1

Fig.4

Fig.5

References 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]	Chengfei YUE, Zhenghua XUE, Weiran YAO, Xibin CAO. Cooperative combat task allocation of multiple aerial vehicles based on the characteristic relation [J]. Systems Engineering and Electronics, 2022, 44(6): 1897-1906.
[2]	Han LI, Honghai ZHANG, Liandong ZHANG, Hao LIU. Multiple logistics unmanned aerial vehicle collaborative task allocation in urban areas [J]. Systems Engineering and Electronics, 2021, 43(12): 3594-3602.
[3]	WANG Jianhao, ZHANG Liang, SHI Chao, CHE Fei, ZHANG Pengtao. Task allocation modeling and solving algorithm for equipment support using DLS-BCIWBA [J]. Systems Engineering and Electronics, 2018, 40(9): 1979-1985.
[4]	CUI Ya-ni, REN Jia, DU Wen-cai. Time-sensitive task dynamic allocation algorithm for multi-UAVs in battlefield environments [J]. Systems Engineering and Electronics, 2016, 38(4): 828-835.
[5]	YAO Peiyang1， WAN Lujun1,2， SUN Peng1， ZHOU Xiangxiang3. Dynamic task allocation in multiple agent groups based on RHPIVFSA [J]. Systems Engineering and Electronics, 2014, 36(7): 1309-1319.
[6]	BI Xiao-jun, WANG Jue, LI Bo. Multi-objective optimization based on hybrid biogeography based optimization [J]. Systems Engineering and Electronics, 2014, 36(1): 179-186.
[7]	WAN Lu-jun， YAO Pei-yang， SUN Peng. Distributed task allocation method of manned/unmanned combat Agents [J]. Journal of Systems Engineering and Electronics, 2013, 35(2): 310-316.
[8]	LIANG Xiao-long，HU Jun-hua，JING Xian-yong，LIU An，FENG Jin-fu. Multi-stage optimization model and algorithm for near space multi-weapon platform attacking ground targets [J]. Journal of Systems Engineering and Electronics, 2010, 32(12): 2618-2622.
[9]	TANG Suyan，ZHU Yifan，LI Qun，LEI Yonglin. Survey of task allocation in multi Agent systems [J]. Journal of Systems Engineering and Electronics, 2010, 32(10): 2155-2161.
[10]	LI Wei-xiang, ZHANG Guang-ming, LI Bang-yi. Research on multi-attributes task allocation mechanism in MAS [J]. Journal of Systems Engineering and Electronics, 2009, 31(5): 1113-1116.

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

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 27

Related Articles 10

Recommended Articles

Metrics

Comments