A multiple heterogeneous UAVs reconnaissance mission planning and re-planning algorithm

doi:10.23919/JSEE.2022.000142

Journal of Systems Engineering and Electronics ›› 2022, Vol. 33 ›› Issue (6): 1190-1207.doi: 10.23919/JSEE.2022.000142

• SYSTEMS ENGINEERING • Previous Articles

A multiple heterogeneous UAVs reconnaissance mission planning and re-planning algorithm

Lei HU¹(), Boqi XI¹(), Guoxing YI¹^,*(), Hui ZHAO¹(), Jiapeng ZHONG²()

¹ School of Astronautics, Harbin Institute of Technology, Harbin 150000, China
² HIT (Anshan) Institute of Industrial Technology, Harbin Institute of Technology, Anshan 114000, China

Received:2021-03-15 Online:2022-12-18 Published:2022-12-24
Contact: Guoxing YI E-mail:maple_hsjz@163.com;xiboqi@163.com;ygx@hit.edu.cn;zhaohui@hit.edu.cn;zhong-j-p@163.com
About author:
HU Lei was born in 1993. He received his M.S. degree from Harbin Institute of Technology in 2018. He is pursuing his Ph.D. degree in Harbin Institute of Technology. His research interests include weapon system combat effectiveness and decision-making. E-mail: maple_hsjz@163.com

XI Boqi was born in 1978. He received his Ph.D. degree from Harbin Institute of Technology, Harbin, China. He is an associate professor in Harbin Institute of Technology. His research interests include the mechanism and application of hemispherical resonance gyro, and the research of inertial and integrated navigation. E-mail: xiboqi@163.com

YI Guoxing was born in 1974. He received his Ph.D. degree from Harbin Institute of Technology, Harbin, China. He is a professor in Harbin Institute of Technology. His research interests include UAV system and application technology, the mechanism and application of hemispherical resonance gyro, and the research of inertial and integrated navigation. E-mail: ygx@hit.edu.cn

ZHAO Hui was born in 1971. He received his Ph.D. degree from Harbin Institute of Technology, Harbin, China. He is a professor in Harbin Institute of Technology. His research intesests include electric drive and high-performance servo drive control, and driving and control of ultrasonic actuator. E-mail: zhaohui@hit.edu.cn

ZHONG Jiapeng was born in 1986. He received his Ph.D. degree from Harbin Institute of Technology, Harbin, China in 2016. He is an engineer in Industrial Technology Research Institute of Harbin Institute of Technology (Anshan). His research interests include UAV system and application technology, the mechanism and application of hemispherical resonance gyro, and the research of inertial and integrated navigation. E-mail: zhong-j-p@163.com

Abstract

Abstract:

Reconnaissance mission planning of multiple unmanned aerial vehicles (UAVs) under an adversarial environment is a discrete combinatorial optimization problem which is proved to be a non-deterministic polynomial (NP)-complete problem. The purpose of this study is to research intelligent multi-UAVs reconnaissance mission planning and online re-planning algorithm under various constraints in mission areas. For numerous targets scattered in the wide area, a reconnaissance mission planning and re-planning system is established, which includes five modules, including intelligence analysis, sub-mission area division, mission sequence planning, path smoothing, and online re-planning. The intelligence analysis module depicts the attribute of targets and the heterogeneous characteristic of UAVs and computes the number of sub-mission areas on consideration of voyage distance constraints. In the sub-mission area division module, an improved K-means clustering algorithm is designed to divide the reconnaissance mission area into several sub-mission areas, and each sub-mission is detected by the UAV loaded with various detective sensors. To control reconnaissance cost, the sampling and iteration algorithms are proposed in the mission sequence planning module, which are utilized to solve the optimal or approximately optimal reconnaissance sequence. In the path smoothing module, the Dubins curve is applied to smooth the flight path, which assure the availability of the planned path. Furthermore, an online re-planning algorithm is designed for the uncertain factor that the UAV is damaged. Finally, reconnaissance planning and re-planning experiment results show that the algorithm proposed in this paper are effective and the algorithms designed for sequence planning have a great advantage in solving efficiency and optimality.

Key words: reconnaissance mission planning, sequence planning, path smoothing, combination optimization

