Area coverage path planning for tilt-rotor unmanned aerial vehicle based on enhanced genetic algorithm

doi:10.3785/j.issn.1008-973X.2024.10.006

Journal of ZheJiang University (Engineering Science)

2024, Vol. 58

Issue (10): 2031-2039 DOI: 10.3785/j.issn.1008-973X.2024.10.006

Area coverage path planning for tilt-rotor unmanned aerial vehicle based on enhanced genetic algorithm

Yue’an WU(

),Changping DU*(

),Rui YANG,Jiahao YU,Tianrui FANG,Yao ZHENG

School of Aeronautics and Astronautics, Zhejiang University, Hangzhou 310027, China

Download:

HTML

PDF(2211KB) HTML
Export: BibTeX | EndNote (RIS)

Abstract

An enhanced genetic algorithm was proposed to address the challenge of area coverage path planning for a tilt-rotor unmanned aerial vehicle (TRUAV) amidst multiple obstacles. A preliminary coverage path plan for the designated task area was devised, utilizing the minimum spanning and back-and-forth path generation algorithms. The area coverage dilemma was transformed into a traveling salesman problem to optimize the sequence of the coverage path. A fishtail-shaped obstacle avoidance strategy was proposed to circumvent obstacles within the region. The nearest neighbor algorithm was introduced to generate a superior initial population than a genetic algorithm. A three-point crossover operator and a dynamic interval mutation operator were adopted in the genetic processes to improve the proposed algorithm's global search capacity and prevent the algorithm from falling into local optima. The efficacy of the proposed algorithm was rigorously tested through simulations in polygonal areas with multiple obstacles. Results showed that, compared to the sequential path coverage algorithm and the genetic algorithm, the proposed algorithm reduced the length of the coverage path by 7.80%, significantly enhancing the coverage efficiency of TRUAV in the given task areas.

Key words： tilt-rotor unmanned aerial vehicle area coverage genetic algorithm local obstacle avoidance Dubins curve

Received: 14 September 2023 Published: 27 September 2024

CLC:

TP 249

Corresponding Authors: Changping DU E-mail: yawu@zju.edu.cn;duchangping@zju.edu.cn

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Yue’an WU
	Changping DU
	Rui YANG
	Jiahao YU
	Tianrui FANG
	Yao ZHENG

Cite this article:

Yue’an WU,Changping DU,Rui YANG,Jiahao YU,Tianrui FANG,Yao ZHENG. Area coverage path planning for tilt-rotor unmanned aerial vehicle based on enhanced genetic algorithm. Journal of ZheJiang University (Engineering Science), 2024, 58(10): 2031-2039.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2024.10.006 OR https://www.zjujournals.com/eng/Y2024/V58/I10/2031

基于改进遗传算法的倾转旋翼无人机区域覆盖路径规划

基于改进遗传算法研究倾转旋翼无人机（TRUAV）在多障碍物约束下的区域覆盖路径规划问题. 运用最小跨度算法和往返路径生成算法进行任务区域内的覆盖路径初规划，将区域覆盖问题转化为旅行商问题以优化覆盖路径顺序. 为了避开区域内的障碍物，提出鱼尾形避障策略. 引入最近邻算法，生成比传统遗传算法质量更高的初始种群，设计三点式交叉算子和动态区间变异算子进行遗传操作以提高所提算法的全局搜索能力，避免算法陷入局部最优. 在含多个障碍物的多边形区域算例内仿真验证所提算法的性能. 结果表明，相比于逐行路径覆盖算法和传统遗传算法，所提算法的覆盖路径长度减少了7.80%，TRUAV的任务区域覆盖效率显著提升.

关键词： 倾转旋翼无人机, 区域覆盖, 遗传算法, 局部避障, 杜宾斯曲线

Fig.1 Task area of coverage path planning

Fig.2 Camera field of view for tilt-rotor unmanned aerial vehicle

Fig.3 Supporting parallel lines of task area

Fig.4 Flight direction of tilt-rotor unmanned aerial vehicle

Fig.5 Detection range of fishtail-shaped obstacle avoidance strategy

Fig.6 Workflow of fishtail-shaped obstacle avoidance strategy

Fig.7 Workflow of Dubins-based enhanced genetic algorithm

Fig.8 Sequence number of coverage path

