Multi-objective path planning based on improved RRT and GA: a case study of UAV forest patrol

Zhang Biao; Kang Feng; Xu Shuting

doi:10.12171/j.1000-1522.20240356

Journal of Beijing Forestry University > 2025 > Accepted Manuscript > DOI: 10.12171/j.1000-1522.20240356

Zhang Biao, Kang Feng, Xu Shuting. Multi-objective path planning based on improved RRT and GA: a case study of UAV forest patrol[J]. Journal of Beijing Forestry University. DOI: 10.12171/j.1000-1522.20240356

Citation:

PDF (22929 KB)

Multi-objective path planning based on improved RRT and GA: a case study of UAV forest patrol

School of Technology, Beijing Forestry University, Beijing 100083, China

More Information

Received Date: October 27, 2024
Revised Date: January 07, 2025
Accepted Date: March 12, 2025
Available Online: March 17, 2025

Graphical Abstract

Abstract

Abstract

Objective
To address the path planning problem of UAVs in artificial forest areas for inspection tasks (such as pest and disease monitoring and fire prevention), which involves solving the optimal traversal sequence of inspection points and generating collision-free flight trajectories, this paper proposes a multi-objective path planning algorithm by integrating and improving the rapidly-exploring random tree (RRT) algorithm and genetic algorithm (GA).
Method
First, the traditional GA was improved to enable traversal of all inspection points in 3D space and solve the optimal sequence. Second, based on this sequence, the path search was conducted by improving the random sampling principle of the RRT algorithm. Obstacle avoidance was achieved through target and tree-avoidance strategies, and redundant turning points generated by obstacle avoidance were eliminated by continuously selecting parent nodes. Finally, the final path was generated through three iterations of B-spline curve optimization.
Result
Simulation results show that the proposed algorithm can traverse all inspection points and plan high-quality, collision-free paths in complex forest environments within a short time. Compared with particle swarm optimization (PSO), ant colony optimization (ACO), and RRT algorithms, when the number of inspection points increased from 3 to 9, the search times of PSO, ACO, and RRT algorithms increased by 221.77%, 332.42%, and 184.78%, respectively, while the proposed algorithm only increased by 102.35%. In a complex environment with 9 inspection points, the path cost of the proposed algorithm was reduced by 14.46%, 30.28%, and 24.76% compared with PSO, ACO, and RRT algorithms, respectively. The path quality was significantly improved, eliminating path crossing and overlap. Additionally, the algorithm was successfully validated through simulation flights on forest point clouds using a UAV on the ROS platform, demonstrating its applicability for multi-objective path planning in forest inspections.
Conclusion
For the path planning problem of UAVs in artificial forest inspections, the proposed algorithm successfully planned a collision-free path that traversed all inspection points while avoiding obstacles in the forest. Compared with PSO, ACO, and RRT algorithms, the proposed algorithm showed significant advantages in path quality, path cost, and search time.

FullText(HTML)

References (29)

References