Lei HU, Boqi XI, Guoxing YI, Hui ZHAO, Jiapeng ZHONG. A multiple heterogeneous UAVs reconnaissance mission planning and re-planning algorithm[J]. Journal of Systems Engineering and Electronics, 2022, 33(6): 1190-1207.

Figures/Tables 22

Table 1

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Table 2

Table 3

Table 4

Fig 7

Fig 8

Table 5

Fig 9

Fig 10

Fig 11

Fig 12

Table 6

Table 7

Fig 13

Fig 14

Fig 15

References 43

44	HU L, YI G X, HUANG C, et al Research on dynamic weapon target assignment based on cross-entropy. Mathematical Problems in Engineering, 2020, 2020, 8618065.
1	HADDON D R, WHITTAKER C J Office of the secretary of defense, unmanned aircraft systems roadmap. Implementation of Network, 2005, 8 (14): 263- 278.
2	JIA G W, WANG J F Research review of UAV swarm mission planning method. Journal of Systems Engineering and Electronics, 2021, 43 (1): 99- 111.
3	JOSHUA A L. Network level control of collaborative UAVs. California, USA: University of California, 2011.
4	MA C Y, FENG Z Q, ZHENG X M Development of bionic UAVs cluster technology. Transactions of Nanjing University of Aeronautics and Astronautics, 2018, 35 (1): 1- 8.
5	KHAN A, AFTAB F, ZHANG Z S UAPM: an urgency-aware packet management for disaster management using flying ad-hoc networks. China Communications, 2019, 16 (11): 167- 182.
6	ZAFAR Z, AWAIS M, JALEEL A, et al A distributed framework of autonomous drones for planning and execution of relief operations during flood situations. International Arab Journal of Information Technology, 2020, 18 (1): 16- 24. doi: 10.34028/iajit/18/1/3
7	VIDAL T, CRAINIC T G, GENDREAU M A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems. Operations Research, 2012, 60 (3): 611- 624. doi: 10.1287/opre.1120.1048
8	CRISTIAN R A, JAVIER D S, DAVID C Weighted strategies to guide a multi-objective evolutionary algorithm for multi-UAV mission planning. Swarm & Evolutionary Computation, 2019, 44, 480- 495.
9	THIBBOTUWAWA A, BOCEWICZ, G RADZKI G, et al UAV mission planning resistant to weather uncertainty. Sensors, 2020, 20 (2): 31963338. doi: 10.3390/s20020515
10	KURDI H A, EBTESAM A, MARAM A, et al Autonomous mission allocation for multi-UAV systems based on the locust elastic behavior. Applied Soft Computing, 2018, 71, 110- 126.
11	MOTLAGH N H, BAGAA M, TALEB T Energy and delay aware mission assignment mechanism for UAV-based IoT platform. IEEE Internet of Things Journal, 2019, 6 (4): 6523- 6536. doi: 10.1109/JIOT.2019.2907873
12	OH G, KIM Y, AHN J Market-based mission assignment for cooperative timing missions in dynamic environments. Journal of Intelligent & Robotic Systems, 2017, 87 (1): 97- 123.
13	CHEN H X, NAN Y, YANG Y Multi-UAV reconnaissance mission assignment for heterogeneous targets based on modified symbiotic organisms search algorithm. Sensors, 2019, 19 (3): 734- 754. doi: 10.3390/s19030734
14	GRIPPA P Decision making in a UAV-based delivery system with impatient customers. Proc. of the IEEE/RSJ International Conference on Intelligent Robots & Systems, 2016, 5034- 5039.
15	PADILLA G E G, KIM K J, PARK S H Flight path planning of solar-powered UAV for sustainable communication relay. IEEE Robotics and Automation Letters, 2020, 5 (4): 6772- 6779. doi: 10.1109/LRA.2020.3014635
16	YAO P, XIE Z X, REN P Optimal UAV route planning for coverage search of stationary target in river. IEEE Trans. on Control Systems Technology, 2019, 27 (2): 822- 829. doi: 10.1109/TCST.2017.2781655
17	MURRAY C, KARWAN M A branch-and-bound-based solution approach for dynamic rerouting of airborne platforms. Naval Research Logistics, 2013, 60 (2): 141- 159. doi: 10.1002/nav.21526
18	HUANG C Q, ZHAO K X, HAN B J, et al Maneuvering decision-making method of UAV based on approximate dynamic programming. Journal of Electronics & Information Technology, 2018, 40 (10): 2447- 2452.
19	LIN C E, SYU Y M GA/DP hybrid solution for UAV multi-target path planning. Journal of Aeronautics Astronautics and Aviation, 2016, 48 (3): 203- 220.
20	PONDA S S, JOHNSON L B, GERAMIFARD A, et al Cooperative mission planning for multi-UAV teams. Handbook of Unmanned Aerial Vehicles, Dordrechit: Spring, 2015.
21	ZHEN Z, XING D J, GAO C Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm. Aerospace Science & Technology, 2018, 76, 402- 411.
22	KIVANC O C An approach to improve the performance of cooperative unmanned vehicle team. Turkish Journal of Electrical Engineering & Computer Sciences, 2019, 27 (2): 1428- 1444.
23	HU C Y, LIU W D, YU T X, et al Analysis of multi task planning model based on UAV real-time data. Journal of Systems Engineering and Electronics, 2021, 43 (3): 747- 754.
24	PENG Y F, YU Q, LI Q Y Method of multi-object equipment support task planning based on improved particle swarm optimization. Journal of Systems Engineering and Electronics, 2017, 39 (3): 562- 568.
25	GOEZ G D, VELEZ R A V, VALENCIA J S B UAV route planning optimization using PSO implemented on microcontrollers. IEEE Latin America Transactions, 2016, 14 (4): 1705- 1710. doi: 10.1109/TLA.2016.7483504
26	SHIVGAN R, DONG Z Q. Energy-efficient drone coverage path planning using genetic algorithm. Proc. of the IEEE 21st International Conference on High Performance Switching and Routing, 2020: 1−6. DOI: 10.1109/HPSR48589.2020.9098989.
27	WU W N, WANG X G, CUI N G Fast and coupled solution for cooperative task planning of multiple heterogeneous unmanned aerial vehicles. Aerospace Science and Technology, 2018, 79, 131- 144. doi: 10.3390/app10124154
28	RADMANESHA M, KUMARB M, SARIMB M Grey wolf optimization-based sense and avoid algorithm in a Bayesian framework for multiple UAV path planning in an uncertain environment. Aerospace Science and Technology, 2018, 77, 168- 179.
29	GAO C, ZHEN Z Y, GONG H J A self-organized search and attack algorithm for multiple unmanned aerial vehicles. Aerospace Science and Technology, 2016, 54, 229- 240. doi: 10.3390/info11040226
30	LI P, DUAN H B A potential game approach to multiple UAV cooperative search and surveillance. Aerospace Science and Technology, 2017, 68, 403- 415. doi: 10.1016/j.ast.2017.05.031
31	LIU Q, SHI L, SUN L L. Path planning for UAV-mounted mobile edge computing with deep reinforcement learning. IEEE Trans. on Vehicular Technology 2020, 69(5): 5723−5728.
32	WANG B H, WU C, KE W J Intelligent planning method of combat mission based on probability graph. Journal of Systems Engineering and Electronics, 2020, 42 (12): 2795- 2801.
33	THI H A L, NGUYEN D M, DINH T P Globally solving a nonlinear UAV mission assignment problem by stochastic and deterministic optimization approaches. Optimization Letters, 2012, 6, 315- 329. doi: 10.1007/s11590-010-0259-x
34	EDISON E, SHIMA T Integrated mission assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Computers & Operations Research, 2011, 38 (1): 340- 356.
35	FOSSEN T I, PETTERSEN K Y, GALEAZZI R Line-of-sight path following for Dubins paths with adaptive sideslip compensation of drift forces. IEEE Trans. on Control Systems Technology, 2015, 23 (2): 820- 827. doi: 10.1109/TCST.2014.2338354
36	DUBINS L E On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 1957, 79 (3): 497- 516. doi: 10.2307/2372560
37	SHKEL A M, LUMELSKY V Classification of the Dubins set. Robotics & Autonomous Systems, 2001, 34 (4): 179- 202.
38	LIKAS A, VLASSIS N, VERBEEK J J The global k-means clustering algorithm. Pattern Recognition, 2003, 36 (2): 451- 461. doi: 10.1016/S0031-3203(02)00060-2
39	MODHA D S, SPANGLER W S Feature weighting in k-means clustering . Machine Learning, 2003, 52, 217- 237. doi: 10.1023/A:1024016609528
40	RODRIGUEZ A, LAIO A Clustering by fast search and find of density peaks. Science, 2014, 344 (6191): 1492- 1496. doi: 10.1126/science.1242072
41	RUBINSTEIN R Y Optimization of computer simulation models with rare events. European Journal of Operational Research, 1997, 99, 89- 112. doi: 10.1016/S0377-2217(96)00385-2
42	RUBINSTEIN R Y The cross-entropy method for combinatorial and continuous optimization. Methodology and Computing in Applied Probability, 1999, 2, 127- 190.
43	BOER P T D, KROESE D P, MANNOR S A tutorial on the cross-entropy method. Annals of Operations Research, 2005, 134, 19- 67. doi: 10.1007/s10479-005-5724-z