Fig.9 Three-point crossover operator

Fig.10 Dynamic interval mutation operator

Fig.11 Prototype of tilt-rotor unmanned aerial vehicle

Fig.12 Turning strategy of Dubins-based enhanced genetic algorithm

Fig.13 Paths planned by different algorithms covering quadrilateral region

Fig.14 Paths planned by different algorithms covering pentagon region

Tab.1 Performance comparison of region-covering path algorithms (quadrilateral region)

Tab.2 Performance comparison of region-covering path algorithms (pentagon region)


[1]	TANG G, TANG C, ZHOU H, et al R-DFS: a coverage path planning approach based on region optimal decomposition[J]. Remote Sensing, 2021, 13 (8): 1525 doi: 10.3390/rs13081525

[2]	LOTTES P, KHANNA R, PFEIFER J, et al. UAV-based crop and weed classification for smart farming [C]// 2017 IEEE International Conference on Robotics and Automation . Singapore: IEEE, 2017: 3024–3031.

[3]	VAN PHAM H, LAM T N A new method using knowledge reasoning techniques for improving robot performance in coverage path planning[J]. International. Journal of Computer Applications in Technology, 2019, 60 (1): 57- 64 doi: 10.1504/IJCAT.2019.099503

[4]	YAO P, XIE, Z, REN P Optimal UAV route planning for coverage search of stationary target in river[J]. IEEE Transactions on Control System Technology, 2019, 27 (2): 822- 829 doi: 10.1109/TCST.2017.2781655

[5]	BASIRI A, MARIANI V, SILANO G, et al A survey on the application of path-planning algorithms for multi-rotor UAVs in precision agriculture[J]. The Journal of Navigation, 2022, 75 (2): 364- 383 doi: 10.1017/S0373463321000825

[6]	PANG B, SONG Y, ZHANG C, et al Effect of random walk methods on searching efficiency in swarm robots for area exploration[J]. Applied Intelligence, 2021, 51: 5189- 5199 doi: 10.1007/s10489-020-02060-0

[7]	XIE J, CARRILLO L R G, JIN L An integrated traveling salesman and coverage path planning problem for unmanned aircraft systems[J]. IEEE Control Systems Letters, 2019, 3 (1): 67- 72 doi: 10.1109/LCSYS.2018.2851661

[8]	TAN C S, MOHD-MOKHTAR R, ARSHAD M R A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms[J]. IEEE Access, 2021, 9: 119310- 119342 doi: 10.1109/ACCESS.2021.3108177

[9]	KAN X, TENG H, KARYDIS K. Multi-robot field exploration in hex-decomposed environments for Dubins vehicles [C]// 2019 IEEE International Conference on Robotics and Biomimetics . Dali: IEEE, 2019: 449-455.

[10]	CHEN J, LING F, ZHANG Y, et al Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system[J]. Swarm and Evolutionary Computation, 2022, 69: 101005 doi: 10.1016/j.swevo.2021.101005

[11]	TUNG W, LIU J Solution of an integrated traveling salesman and coverage path planning problem by using a genetic algorithm with modified operators[J]. IADIS International Journal on Computer Science and Information Systems, 2019, 14 (2): 95- 114 doi: 10.33965/ijcsis_2019140206

[12]	LE A V, PARWEEN R, KYAW P T, et al Reinforcement learning-based energy-aware area coverage for reconfigurable hRombo tiling robot[J]. IEEE Access, 2020, 8: 209750- 209761 doi: 10.1109/ACCESS.2020.3038905

[13]	CHEN X, TUCKER T M, KURFESS T R, et al. Adaptive deep path: efficient coverage of a known environment under various configurations [C]// 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems . Macau: IEEE, 2019: 3549–3556.

[14]	杜楠楠, 陈建, 马奔, 等多太阳能无人机覆盖路径优化方法[J]. 航空学报, 2021, 42 (6): 324476 DU Nannan, CHEN Jian, MA Ben, et al Optimization method for coverage path planning of multi-solar powered UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42 (6): 324476

[15]	TNUNAY H, MOUSSA K, HABLY A, et al. Virtual leader based trajectory generation of UAV formation for visual area coverage [C]// IECON 2021 - 47th Annual Conference of the IEEE Industrial Electronics Society . Toronto: IEEE, 2021: 1–6.