[1]	杨兰, 孟凡烨. 林火防控中多旋翼无人机的应用分析[J]. 林业科技情报, 2020, 52(4): 105−107. doi: 10.3969/j.issn.1009-3303.2020.04.035 Yang L, Meng F Y. Application analysis of multi-rotor UAV in forest fire prevention and control[J]. Forestry Science and Technology Information, 2020, 52(4): 105−107. doi: 10.3969/j.issn.1009-3303.2020.04.035
[2]	徐凯男, 朱红伟. 无人机在森林防火中的应用研究[J]. 林业机械与木工设备, 2024, 52(8): 57−60. doi: 10.3969/j.issn.2095-2953.2024.08.010 Xu K N, Zhu H W. Research on the application of UAV in forest fire prevention[J]. Forestry Machinery & Woodworking Equipment, 2024, 52(8): 57−60. doi: 10.3969/j.issn.2095-2953.2024.08.010
[3]	Li J, Kang F, Chen C, et al. The improved A* algorithm for quadrotor UAVs under forest obstacle avoidance path planning[J]. Applied Sciences, 2023, 13(7): 4290. doi: 10.3390/app13074290
[4]	马力, 江东晓, 辛明翰, 等. 基于农机智能管理平台的田间燃油配给策略[J]. 农业工程学报, 2024, 40(15): 22−33. Ma L, Jiang D X, Xin M H, et al. Fuel rationing strategy in farmland based on intelligent management platform for agricultural machinery[J]. Transactions of the Chinese Society of Agricultural Engineering, 2024, 40(15): 22−33.
[5]	Vonásek V, Pěnička R. Space-filling forest for multi-goal path planning[C]//2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA). Zaragoza: IEEE, 2019: 1587-1590.
[6]	Sun C. A study of solving traveling salesman problem with genetic algorithm[C]//2020 9th International Conference on Industrial Technology and Management (ICITM). Oxford: IEEE, 2020: 307-311.
[7]	Wurll C, Henrich D, Wörn H. Multi-goal path planning for industrial robots[J]. International Conference on Robotics and Application, 1999, 18: 1−7.
[8]	Spitz S N, Requicha A A. Multiple-goals path planning for coordinate measuring machines[C]//Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings. San Francisco: IEEE, 2000: 2322-2327.
[9]	Yang H, Lu X, Zhou X, et al. Expected length of the shortest path of the traveling salesman problem in 3D space[J]. Journal of Advanced Transportation, 2022(1): 4124950.
[10]	Yang B, Li W, Wang J, et al. A novel path planning algorithm for warehouse robots based on a two-dimensional grid model[J]. IEEE Access, 2020, 8: 80347−80357. doi: 10.1109/ACCESS.2020.2991076
[11]	陈璐, 魏文红. 基于改进自适应遗传算法的旅行商问题研究[J]. 东莞理工学院学报, 2024, 31(5): 1−8. Chen L, Wei W H. Research on travelling salesman problem based on improved adaptive genetic algorithm[J]. Journal of Dongguan University of Technology, 2024, 31(5): 1−8.
[12]	韦念念, 韩曙光. 基于图卷积和注意力神经网络的旅行商问题新解法[J]. 计算机科学, 2024, 51(增刊1): 222−229. doi: 10.11896/jsjkx.230700222 Wei N N, Han S G. New solution for traveling salesman problem based on graph convolution and attention neural network[J]. Computer Science, 2024, 51(Suppl.1): 222−229. doi: 10.11896/jsjkx.230700222
[13]	刘孟莹, 秦进, 陈双. 求解动态旅行商问题的蚁群优化算法新策略[J]. 计算机仿真, 2024, 41(8): 349−355. doi: 10.3969/j.issn.1006-9348.2024.08.061 Liu M Y, Qing J, Chen S. Novel strategy of ant colony optimization for dynamic traveling salesman problem[J]. Computer Simulation, 2024, 41(8): 349−355. doi: 10.3969/j.issn.1006-9348.2024.08.061
[14]	Kuffner J J, La Valle S M. RRT-connect: an efficient approach to single-query path planning[C]//Proceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings. San Francisco: IEEE, 2000: 995-1001.
[15]	Jeong I B, Lee S J, Kim J H. Quick-RRT: triangular inequality-based implementation of RRT with improved initial solution and convergence rate[J]. Expert Systems with Applications, 2019, 123: 82−90. doi: 10.1016/j.eswa.2019.01.032
[16]	Gammell J D, Srinivasa S S, Barfoot T D. Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//2014 IEEE/RSJ international conference on intelligent robots and systems. Chicago: IEEE, 2014: 2997-3004.
[17]	Gammell J D, Srinivasa S S, Barfoot T D. Batch informed trees (BIT*): sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs[C]//2015 IEEE international conference on robotics and automation (ICRA). Seattle: IEEE, 2015: 3067-3074.
[18]	吴宇, 胡莘婷. 城市低空环境中多旋翼无人机在线航线规划方法[J]. 控制与决策, 2021, 36(12): 2851−2860. Wu Y, Hu X T. An online route planning method for multi-rotor drone in urban environments[J]. Control and Decision, 2021, 36(12): 2851−2860.
[19]	栾添添, 王皓, 孙明晓, 等. 基于动态变采样区域RRT的无人车路径规划[J]. 控制与决策, 2023, 38(6): 1721−1729. Luan T T, Wang H, Sun M X, et al. Path planning of unmanned vehicle based on dynamic variable sampling area RRT[J]. Control and Decision, 2023, 38(6): 1721−1729.
[20]	Kang J G, Lim D W, Choi Y S, et al. Improved RRT-connect algorithm based on triangular inequality for robot path planning[J]. Sensors, 2021, 21(2): 333. doi: 10.3390/s21020333
[21]	Wang B, Ju D, Xu F, et al. CAF-RRT*: a 2D path planning algorithm based on circular arc fillet method[J]. IEEE Access, 2022, 10: 127168−127181. doi: 10.1109/ACCESS.2022.3226465
[22]	Zhong H, Cong M, Wang M, et al. HB-RRT: a path planning algorithm for mobile robots using halton sequence-based rapidly-exploring random tree[J]. Engineering Applications of Artificial Intelligence, 2024, 133: 1952−1976.
[23]	Faigl J. An application of self-organizing map for multirobot multigoal path planning with minmax objective[J]. Computational Intelligence and Neuroscience, 2016(1): 2720630.
[24]	Cui X, Wang Y, Yang S, et al. UAV path planning method for data collection of fixed-point equipment in complex forest environment[J]. Frontiers in Neurorobotics, 2022, 16: 1105177. doi: 10.3389/fnbot.2022.1105177
[25]	Englot B, Hover F. Multi-goal feasible path planning using ant colony optimization[C]//2011 IEEE International Conference on Robotics and Automation. Shanghai: IEEE, 2011: 2255-2260.
[26]	Diaz-Arango G, Vazquez-Leal H, Hernandez-Martinez L, et al. Multiple-target homotopic quasi-complete path planning method for mobile robot using a piecewise linear approach[J]. Sensors, 2020, 20(11): 3265. doi: 10.3390/s20113265
[27]	Punnen A P. The traveling salesman problem and its variations[M]. Boston, MA: Springer US, 2007.
[28]	Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transaction on Systems, Man and Cybernetics, 1994, 24(4): 656−667. doi: 10.1109/21.286385
[29]	Zhou B, Gao F, Wang L, et al. Robust and efficient quadrotor trajectory generation for fast autonomous flight[J]. IEEE Robotics and Automation Letters, 2019, 4(4): 3529−3536. doi: 10.1109/LRA.2019.2927938

