GAO-RRT*: A path planning algorithm for mobile robot with low path cost and fast convergence

Lijuan Zhu; Peng Duan; Leilei Meng; Xiaohui Yang; Lijuan Zhu; Peng Duan; Leilei Meng; Xiaohui Yang

doi:10.3934/math.2024587

AIMS Mathematics

2024, Volume 9, Issue 5: 12011-12042. doi: 10.3934/math.2024587

Previous Article Next Article

Research article Special Issues

GAO-RRT*: A path planning algorithm for mobile robot with low path cost and fast convergence

1.
School of Computer Science, Liaocheng University, Shandong Liaocheng, 252059, China
2.
Shandong Provincial Key Laboratory of Network Based Intelligent Computing, Shandong Jinan, 250022, China

Received: 28 January 2024 Revised: 04 March 2024 Accepted: 12 March 2024 Published: 27 March 2024
MSC : 68T40, 68W20

Path planning is an essential research topic in the navigation of mobile robots. Currently, rapidly-exploring random tree star (RRT*) and its variants are known for their probabilistic completeness and asymptotic optimality, making them effective in finding solutions for many path planning problems. However, slow convergence rate of the RRT* limits its practical efficiency. To address this problem, this paper proposed an enhanced RRT* algorithm by refining the extension process of the exploring tree. This enhancement aims to guide the tree approaching to obstacles (GAO) while exploring toward the target point. First, GAO-RRT* employed a dual-weighted sample strategy instead of random sample to guide search direction of the exploring tree. Second, a variable step size extension strategy was adopted to increase the efficiency of node generation, balancing searching time and path safety in regions with different obstacles densities. Third, growth status of new nodes was monitored in real-time, and a reverse growth strategy was proposed to guide the exploring tree to escape local optima. In addition, parent node creation procedure for new nodes was used to produce a better initial path. Finally, the proposed GAO-RRT* was compared with three state of the art algorithms on 16 different instances of four representative environments. Compared to RRT*, Quick-RRT* (Q-RRT*), and Fast-RRT* (F-RRT*), the results showed that (1) the average path cost of initial solutions obtained by GAO-RRT* decreased by 38.32%, 29.69%, and 20.44%, respectively; and (2) the average convergence time of solution obtained by GAO-RRT* to suboptimal (1.05*$ C_{best} $) was reduced by 71.22%, 69.69%, and 58.37%, respectively. Simulation results indicated that GAO-RRT* outperforms the compared algorithms in terms of path cost and convergence speed.
- mobile robots,
- path planning,
- GAO-RRT*,
- dual-weighted sample strategy,
- variable step size extension strategy,
- reverse growth strategy
Citation: Lijuan Zhu, Peng Duan, Leilei Meng, Xiaohui Yang. GAO-RRT*: A path planning algorithm for mobile robot with low path cost and fast convergence[J]. AIMS Mathematics, 2024, 9(5): 12011-12042. doi: 10.3934/math.2024587

Related Papers:

Abstract

Path planning is an essential research topic in the navigation of mobile robots. Currently, rapidly-exploring random tree star (RRT*) and its variants are known for their probabilistic completeness and asymptotic optimality, making them effective in finding solutions for many path planning problems. However, slow convergence rate of the RRT* limits its practical efficiency. To address this problem, this paper proposed an enhanced RRT* algorithm by refining the extension process of the exploring tree. This enhancement aims to guide the tree approaching to obstacles (GAO) while exploring toward the target point. First, GAO-RRT* employed a dual-weighted sample strategy instead of random sample to guide search direction of the exploring tree. Second, a variable step size extension strategy was adopted to increase the efficiency of node generation, balancing searching time and path safety in regions with different obstacles densities. Third, growth status of new nodes was monitored in real-time, and a reverse growth strategy was proposed to guide the exploring tree to escape local optima. In addition, parent node creation procedure for new nodes was used to produce a better initial path. Finally, the proposed GAO-RRT* was compared with three state of the art algorithms on 16 different instances of four representative environments. Compared to RRT*, Quick-RRT* (Q-RRT*), and Fast-RRT* (F-RRT*), the results showed that (1) the average path cost of initial solutions obtained by GAO-RRT* decreased by 38.32%, 29.69%, and 20.44%, respectively; and (2) the average convergence time of solution obtained by GAO-RRT* to suboptimal (1.05*$ C_{best} $) was reduced by 71.22%, 69.69%, and 58.37%, respectively. Simulation results indicated that GAO-RRT* outperforms the compared algorithms in terms of path cost and convergence speed.