Parameter	Definition	Parameter	Definition
$ \tau $	Time	$ {v_i} $	Velocity of UAV i
$ \varepsilon $	Type of UAV sensor, type of targets	$ r_i^{\min } $	Minimum turning radius of UAVi
$ {N_T} $	Number of all targets in mission area	$ d $	Dubins path of any two points
$ {N_R} $	Number of UAVs	$ {N_{Ti}} $	Number of targets visited by UAV i
$ L_i^{\max } $	Maximum voyage of UAV i	$ {n_i} $	Number of nodes visited by UAV i
$ p\left( {i;\varepsilon } \right) $	Indicator function, sensor type loaded in UAV i	$ {M_{Ri}} $	PDM of reconnaissance mission corresponding to UAVi
$ q\left( {j;\varepsilon } \right) $	Indicator function, the type of target j	$ {X_{Ri}} $	Decision vector of UAV i
$ I\left( {i;j} \right) $	Indicator function, whether the target j can be detected by UAVi	${S_{ Ri} }$	Voyage distance cost function of UAV i
$ r\left( {i;j} \right) $	Indicator function, whether the target j is detected by UAV i	${S_ R}$	Total voyage distance cost function of UAVs
$ h\left( {i;\tau } \right) $	Indicator function, the healthy state of UAV i at time $ \tau $	$ {N_S} $	Sampling number
K	K sub-missions	PDM	Probability density matrix