[1]	Yi Ziyue, Li Junjie, Sun Hailong, Chen Meiqing, Li Shuang, Xiang Wei. Contribution rate of climate factors to radial growth of main coniferous species in spurce-fir conifer mixed forest of northeastern China[J]. Journal of Beijing Forestry University, 2024, 46(5): 55-63. DOI: 10.12171/j.1000-1522.20220332
[2]	Sun Yanan, Liu Yajing, Sun Zhao, Luo Mi, Zhang Yungen, Sun Yujun. Radial growth of Cunninghamia lanceolata and its response to climate in Jiangle National Forest Farm, Fujian Province of eastern China[J]. Journal of Beijing Forestry University, 2024, 46(2): 18-27. DOI: 10.12171/j.1000-1522.20220373
[3]	Gong Xiaoqing, Xie Rong, Yang Hua. Response of radial growth of three common tree species to climate change in a spruce-fir mixed stand in Changbai Mountain of northeastern China[J]. Journal of Beijing Forestry University, 2023, 45(4): 1-10. DOI: 10.12171/j.1000-1522.20210479
[4]	Wang Tong, Sun Yujun, Qiao Jingjing. Response of Pinus massoniana tree-ring width in the Jiangle Area of Fujian Province to climate change[J]. Journal of Beijing Forestry University, 2019, 41(9): 30-39. DOI: 10.13332/j.1000-1522.20190067
[5]	Zhang Xiao, Pan Leilei, Semyung Kwon, Liu Yanshu, Yang Xiaohui, Shi Zhongjie. Climatological response of radial growth for Pinus sylvestris var. mongolica to drought in Hulun Buir Sandland, Inner Mongolia of northern China[J]. Journal of Beijing Forestry University, 2018, 40(7): 27-35. DOI: 10.13332/j.1000-1522.20170467
[6]	YAN Bo-qian, LIN Wan-zhong, LIU Qi-jing, YU Jian. Age-dependent radial growth responses of Larix chinensis to climatic factors in Qinling Mountains, northwestern China[J]. Journal of Beijing Forestry University, 2017, 39(9): 58-65. DOI: 10.13332/j.1000-1522.20170161
[7]	YU Jia-lin, ZHANG Wei-guo, TIAN Kun, SONG Wei-hong, LI Qiu-ping, YANG Rong, ZHANG Yun. Response of radial growth of three conifer trees to climate change at their upper distribution limits in Potatso National Park, Shangri-La, southwestern China[J]. Journal of Beijing Forestry University, 2017, 39(1): 43-51. DOI: 10.13332/j.1000-1522.20160184
[8]	GAO Lu-shuang, WANG Xiao-ming, ZHAO Xiu-hai.. Growth response of two coexisting species to climate change in broadleaved Korean pine forests in Changbai Mountain, northeastern China.[J]. Journal of Beijing Forestry University, 2013, 35(3): 24-31.
[9]	XU Jin-mei, BAO Fu-cheng, Lv Jian-xiong, HUANG Rong-feng, ZHAO You-ke, Evans Robert. Climate response of radial growth of Picea crassifolia in Qilian Mountains of northwestern China.[J]. Journal of Beijing Forestry University, 2012, 34(2): 1-6.
[10]	ZHANG Bao-lei, ZHOU Wan-cun, ZHOU Qi-gang, FENG Chao-yang. Forestland changes and climate response in the Three Gorges Reservoir Area based on RS and GIS[J]. Journal of Beijing Forestry University, 2006, 28(4): 62-66.