References

[1]	L. Liu, X. Wang, X. Yang, H. Liu, J. Li, P. Wang, Path planning techniques for mobile robots: Review and prospect, Expert Syst. Appl., 227 (2023), 1–30. https://doi.org/10.1016/j.eswa.2023.120254 doi: 10.1016/j.eswa.2023.120254
[2]	Z. Zhou, L. Li, A. Fürsterling, H. J. Durocher, J. Mouridsen, X. Zhang, Learning-based object detection and localization for a mobile robot manipulator in SME production, Robot. Comput. Integr. Manuf., 73 (2022), 1–12. https://doi.org/10.1016/j.rcim.2021.102229 doi: 10.1016/j.rcim.2021.102229
[3]	M. Pantscharowitsch, B. Kromoser, Automated subtractive timber manufacturing-joinery machines versus industrial robots, J. Manuf. Sci. Eng., 145 (2023), 1–15. https://doi.org/10.1115/1.4056924 doi: 10.1115/1.4056924
[4]	K. Hu, Z. Chen, H. Kang, Y. Tang, 3D vision technologies for a self-developed structural external crack damage recognition robot, Autom. Constr., 159 (2024), 1–19. https://doi.org/10.1016/j.autcon.2023.105262 doi: 10.1016/j.autcon.2023.105262
[5]	J. Holthöwer, J. van Doorn, Robots do not judge: Service robots can alleviate embarrassment in service encounters, J. Acad. Mark. Sci., 51 (2023), 767–784. https://doi.org/10.1007/s11747-022-00862-x doi: 10.1007/s11747-022-00862-x
[6]	M. Zhang, G. Tian, Y. Zhang, P. Duan, Service skill improvement for home robots: Autonomous generation of action sequence based on reinforcement learning, Knowl. Based Syst., 212 (2021), 1–15. https://doi.org/10.1016/j.knosys.2020.106605 doi: 10.1016/j.knosys.2020.106605
[7]	J. Cheng, L. Zhang, Q. Chen, X. Hu, J. Cai, A review of visual SLAM methods for autonomous driving vehicles, Eng. Appl. Artif. Intell., 114 (2022), 1–17. https://doi.org/10.1016/j.engappai.2022.104992 doi: 10.1016/j.engappai.2022.104992
[8]	H. Kim, Y. Choi, Development of autonomous driving patrol robot for improving underground mine safety, Appl. Sci., 13 (2023), 1–19. http://doi.org/10.3390/app13063717 doi: 10.3390/app13063717
[9]	Z. Jiang, S. E. Salcudean, N. Navab, Robotic ultrasound imaging: State-of-the-art and future perspectives, Med. Image Anal., 89 (2023), 1–26. https://doi.org/10.1016/j.media.2023.102878 doi: 10.1016/j.media.2023.102878
[10]	B. Song, Z. Wang, L. Zou, An improved PSO algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve, Appl. Soft Comput., 100 (2021), 1–11. http://doi.org/10.1016/j.asoc.2020.106960 doi: 10.1016/j.asoc.2020.106960
[11]	O. Khatib, Real-time obstacle avoidance for manipulators and mobile robots, Int. J. Robot. Res., 5 (1986), 90–98. http://dx.doi.org/10.1177/027836498600500106 doi: 10.1177/027836498600500106
[12]	W. Deng, X. Zhang, Y. Zhou, Y. Liu, X. Zhou, H. Chen, et al., An enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems, Inf. Sci., 585 (2022), 441–453. https://doi.org/10.1016/j.ins.2021.11.052 doi: 10.1016/j.ins.2021.11.052
[13]	L. Wu, X. Huang, J. Cui, C. Liu, W. Xiao, Modified adaptive ant colony optimization algorithm and its application for solving path planning of mobile robot, Expert Syst. Appl., 215 (2023), 1–37. https://doi.org/10.1016/j.eswa.2022.119410 doi: 10.1016/j.eswa.2022.119410
[14]	C. Pozna, R. E. Precup, E. Horváth, E. M. Petriu, Hybrid particle filter-particle swarm optimization algorithm and application to fuzzy controlled servo systems, Inst. Electr. Electron. Eng. Trans. Fuzzy Syst., 30 (2022), 4286–4297. http://dx.doi.org/10.1109/TFUZZ.2022.3146986 doi: 10.1109/TFUZZ.2022.3146986
[15]	Z. Zhang, J. Jiang, J. Wu, X. Zhu, Efficient and optimal penetration path planning for stealth unmanned aerial vehicle using minimal radar cross-section tactics and modified A-Star algorithm, Int. Soc. Autom. Trans., 134 (2023), 42–57. https://doi.org/10.1016/j.isatra.2022.07.032 doi: 10.1016/j.isatra.2022.07.032
[16]	Y. Zhang, G. Tian, X. Shao, S. Liu, M. Zhang, P. Duan, Building metric-topological map to efficient object search for mobile robot, Inst. Electr. Electron. Eng. Trans. Ind. Electron., 69 (2022), 7076–7087. https://doi.org/10.1109/TIE.2021.3095812 doi: 10.1109/TIE.2021.3095812
[17]	S. M. LaValle, J. J. Kuffner Jr, Randomized kinodynamic planning, Int. J. Robot. Res., 20 (2001), 378–400. http://dx.doi.org/10.1177/02783640122067453 doi: 10.1177/02783640122067453
[18]	J. Rao, C. Xiang, J. Xi, J. Chen, J. Lei, W. Giernacki, et al., Path planning for dual UAVs cooperative suspension transport based on artificial potential field-A* algorithm, Knowl. Based Syst., 277 (2023), 1–20. https://doi.org/10.1016/j.knosys.2023.110797 doi: 10.1016/j.knosys.2023.110797
[19]	Y. Tang, S. Qi, L. Zhu, X. Zhuo, Y. Zhang, F. Meng, Obstacle avoidance motion in mobile robotics, J. Syst. Simul., 36 (2024), 1–26. http://dx.doi.org/10.16182/j.issn1004731x.joss.23-1297E doi: 10.16182/j.issn1004731x.joss.23-1297E
[20]	Y. Guo, X. Liu, Q. Jia, X. Liu, W. Zhang, HPO-RRT: A sampling-based algorithm for UAV real-time path planning in a dynamic environment, Complex Intell. Syst.*, 9 (2023), 7133–7153. https://doi.org/10.1007/s40747-023-01115-2 doi: 10.1007/s40747-023-01115-2
[21]	S. Karaman, E. Frazzoli, Sampling-based algorithms for optimal motion planning, Int. J. Robot. Res., 30 (2011), 846–894. http://dx.doi.org/10.1177/0278364911406761 doi: 10.1177/0278364911406761
[22]	W. Zhang, L. Shan, L. Chang, Y. Dai, SVF-RRT: A stream-based VF-RRT for USVs path planning considering ocean currents, Inst. Electr. Electron. Eng. Robot. Autom. Lett., 8 (2023), 2413–2420. http://dx.doi.org/10.1109/LRA.2023.3245409 doi: 10.1109/LRA.2023.3245409
[23]	J. Nasir, F. Islam, U. Malik, Y. Ayaz, O. Hasan, M. Khan, et al., RRT-SMART: A rapid convergence implementation of RRT, Int. J. Adv. Robot. Syst.*, 10 (2013), 1–12. http://dx.doi.org/10.5772/56718 doi: 10.5772/56718
[24]	J. Fan, X. Chen, Y. Wang, X. Chen, UAV trajectory planning in cluttered environments based on PF-RRT* algorithm with goal-biased strategy, Eng. Appl. Artif. Intell., 114 (2022), 1–12. http://dx.doi.org/10.1016/j.engappai.2022.105182 doi: 10.1016/j.engappai.2022.105182
[25]	J. D. Gammell, S. S. Srinivasa, T. D. Barfoot, Informed RRT: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, In: 2014 IEEE/RSJ international conference on intelligent robots and systems, Chicago, IL, USA, IEEE, 2014, 2997–3004.
[26]	A. H. Qureshi, Y. Ayaz, Potential functions based sampling heuristic for optimal path planning, Auton. Robot., 40 (2016), 1079–1093. http://dx.doi.org/10.1007/s10514-015-9518-0 doi: 10.1007/s10514-015-9518-0
[27]	J. Fan, X. Chen, X. Liang, UAV trajectory planning based on bi-directional APF-RRT* algorithm with goal-biased, Expert Syst. Appl., 213 (2023), 1–12. http://dx.doi.org/10.1016/j.eswa.2022.119137 doi: 10.1016/j.eswa.2022.119137
[28]	L. Ye, F. Wu, X. Zou, J. Li, Path planning for mobile robots in unstructured orchard environments: An improved kinematically constrained bi-directional RRT approach, Comput. Electron. Agric., 215 (2023), 1–17. http://doi.org/10.1016/j.compag.2023.108453 doi: 10.1016/j.compag.2023.108453
[29]	I. B. Jeong, S. J. Lee, J. H. Kim, Quick-RRT: Triangular inequality-based implementation of RRT with improved initial solution and convergence rate, Expert Syst. Appl., 123 (2019), 82–90. http://dx.doi.org/10.1016/j.eswa.2019.01.032 doi: 10.1016/j.eswa.2019.01.032
[30]	J. Ding, Y. Zhou, X. Huang, K. Song, S. Lu, An improved RRT* algorithm for robot path planning based on path expansion heuristic sampling, J. Comput. Sci., 67 (2023), 1–12. http://dx.doi.org/10.1016/j.jocs.2022.101937 doi: 10.1016/j.jocs.2022.101937
[31]	B. Liao, F. Wan, Y. Hua, R. Ma, S. Zhu, X. Qing, F-RRT: An improved path planning algorithm with improved initial solution and convergence rate, Expert Syst. Appl., 184* (2021), 1–12. http://dx.doi.org/10.1016/j.eswa.2021.115457 doi: 10.1016/j.eswa.2021.115457
[32]	J. Ou, S. H. Hong, P. Ziehl, Y. Wang, GPU-based global path planning using genetic algorithm with near corner initialization, J. Intell. Robot. Syst., 104 (2022), 1–17. http://doi.org/10.1007/s10846-022-01576-6 doi: 10.1007/s10846-022-01576-6
[33]	A. Hidalgo-Paniagua, M. A. Vega-Rodríguez, J. Ferruz, N. Pavón, Mosfla-mrpp: Multi-objective shuffled frog-leaping algorithm applied to mobile robot path planning, Eng. Appl. Artif. Intell., 44 (2015), 123–136. http://dx.doi.org/10.1016/j.engappai.2015.05.011 doi: 10.1016/j.engappai.2015.05.011
[34]	Z. Yu, P. Duan, L. Meng, Y. Han, F. Ye, Multi-objective path planning for mobile robot with an improved artificial bee colony algorithm, Math. Biosci. Eng., 20 (2023), 2501–2529. http://dx.doi.org/10.3934/mbe.2023117 doi: 10.3934/mbe.2023117
[35]	X. He, Q. K. Pan, L. Gao, J. S. Neufeld, J. N. D. Gupta, Historical information based iterated greedy algorithm for distributed flowshop group scheduling problem with sequence-dependent setup times, Omega, 123 (2024), 1–19. https://doi.org/10.1016/j.omega.2023.102997 doi: 10.1016/j.omega.2023.102997

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)