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

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

Abstract

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

CLC Number:

V249

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

Figures/Tables 16

Fig.1

Fig.2

Fig.3

Table 1

Table 2

Test function running results"

函数	维度	算法	最优值	平均值	标准方差	运行时间/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

Table 2

Fig.4

Table 3

Table 4

Table 5

Fig.5

Fig.6

Table 6

Fig.7

Fig.8

Table 7

Fig.9

References 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]	Weijian PANG, Hui LI, Qian HUANG, Peng LI, Xianming MA. Review on ontology-based task planning for unmanned systems [J]. Systems Engineering and Electronics, 2022, 44(3): 908-920.
[2]	Chen DONG, Yixian SHUAI, Jinpeng ZHOU, Peng LAI, Xianlei CHENG. Cooperative air defense task planning of networked multi-sensor-multi-weapon [J]. Systems Engineering and Electronics, 2022, 44(12): 3738-3746.
[3]	Peng JIN, Kang LI. Distributed satellite resource scheduling based on improved contract network protocol [J]. Systems Engineering and Electronics, 2022, 44(10): 3164-3173.
[4]	Chunyu HU, Weidong LIU, Tianxiang YU, Liyao ZHOU, Chen FENG. Analysis of multi wave task planning model based on UAV real-time data [J]. Systems Engineering and Electronics, 2021, 43(3): 747-754.
[5]	Taifei ZHAO, Minhua CHENG, Xinzhe LYU, Borui ZHENG. Energy consumption balancing routing algorithm of UAV swarm for ultraviolet secret communication [J]. Systems Engineering and Electronics, 2021, 43(1): 251-257.
[6]	MA Hua-wei, ZHU Yi-min, HU Xiao-xuan. Cooperative task planning for ship and UAVs based on particle swarm optimization algorithm [J]. Systems Engineering and Electronics, 2016, 38(7): 1583-1588.
[7]	WAN Ming, DAI Zhong, CHU Wen-kui. Turning path planning for UAV in region coverage with scanline [J]. Systems Engineering and Electronics, 2014, 36(9): 1750-1754.
[8]	KOU Ming-yan， XIONG Hua-gang， LI Qiao， HE Feng. Mission capacity oriented self-organized networks architecture [J]. Journal of Systems Engineering and Electronics, 2013, 35(5): 980-986.
[9]	LIU Fu-cai, DOU Jin-mei, Wang Shu-en. T-S fuzzy model identification based on intelligent optimization algorithms [J]. Systems Engineering and Electronics, 2013, 35(12): 2643-2650.

Multi-heterogeneous UAV task planning based on bacterial foraging algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 33

Related Articles 9

Recommended Articles

Metrics

Comments

障碍物	位置/m	碰撞半径/m	避碰半径/m	自身半径/m
1	(300, 700)	20	60	10
2	(450, 250)	30	70	20
3	(750, 450)	40	80	30
4	(500, 500)	50	90	40

算法	运行时间t/s
BFO	10.23
BFO-1	11.21
BFO-2	1.22
SSO	1.45
PSO	1.23
GA	1.34