基于细菌觅食算法的多异构无人机任务规划

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

摘要/Abstract

摘要：

针对多无人机任务规划问题, 以细菌觅食算法为基础, 融合遗传算法的交叉变异操作, 进行任务分配。为了提高算法的收敛能力, 动态自适应调节算法的游动步长、繁殖次数和迁徙概率。基于Lyapunov导航向量场和避障向量场构建融合向量场, 模拟真实静态和动态障碍物环境, 在任务分配阶段完成航迹规划; 基于合同网拍卖算法, 进行无人机坠毁后的任务重分配。仿真结果显示, 改进算法满足任务规划需求, 在考虑静态和动态障碍物的环境下, 能够高效的完成多异构无人机的任务分配以及重分配且总代价最小。

关键词: 无人机, 任务规划, 细菌觅食算法, 合同网拍卖算法

Abstract:

Aiming at the problem of multi unmanned aerial vehicle(UAV) task planning, based on the bacterial foraging algorithm, the cross-mutation operation of genetic algorithm is combined to perform task assignment. In order to improve the convergence ability of the algorithm, the swimming step length, reproduction times and migration probability of the algorithm are dynamically and adaptively adjusted. A fusion vector field based on the Lyapunov navigation vector field and obstacle avoidance vector field, the real static and dynamic obstacle environment is simulated, and the trajectory planning is completed in the task allocation stage; at the same time, based on the contract network auction algorithm, the task is redistributed after UAV attacked. The simulation results show that, considering static and dynamic obstacles, the task allocation and redistribution of multi-heterogeneous UAVs can be efficiently completed with minimal total cost.

Key words: unmanned aerial vehicle(UAV), task planning, bacterial foraging optimization, contract network

中图分类号:

V249

谷旭平, 唐大全. 基于细菌觅食算法的多异构无人机任务规划[J]. 系统工程与电子技术, 2021, 43(11): 3312-3320.

Xuping GU, Daquan TANG. Multi-heterogeneous UAV task planning based on bacterial foraging algorithm[J]. Systems Engineering and Electronics, 2021, 43(11): 3312-3320.

图/表 16

图1

图2

图3

表1

表2

测试函数运行结果"

函数	维度	算法	最优值	平均值	标准方差	运行时间/s	函数	维度	算法	最优值	平均值	标准方差	运行时间/s
f₁(x)	30	BFO	4.51E-02	4.93E-02	2.10E-16	1.31E+02	f₅(x)	30	BFO	9.76E-02	1.23E-01	7.54E-22	1.31E+02
		BFO-1	3.07E-02	3.11E-02	1.72E-24	1.02E+02			BFO-1	1.36E-02	1.41E-02	4.53E-14	1.08E+02
		BFO-2	5.34E-02	5.37E-02	3.23E-14	7.25E-01			BFO-2	3.07E-02	3.13E-02	4.13E-23	1.56E-00
		GA	1.34E-01	2.03E-01	1143E-02	7.73E-01			GA	6.13E-00	1.22 E+01	4.35E-00	6.77E-01
		PSO	5.23E+04	5.34E+04	2.13E+03	3.25E-01			PSO	3.94E+01	4.57E+01	5.34E+01	2.85E-01
		SSO	1.59E-01	1.60E-01	0.10E-04	1.40E-01			SSO	7.14E+01	8.97E+01	1.55E+01	6.142E-01
f₂(x)	30	BFO	2.14E-01	2.25E-01	0.14E-23	1.40E+02	f₆(x)	3	BFO	-3.86E-00	-3.86E-00	0	1.07E+02
		BFO-1	1.20E-03	1.20E-03	0	2.19E+02			BFO-1	-3.86E-00	-3.86E-00	0	1.11E+02
		BFO-2	2.04E-02	2.95E-02	0.21E-14	7.04E-01			BFO-2	-3.86E-00	-3.86E-00	0	7.04E-01
		GA	3.67E-01	4.13E-01	2.25E-01	6.78E-01			GA	-3.86E-00	-3.86E-00	4.03E-04	6.30E-01
		PSO	6.19E-00	7.14E-00	1.36E-00	3.07E-01			PSO	-3.78E-00	-3.70E-00	5.31E-02	2.25E-01
		SSO	3.48E-01	4.12E-01	1.17E-01	6.24E-01			SSO	-3.86E-00	-3.86E-00	1.23E-00	8.39E-01
