UAV's Coverage Search Planning Algorithm Based on Action Combinations

doi:10.1007/s12204-018-2010-1

Abstract

Abstract: The autonomous route planning in coverage search is an important subject of unmanned aerial vehicle (UAV) mission planning. Pre-planning is simple and feasible for the coverage search mission of single UAV in regular areas. As to the dynamic mission in complicated environment of multi-UAV, the route planning will encounter the difficulties of reasonable task distribution and the real-time environment changes which include the changes of the mission area, the detection of threat area, the interference of communication and so on. At this point, making the UAV to do real-time autonomous planning is necessary. However, it is hard to fulfil requirements of real-time, autonomous and efficient at the same time. According to a scalable knowledge base, this paper proposes a coverage search algorithm which is based on the mapping between the basic behavior combination and surroundings. A UAV’s coverage search simulation model with random shapes is built with a discrete map to update the environment and the changes of the mission on time. Comparison of the simulation analysis and the dynamic programming shows that the method has amazing expandability and can change the search strategy feasibly. It is efficient, and the ratio of coverage redundancy can be decreased to 1.21. It also has the potentiality in real-time calculation, and the computing time can be shortened to about 2 s.

Key words: unmanned aerial vehicle (UAV)| coverage search| action combinations| search strategy| dynamic programming

摘要： The autonomous route planning in coverage search is an important subject of unmanned aerial vehicle (UAV) mission planning. Pre-planning is simple and feasible for the coverage search mission of single UAV in regular areas. As to the dynamic mission in complicated environment of multi-UAV, the route planning will encounter the difficulties of reasonable task distribution and the real-time environment changes which include the changes of the mission area, the detection of threat area, the interference of communication and so on. At this point, making the UAV to do real-time autonomous planning is necessary. However, it is hard to fulfil requirements of real-time, autonomous and efficient at the same time. According to a scalable knowledge base, this paper proposes a coverage search algorithm which is based on the mapping between the basic behavior combination and surroundings. A UAV’s coverage search simulation model with random shapes is built with a discrete map to update the environment and the changes of the mission on time. Comparison of the simulation analysis and the dynamic programming shows that the method has amazing expandability and can change the search strategy feasibly. It is efficient, and the ratio of coverage redundancy can be decreased to 1.21. It also has the potentiality in real-time calculation, and the computing time can be shortened to about 2 s.

关键词: unmanned aerial vehicle (UAV)| coverage search| action combinations| search strategy| dynamic programming

CLC Number:

V 279
TP 242

CHEN Zirong *(陈仔荣), LU Yafei (鲁亚飞), HOU Zhongxi (侯中喜), WANG Junwei (王俊伟). UAV's Coverage Search Planning Algorithm Based on Action Combinations[J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(1): 48-57.

References 23