Cited By

Cited by

Periodical cited type(8)

1.	林立，何月秋，王豪，陆云峰，王建军，黄华宏. 代谢组与转录组联合解析赤皮青冈叶片黄化变异机制. 广西植物. 2024(07): 1319-1336 .
2.	李可悦，王丹丹，刘江涛，申琼，盖少杰，武峻新. 西葫芦嫩瓜皮叶绿素合成代谢与其皮色形成的关联性研究. 植物遗传资源学报. 2024(08): 1336-1346 .
3.	靳程，曹孟岩，杨衡荣，项瑶，杨建峰，时波，黄颂谊，辛国荣. 施肥和修剪对‘兰引Ⅲ号’草坪冬季质量及土壤特性的影响. 草地学报. 2024(09): 3006-3016 .
4.	邓皓予，吴一超，符腾，杨在君，乌日娜. 甘氨酸喷施下Cd对川麦28生理生化过程的影响. 华北农学报. 2024(S1): 63-71 .
5.	刘冬杰，肖波，曹秀珑. 微生物菌剂对草坪草抗寒性的研究进展. 草学. 2023(01): 11-14 .
6.	何海鹏，南丽丽，马彪，夏静，姚宇恒，陈洁，汪堃. 红豆草种质苗期耐寒性筛选及评价. 中国草地学报. 2023(05): 41-49 .
7.	廖浩钦，谢文刚. 牧草应对低温胁迫机制研究进展. 中国草地学报. 2023(12): 99-111 .
8.	王明莹. 不同品种苜蓿对低温胁迫的生理响应及抗寒性评价. 呼伦贝尔学院学报. 2022(03): 84-88+128 .

Other cited types(9)

Get Citation

PDF

XML

Article views (70) PDF downloads (21) Cited by(17)

Turn off MathJax

Article Contents

Abstract

References

Multi-objective path planning based on improved RRT and GA: a case study of UAV forest patrol