f₃(x)	30	BFO	5.16E-02	5.21E-02	3.20E-24	1.28E+02	f₇(x)	4	BFO	-1.01E+01	-1.01E+01	2.44E-12	1.19E+02
		BFO-1	7.03E-02	7.12E-02	1.21E-13	1.18E+02			BFO-1	-1.01E+01	-1.01E+01	5.14E-21	1.51E+02
		BFO-2	2.86E-02	2.87E-02	3.41E-14	7.01E-01			BFO-2	-1.01E+01	-1.01E+01	1.53E-21	7.42E-01
		GA	4.41E-00	5.23E-00	2.12E-00	8.52E-01			GA	-1.01E+01	-1.02E+01	9.54E-13	6.32E-01
		PSO	1.93E+01	2.36E+01	5.23E+01	4.73E-01			PSO	-4.19E-00	-3.21E-00	1.43E-00	2.51E-01
		SSO	1.80E-00	1.93E-00	2.34E-02	8.56E-01			SSO	-1.01E+01	-1.00E+01	2.31E-11	8.32E-01
f₄(x)	30	BFO	8.86E-02	8.91E-02	3.42E-12	1.37E+02	f₈(x)	2	BFO	9.98E-01	9.98E-01	0	2.19E+02
		BFO-1	6.97E-02	7.03E-02	2.17E-53	1.19E+02			BFO-1	9.98E-01	9.98E-01	0	5.34E+02
		BFO-2	2.58E-01	2.63E-01	2.01E-24	1.04E-01			BFO-2	9.98E-01	9.98E-01	1.21E-14	1.12E-00
		GA	1.81E-00	7.11E-00	7.35E-00	7.89E-01			GA	9.98E-01	9.98E-01	0	1.16E-00
		PSO	2.74E+02	3.01	4.25E+02	4.35E-01			PSO	3.96E-00	4.57E-00	1.73E-00	6.30E-01
		SSO	3.40E-01	7.86E-01	1.43E+01	9.29E-01			SSO	1.99E-00	2.43E-00	9.56E-00	2.34E-00

表2

图4

表3

表4

表5

图5

图6

表6

图7

图8

表7

图9

参考文献 33