Parameter	Shape
Parameter	Square	Hexagons	Triangle	Diamond	Star
Target type	a	b	c	d	e

UAV	Loaded sensors	Maximum voyage/km	Flight velocity/(m·s⁻¹)	Minimum turning radius/m
UAV 1	a, b, c	210	180	760
UAV 2	b, c, d	180	200	800
UAV 3	a, b, c, d	220	165	700
UAV 4	b, c, d, e	200	170	700
UAV 5	a, c, e	180	210	820
UAV 6	c, d, e	210	190	780
UAV 7	a, b, c, d, e	230	150	660

Method	Parameter	Parameter setting rule
RMP-ISCE	N_s	200
RMP-ISCE	$\theta $	0.4
	T	500
OPSO, GADO, IDACO	Num	200
OPSO, GADO, IDACO	D	500
MC	NMC	$ {10^6} $

Parameter	Submission area
Parameter	1	2	3
Number of targets	18	15	15
UAV code	UAV 1	UAV 2	UAV 6

A multiple heterogeneous UAVs reconnaissance mission planning and re-planning algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 22

References 43

Related Articles 2

Recommended Articles

Metrics

Comments

UAV serial number	Time/s	Healthy state	Remaining target	Re-assignment
UAV 1	−	Healthy	22,1,31,9,3,26,42,41,46,45	18
UAV 2	354	Damaged	19,18	−
UAV 6	−	Healthy	25,17,11,7	19

UAV serial number	Before/km	After/km	Total voyage distance/km
UAV1	63.72	75.44	139.16
UAV2	70.8	−	70.8
UAV6	67.26	58.2	125.46

[1]	Wu Hao & Zuo Hongfu. Using genetic/simulated annealing algorithm to solve disassembly sequence planning [J]. Journal of Systems Engineering and Electronics, 2009, 20(4): 906-912.
[2]	Li Bo , Li Xinjun & Ζhao Zhiyan. Novel algorithm for constructing support vector machine regression ensemble [J]. Journal of Systems Engineering and Electronics, 2006, 17(3): 541-545.