[1]	WEI R X, LI X R. Advance unmanned aerial vehiclesystem and operational application [M]. Beijing,China: National Defense Industry Press, 2014 (in Chinese).
[2]	YU S N, ZHOU R, XIA J, et al. Decomposition andcoverage of multi-UAV cooperative search area [J].Journal of Beijing University of Aeronautics and Astronautics,2015, 41(1): 167-173 (in Chinese).
[3]	TORRES M, PELTA D A, VERDEGAY J L, et al.Coverage path planning with unmanned aerial vehiclesfor 3D terrain reconstruction [J]. Expert Systems withApplications, 2016, 55: 441-445.
[4]	CHEN H, WANG X M, JIAO Y S, et al. An algorithmof coverage flight path planning for UAVs in convexpolygon areas [J]. Acta Aeronautica et AstronauticaSinica, 2010, 31(9): 1802-1808 (in Chinese).
[5]	GUO W Q, ZHU Z, HOU Y Y. Bayesian networkbased cooperative area coverage searching for UAVs[C]//Frontiers in Computer Education AISC 133.Berlin, Germany: AISC, 2012: 611-618.
[6]	CHEN H, HE K F, QIAN W Q. Cooperative coveragepath planning for multiple UAVs [J]. Acta Aeronauticaet Astronautica Sinica, 2016, 37(3): 928-935 (inChinese).
[7]	SHEN Y H, ZHOU Z, ZHU X P. Research on cooperativereconnaissance/suppression path planning forAUAVs [J]. Fire Control and Command Control, 2008,33(9): 64-67 (in Chinese).
[8]	SUN X L, QI N M, DONG C, et al. Cooperative controlalgorithm of task assignment and path planningfor multiple UAVs [J]. Systems Engineering and Electronic,2015, 37(12): 2772-2776 (in Chinese).
[9]	SHEN D,WEI R X, RU C J. Digital-pheromone-basedcontrol method for UAV swarm search [J]. SystemsEngineering and Electronic, 2013, 35(3): 591-596 (inChinese).
[10]	WEI R X, ZHOU K, RU C J, et al. Study on fuzzycognitive decision-making method for multiple UAVscooperative search [J]. Scientia Sinica (Technologica),2015, 45(6): 595-601 (in Chinese).
[11]	GAO C, ZHEN Z Y, GONG H J. A self-organizedsearch and attack algorithm for multiple unmannedaerial vehicles [J]. Aerospace Science and Technology,2016, 54: 229-240.
[12]	BAMHART R K, HOTTMAN S B, MARSHALL D M,et al. Introduction to unmanned aircraft systems [M].SHEN L C (trans). Beijing, China: National DefenseIndustry Press, 2014 (in Chinese).
[13]	CHEN Z J, WEI J Z, WANG Y X, et al. UAV autonomouscontrol levels and system structure [J]. ActaAeronautica et Astronautica Sinica, 2011, 36(6): 1075-1083 (in Chinese).
[14]	CHEN Y, ZHANG D H, ZHAO X G, et al. UAV 3Dpath planning based on IHDR autonomous-learningframework[J]. Robot, 2012, 34(5): 513-518 (inChinese).
[15]	CHEN R G, LI C S, CHEN J, et al. Optimization ofnear-space aerocraft track for regional coverage basedon greedy algorithm [J]. Journal of Beijing Universityof Aeronautics and Astronautics, 2009, 35(5): 547-550(in Chinese).
[16]	WU R. Research on multi-UAVs cooperative pathplanning based on hierarchy decomposition strategy[D]. Nanjing, China: College of Automation Engineering,Nanjing University of Aeronautics and Astronautics,2012 (in Chinese).
[17]	TIAN J, CHEN Y, SHEN L C. Cooperative searchalgorithm for multi-UAVs in uncertainty environment[J]. Journal of Electronics & Information Technology,2007, 29(10): 2325-2328 (in Chinese).
[18]	JIN Y N, WU Y X, FAN N J. Distributed cooperativecontrol of swarm UAVs for dynamics environmentpersistent coverage [J]. Transactions of Beijing Instituteof Technology, 2016, 36(6): 588-592 (in Chinese).
[19]	LU C, WU Q X, JIANG C S. On reconnaissance pathplanning of UAV [J]. Electronics Optics & Control,2010, 17(3): 35-39 (in Chinese).
[20]	PEI H, SHEN L C, ZHU H Y. Multiple UAV cooperativearea search based on distributed model predictivecontrol [J]. Acta Aeronautica et Astronautica Sinica,2010, 31(3): 593-601 (in Chinese).
[21]	WANG M, ZHANG W P, CHEN H. Modeling andsimulation on maneuvering actions of UAV based ontemplate [J]. Fire Control & Command Control, 2016,41(8): 15-19 (in Chinese).
[22]	WANG G, YU X C, BU S H, et al. Unmanned aerialvehicle surveying and mapping technology and application[M]. Beijing, China: Surveying and MappingPublishing House, 2015 (in Chinese).
[23]	NORIEGA A, ANDERSON R. Linear-optimizationbasedpath planning algorithm for an agricultural UAV[C]//AIAA Infotech. San Diego, USA: AIAA, 2016:1003.