1	HUANG T P , HUANG D Q , WANG Z K , et al. Robust tracking control of a quadrotor UAV based on adaptive sliding mode controller[J]. Complexity, 2019, 29 (1): 37- 42.
2	SUN F J , WANG X C , ZHANG R . Task scheduling system for UAV operations in agricultural plant protection environment[J]. Journal of Ambient Intelligence and Humanized Computing, 2020, 17 (1): 37- 46. doi: 10.1007/s12652-020-01969-1
3	MENG H W , GUO Y M . Automatic safety routing inspection of the electric circuits based on UAV light detection and ranging[J]. Destech Transactions on Engineering and Technology Research, 2017, 23 (2): 102- 113.
4	SCHERER J, RINNER B. Persistent multi-UAV surveillance with energy and communication constraints[C]//Proc. of the IEEE International Conference on Automation Science and Engineering, 2016: 1225-1230.
5	CHEN H X , NAN Y , YANG Y . Multi-UAV reconnaissance task assignment for heterogeneous targets based on modified symbiotic organisms search algorithm[J]. Sensors, 2019, 19 (3): 734- 745. doi: 10.3390/s19030734
6	GRAYSON S . Search & rescue using multi-robot systems[J]. School of Computer Science and Informatics, University College Dublin, 2014, 14 (2): 112- 132.
7	OH B H , KIM K , CHOI H L , et al. Cooperative multiple agent-based algorithm for evacuation planning for victims with different urgencies[J]. Journal of Aerospace Information Systems, 2018, 15 (6): 382- 395. doi: 10.2514/1.I010589
8	JUNG S , ARIYUR K B . Strategic cattle roundup using multiple quadrotor UAVs[J]. International Journal of Aeronautical Space Science, 2017, 18, 315- 326. doi: 10.5139/IJASS.2017.18.2.315
9	LOTTES P, KHANNA R, PFEIFER J, et al. UAV-based crop and weed classification for smart farming[C]//Proc. of the IEEE International Conference on Robotics and Automation, 2017: 3024-3031.
10	MAZA I, KONDAK K, BERNARD M, et al. Multi-UAV cooperation and control for load transportation and deployment[C]//Proc. of the 2nd International Symposium on UAVs, 2009: 417-449.
11	OMAGARI H , HIGASHINO S I . Provisional-ideal-point-based multi-objective optimization method for drone delivery problem[J]. International Journal of Aeronautical and Space Sciences, 2018, 19 (1): 262- 277. doi: 10.1007/s42405-018-0021-7
12	BEKTAS T . The multiple traveling salesman problem: an overview of formulations and solution procedures[J]. Omega, 2006, 34 (3): 209- 219. doi: 10.1016/j.omega.2004.10.004
13	SHMOYS D B , TARDOS É . An approximation algorithm for the generalized assignment problem[J]. Mathematical Programming, 1993, 62 (1): 461- 474.
14	PISINGER D , ROPKE S . A general heuristic for vehicle routing problems[J]. Computers & Operations Research, 2007, 34 (8): 2403- 2435.
15	BÉNICHOU M , GAUTHIER J M , GIRODET P , et al. Experiments in mixed-integer linear programming[J]. Mathematical Programming, 1971, 1 (1): 76- 94. doi: 10.1007/BF01584074
16	GHALENOEI M R, HAJIMIRSADEGHI H, LUCAS C. Discrete invasive weed optimization algorithm: application to coope-rative multiple task assignment of UAVs[C]//Proc. of the IEEE 48h Conference on Decision and Control Held Jointly with 28th Chinese Control Conference, 2009: 1665-1670.
17	ABD-ELRAHMAN E, AFIFI H, ATZORI L, et al. IoT-D2D task allocation: an award-driven game theory approach[C]//Proc. of the IEEE 23rd International Conference on Telecommunications, 2016.
18	XIA C, LIANG Y T, YUAN L Y, et al. Cooperative task assignment and track planning for multi-UAV attack mobile targets[J]. Journal of Intelligent & Robotic Systems, 100(3): 1383-1400.
19	LI M , LIU C , LI K , et al. Multi-task allocation with an optimized quantum particle swarm method[J]. Applied Soft Computing, 2020, 96, 106603.
20	YE F , CHEN J , TIAN Y , et al. Cooperative task assignment of a heterogeneous multi-UAV system using an adaptive genetic algorithm[J]. Electronics, 2020, 9 (4): 687- 692. doi: 10.3390/electronics9040687
21	KIM K S , KIM H Y , CHOI H L . A bid-based grouping method for communication-efficient decentralized multi-UAV task allocation[J]. International Journal of Aeronautical and Space Sciences, 2020, 21 (1): 290- 302. doi: 10.1007/s42405-019-00205-1
22	CHEN C , BAO W D , MEN T M , et al. NECTAR-an agent-based dynamic task allocation algorithm in the UAV swarm[J]. Complexity, 2020, 9 (14): 34- 45.
23	孙浩磊. 基于群体智能算法的无人机路径规划技术研究[D]. 沈阳: 沈阳理工大学, 2019.
	SUN H L. Research on UAV path planning technology based on swarm intelligence algorithms[D]. Shenyang: Shenyang Ligong University, 2019.
24	谌海云, 陈华胄, 刘强. 基于改进人工势场法的多无人机三维编队路径规划[J]. 系统仿真学报, 2020, 32 (3): 414- 420.
	CHEN Y H , CHEN Y Z , LIU Q . Multi-UAV 3D formation path planning based on improved artificial potential field[J]. Journal of System Simulation, 2020, 32 (3): 414- 420.
25	凌富园, 杜承烈, 孙宝亮, 等. 基于不规则障碍物环境下无人机的改进几何路径规划算法[J]. 航空电子技术, 2019, 50 (4): 40- 46.
	LING F Y , DU C L , SUN B L , et al. An improved geometrical path planning algorithmfor UAV in irregular-obstacle environment[J]. Avionics Technology, 2019, 50 (4): 40- 46.