[16]	KUČEROVÁ K, VÁŇA P, FAIGL J. Variable-speed traveling salesman problem for vehicles with curvature constrained trajectories [C]// 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems . Prague: IEEE, 2021: 4714–4719.

[17]	YUAN J, LIU Z, LIAN Y, et al. Global optimization of UAV area coverage path planning based on good point set and genetic algorithm[J]. Aerospace, 2022, 9 (2): 86 doi: 10.3390/aerospace9020086

[18]	XIE J, L CARRILLO L R G, JIN L. Path planning for UAV to cover multiple separated convex polygonal regions[J]. IEEE Access, 2020, 8: 51770- 51785 doi: 10.1109/ACCESS.2020.2980203

[19]	李文广, 胡永江, 孙世宇, 等基于最小转弯半径的无人机转弯航迹规划算法[J]. 计算机工程与设计, 2019, 40 (10): 2849- 2854 LI W, HU Y, SUN S, et al UAV turning path planning algorithm based on minimum turning radius[J]. Computer Engineering and Design, 2019, 40 (10): 2849- 2854

[1]	Yunchen ZHU,Mingjun CHENG,Xinwen ZHENG,Peili CEN,Xiangshuo XI,Shan HUANG,Chen HUA,Hai HUANG. Fuzzy location selection of urban emergency facilities based on optimized non-dominated sorting genetic algorithm III[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(9): 1832-1843.

[2]	Yali XUE,Hanyan LI,Quan OUYANG,Shan CUI,Jun HONG. Multi-UAVs collaborative task allocation based on genetic slime mould algorithm in battlefield environment[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(8): 1748-1756.

[3]	Jie ZHAO,Feng LIU,Ling XIA,Yifeng FAN. Passive shimming optimization method of MRI based on genetic algorithm-sequential quadratic programming[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(6): 1305-1314.

[4]	Lifeng LI,Kun HOU,Deqiang ZOU,Hao PENG,Lingxiao LI. Optimization of section layout of steel plate composite beam with medium span[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(3): 510-517.

[5]	Peng LIU,Qingchang LU,Han QIN,Xin CUI. Road network multi-stage disaster resistance optimization model and its application[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(1): 96-108.

[6]	Huang LI,Hong-juan GE,Ying MA,Yong-shuai WANG. Parameters optimization design of dual-input dual-buck inverter system based on hyperplane NSGA-II[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(3): 606-615.

[7]	Li-li XU,Yan ZHAN,Jian-sha LU,Yi-ding LANG. Compound operation scheduling optimization in four-way shuttle warehouse system[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(11): 2188-2199.

[8]	Hao ZHA,Shao-hua FEI,Yun FU,Zhen LV,Wei-dong ZHU. Online decoupling technology of six-dimensional force sensor based on EtherCAT bus[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(10): 2042-2050.

[9]	Yong-sheng ZHAO,Rui-xiang LI,Na-na NIU,Zhi-yong ZHAO. Shape control method of fuselage driven by digital twin[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(7): 1457-1463.

[10]	Bao-feng SUN,Xin-kang ZHANG,Gen-dao LI,Jiao-jiao LIU. Joint decision-making of balancing and sequencing for type-II robotic mixed-model assembly line[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(6): 1097-1106.

[11]	Xin-ying ZHANG,Lu CHEN,Wen-hui YANG. A parallel-machine scheduling problem with time-changing effect and preventive maintenance[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 408-418.

[12]	Hong-hao HU,Xiu-juan LI,Jun-feng YU,Qing-zhou ZHANG,Jing-qing LIU. Quantitative identification of inflow and infiltration of sanitary sewer system based on coupling simulation[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(11): 2313-2320.

[13]	Yi-quan ZOU,Hao-zhou HUANG,Xu-yong XIA,Xin WANG. Design optimization of curved curtain wall based on genetic algorithm under cost orientation[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(10): 2049-2056.

[14]	Sheng-tao XIANG,Da WANG. Model interactive modification method based on improved quantum genetic algorithm[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(1): 100-110.

[15]	Fei JU,Wei-chao ZHUANG,Liang-mo WANG,Jing-xing LIU,Qun WANG. Velocity planning strategy for economic cruise of hybrid electric vehicles[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(8): 1538-1547.

Viewed

Full text

Abstract

Cited

Shared

Discussed