26	FARSHI T R , ORUJPOUR M . A multi-modal bacterial foraging optimization algorithm[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 1, 1- 15. doi: 10.1007/s12652-020-02755-9
27	SAUNDERS J , CALL B , CURTIS A , et al. Static and dynamic obstacle avoidance in miniature air vehicles[M]. Virginia: Infotech@ Aerospace, 2005: 6950
28	WILHELM J, CLEM G, CASBEER D, et al. Circumnavigation and obstacle avoidance guidance for UAVs using gradient vector fields[C]//Proc. of the AIAA Scitech Forum, 2019.
29	WANG X , YADAV V , BALAKRISHNAN S N . Cooperative UAV formation flying with obstacle/collision avoidance[J]. IEEE Trans. on Control Systems Technology, 2007, 15 (4): 672- 679.
30	MIRJALILI S. Genetic algorithm[M]// Evolutionary algorithms and neural networks, Brisbane: Springer, 2019: 43-55.
31	XIA X W , GUI L , HE G L , et al. An expanded particle swarm optimization based on multi-exemplar and forgetting ability[J]. Information Sciences, 2020, 508, 105- 120.
32	BAȘE , ÜLKER E . A binary social spider algorithm for conti-nuous optimization task[J]. Soft Computing, 2020, 24 (17): 12953- 12979.
33	SUV W, DOU L H, FANG H, et al. Task allocation for multi-robot cooperative hunting behavior based on improved auction algorithm[C]//Proc. of the IEEE 27th Chinese Control Conference, 2008: 435-440.

函数	维度	范围	f_min
$ {f_1}(x) = \sum\nolimits_{i = 1}^n {x_i^2} $	30	[-100, 100]	0
$ {f_2}(x) = \sum\nolimits_{i = 1}^n {ix_i^4} + {\rm{random[0, 1)}}$	30	[-1.28, 1.28]	0
$ {f_3}(x) = - 20\exp \left( { - 0.2\sqrt {\frac{1}{n}\sum\nolimits_{i = 1}^n {x_i^2} } } \right) - \exp \left( {\frac{1}{n}\sum\nolimits_{i = 1}^n {\cos } \left( {2\pi {x_i}} \right)} \right) + 20 + e$	30	[-32, 32]	0
$ f_{4}(x)=\frac{1}{400} \sum_{i=1}^{n} x_{i}^{2}-\prod_{1}^{n} \cos \left(\frac{x_{i}}{\sqrt{i}}\right)+1$	30	[-600, 600]	0
$ {f_5}(x) = \sum\nolimits_{i = 1}^n {{\mathop{\rm rand}\nolimits} } \cdot \left\| {{x_i} \cdot \sin {x_i} - 0.1{x_i}} \right\|$	30	[-10, 10]	0
$ f_{6}(x)=-\sum_{i=1}^{4} c_{i} \exp \left(-\sum_{j=1}^{3} a_{i j}\left(x_{j}-p_{i j}\right)^{2}\right)$	3	[1, 3]	-3.86
$ {f_7}(x) = - \sum\nolimits_{i = 1}^5 {{{\left[ {\left( {\mathit{\boldsymbol{X}} - {\mathit{\boldsymbol{a}}_i}} \right){{\left( {\mathit{\boldsymbol{X}} - {\mathit{\boldsymbol{a}}_i}} \right)}^{\rm{T}}} + {c_i}} \right]}^{ - 1}}} $	4	[0, 10]	-10.1
$ {f_8}\left( x \right) = {\left( {\frac{1}{{500}} + \sum\nolimits_{j = 1}^{25} {\frac{1}{{j + \sum\nolimits_{i = 1}^2 {({x_i} - {a_{ij}})} }}} } \right)^{ - 1}}$	2	[-65, 65]	1

序号	位置/m	类型	价值	武器数量	航速/(m/s)
1	(20, 30)	强击机	0.8	12	40
2	(20, 40)	强击机	0.7	8	40
3	(20, 50)	侦察机	0.6	0	40
4	(30, 30)	侦察机	0.9	0	40
5	(30, 40)	轰炸机	0.6	12	40
6	(40, 30)	轰炸机	0.8	12	40

目标编号	位置/m	目标价值	武器需求	威胁系数
A₁	(100, 450)	0.75	1	0.34
A₂	(300, 400)	0.65	2	0.45
A₃	(350, 600)	0.84	1	0
A₄	(150, 800)	0.54	1	0
A₅	(400, 850)	0.98	2	0.12
A₆	(600, 700)	0.72	1	0
A₇	(750, 800)	0.55	1	0
A₈	(670, 520)	0.98	3	0
A₉	(780, 620)	0.34	1	0
A₁₀	(600, 340)	0.65	2	0
A₁₁	(600, 100)	0.75	1	0.32
A₁₂	(800, 200)	0.86	1	0.12

UAV	任务分配结果与预计完成时间/s
UAV1	S₁	T₁	T₄	T₅	E₁
	-	(C, A, V)	(C, A, V)	(C, A, V)	-
	0	293.1	577.6	869.2	886.9
UAV2	S₂	T₃	T₆	T₇	E₂
	-	(C, A, V)	(C, A, V)	(C, A, V)	-
	0	293.2	584.8	872.8	878.1
UAV3	S₃	T₁₁	T₁₂	T₉	E₃
	-	(C, V)	(C, V)	(C, V)	-
	0	299.5	585.8	869.3	873.5
UAV4	S₄	T₂	T₁₀	T₈	E₄
	-	(C, V)	(C, V)	(C, V)	-
	0	302.5	599.4	883.2	893.1
UAV5	S₅	T₂	T₁₀	T₈	E₅
	-	(A)	(A)	(A)	-
	0	302.5	599.4	883.2	893.1
UAV6	S₆	T₁₁	T₁₂	T₉	E₆
	-	(A)	(A)	(A)	-
	0	299.5	585.8	869.3	873.5

[1]	孙田野, 孙伟, 吴建军. 改进Quatre算法的无人机编队快速集结方法[J]. 系统工程与电子技术, 2022, 44(9): 2840-2848.
[2]	余婧, 雍恩米, 陈汉洋, 郝东, 张显才. 面向多无人机协同对地攻击的双层任务规划方法[J]. 系统工程与电子技术, 2022, 44(9): 2849-2857.
[3]	徐星光, 王晓峰, 姚璐, 任章. 固定翼无人机编队构型与通信拓扑优化[J]. 系统工程与电子技术, 2022, 44(9): 2936-2946.
[4]	杨建峰, 肖和业, 李亮, 白俊强, 董维浩. 基于模糊聚类和专家评分机制的无人机多层次模块划分方法[J]. 系统工程与电子技术, 2022, 44(8): 2530-2539.
[5]	卢元杰, 刘志敏, 孙智孝, 阚东. 基于模型的无人机系统架构综合评估方法[J]. 系统工程与电子技术, 2022, 44(4): 1239-1245.
[6]	李洪瑶, 李小强, 韩心中, 谢学立, 席建祥. 基于决策融合的多无人机协同目标检测识别算法[J]. 系统工程与电子技术, 2022, 44(3): 746-754.
[7]	张源原, 高阳, 朱鹏, 刘锦涛, 谷树山. 基于着色Petri网的无人机侦察战术规划[J]. 系统工程与电子技术, 2022, 44(3): 900-907.
[8]	庞维建, 李辉, 黄谦, 李朋, 马贤明. 基于本体的无人系统任务规划研究综述[J]. 系统工程与电子技术, 2022, 44(3): 908-920.
[9]	谷旭平, 唐大全. 基于联邦滤波算法的无人机集群分层协同导航[J]. 系统工程与电子技术, 2022, 44(3): 967-976.
[10]	余雪勇, 朱烨, 邱礼翔, 朱洪波. 基于无人机辅助边缘计算系统的节能卸载策略[J]. 系统工程与电子技术, 2022, 44(3): 1022-1029.
[11]	杨兴家, 段克清, 李想, 祁炜. 无人机集群协同探测距离解模糊方法[J]. 系统工程与电子技术, 2022, 44(2): 480-489.
[12]	符小卫, 潘静. 无人机集群规避动态障碍物的分布式队形控制[J]. 系统工程与电子技术, 2022, 44(2): 529-537.
[13]	陈都, 孟秀云. 基于自适应郊狼算法的无人机离线航迹规划[J]. 系统工程与电子技术, 2022, 44(2): 603-611.
[14]	刘步花, 丁丹, 杨柳, 薛乃阳, 刘仲谦. 基于DNN的无人机数据OFDM传输技术[J]. 系统工程与电子技术, 2022, 44(2): 696-702.
[15]	吴志鹏, 张平, 李震, 黄磊, 刘畅, 高硕. 基于轻小型无人机雷达的植被高度反演方法[J]. 系统工程与电子技术, 2022, 44(12): 3667-3675.