FF-RRT*: a sampling-improved path planning algorithm for mobile robots against concave cavity obstacle
Tóm tắt
The slow convergence rate and large cost of the initial solution limit the performance of rapidly exploring random tree star (RRT*). To address this issue, this paper proposes a modified RRT* algorithm (defined as FF-RRT*) that creates an optimal initial solution with a fast convergence rate. An improved hybrid sampling method is proposed to speed up the convergence rate by decreasing the iterations and overcoming the application limitation of the original hybrid sampling method towards concave cavity obstacle. The improved hybrid sampling method combines the goal bias sampling strategy and random sampling strategy, which requires a few searching time, resulting in a faster convergence rate than the existing method. Then, a parent node is created for the sampling node to optimize the path. Finally, the performance of FF-RRT* is validated in four simulation environments and compared with the other algorithms. The FF-RRT* shortens 32% of the convergence time in complex maze environment and 25% of the convergence time in simple maze environment compared to F-RRT*. And in a complex maze with a concave cavity obstacle, the average convergence time of Fast-RRT* in this environment is 134% more than the complex maze environment compared to 12% with F-RRT* and 34% with FF-RRT*. The simulation results show that FF-RRT* possesses superior performance compared to the other algorithms, and also fits with a much more complex environment.
Tài liệu tham khảo
Aggarwal S, Kumar N (2019) Path planning techniques for unmanned aerial vehicles: a review, solutions, and challenges. Comput Commun. https://doi.org/10.1016/j.comcom.2019.10.014
Fan J, Chen X, Liang X (2022) UAV trajectory planning based on bi-directional APF-RRT* algorithm with goal-biased. Expert Syst Appl. https://doi.org/10.1016/j.eswa.2022.119137
Jin Y, He Y, Jianke Du (2017) A novel path planning methodology for extrusion-based additive manufacturing of thin-walled parts. Int J Comput Integr Manuf. https://doi.org/10.1080/0951192X.2017.1307526
Jiang J, Ma Y (2020) Path planning strategies to optimize accuracy, quality, build time and material use in additive manufacturing: a review. Micromachines. https://doi.org/10.3390/mi11070633
Rezazadeh J, Moradi M, Ismail AS, Dutkiewicz E (2014) Superior path planning mechanism for mobile beacon-assisted localization in wireless sensor networks. IEEE Sens J. https://doi.org/10.1109/JSEN.2014.2322958
Yildiz D, Karagol S (2021) Path planning for mobile-anchor based wireless sensor networks localization: obstacle-presence schemes. Sensors. https://doi.org/10.3390/s21113697
Vargas ÁJO, Serrano JEC, Acuña LC, Martinez-Santos JC (2020) Path planning for non-playable characters in arcade video games using the wavefront algorithm. In: 2020 IEEE games, multimedia, animation and multiple realities conference (GMAX)
Ghanatian M, Yazdi MRH, Masouleh MT (2021) Experimental study on reducing the oscillations of a cable-suspended parallel robot for video capturing purposes using simulated annealing and path planning. In: 2021 7th International conference on signal processing and intelligent systems (ICSPIS), Tehran, Iran
Koul S, Horiuchi TK (2019) Waypoint path planning with synaptic-dependent spike latency. IEEE Trans Circuits Syst I Regul Pap 66(4):1544–1557
Shen LZ, Tao HF, Ni YZ, Wang Y, Vladimir S (2023) Improved YOLOv3 model with feature map cropping for multi-scale road object detection. Meas Sci Technol. https://doi.org/10.1088/1361-6501/acb075
Pan ZH, Zhang CX, Xia YQ, Xiong H, Shao XD (2022) An improved artificial potential field method for path planning and formation control of the multi-UAV systems. IEEE Trans Circuits Syst II Express Briefs 69(3):1129–1133
Zhu LF, Yao S, Li BY, Song AG, Jia YY, Jun M (2021) A geometric folding pattern for robot coverage path planning. In: 2021 IEEE international conference on robotics and automation, May 30–June 5
Mouad B, Lamine M, Abderazzak L (2021) FDA*: a focused single-query grid based path planning algorithm. J Autom Mob Robot Intell Syst 15(3):37–43
LaValle SM (1998) Rapidly-exploring random trees: a new tool for path planning
Justice D, Larkin F, Hyoshin P, Masashi M, Masahiro O, Su H (2022) A sampling-based path planning algorithm for improving observations in tropical cyclone. Earth Space Sci 9:2020EA001498. https://doi.org/10.1029/2020EA001498
He ZC, Dong L, Sun CY, Wang JW (2022) Asynchronous multithreading reinforcement-learning-based path planning and tracking for unmanned underwater vehicle. IEEE Trans Syst Man Cybern Syst 52(5):2757–2769
Shahnlia R, Mian MR, Chang SY, Peng LM (2022) A reinforcement learning-based path planning for collaborative UAVs. In: Proceedings of the 37th ACM/SIGAPP symposium on applied computing, pp 1938–1943. https://doi.org/10.1145/3477314.3507052
Karaman S, Frazzoli E (2011) Sampling-based algorithms for optimal motion planning. Int J Robot Res 30:846–894
Islam F, Nasir J, Malik U, Ayaz Y, Hasan O (2012) RRT*-smart: rapid convergence implementation of RRT* towards optimal solution. In: 2012 IEEE international conference on mechatronics and automation, IEEE, pp 1651–1656
Gammell JD, Srinivasa SS, Barfoot TD (2014) 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
Qureshi AH, Ayaz Y (2016) Potential functions based sampling heuristic for optimal path planning. Auton Robot 40:1079–1093
Li Y, Wei W, Gao Y, Wang D, Fan Z (2020) PQ-RRT*: an improved path planning algorithm for mobile robots. Expert Syst Appl 152:113425
Jeong I-B, Lee S-J, Kim J-H (2019) Quick-RRT*: triangular inequality-based implementation of RRT* with improved initial solution and convergence rate. Expert Syst Appl 123:82–90
Mishra UA, Métillon M, Caro S (2021) Kinematic stability based AFG-RRT* path planning for cable-driven parallel robots. In: The 2021 IEEE international conference on robotics and automation (ICRA 2021), May 2021, Xi’an, China. ffhal-03182298
Ge QY, Li AJ, Li SH, Du HP, Huang X, Niu CH (2021) Improved bidirectional RRT∗ path planning method for smart vehicle. Math Probl Eng 2021:1–14. https://doi.org/10.1155/2021/6669728
Wang J, Chi W, Li C, Wang C, Meng MQ-H (2020) Neural RRT*: learning-based optimal path planning. IEEE Trans Autom Sci Eng 17:1748–1758
Ganesan S, Natarajan S, Thondiyath A (2021) G-RRT*: goal-oriented sampling-based RRT* path planning Algorithm for mobile robot navigation with improved convergence rate. In: 5th international conference of the robotics society, 23, pp 1–6
Li JY, Wang KZ, Chen ZH, Wang JK (2022) An improved RRT* path planning algorithm in dynamic environment. Communications in computer and information science, vol 1713. Springer, Singapore. https://doi.org/10.1007/978-981-19-9195-0_25
Li Q, Wang J, Li H, Wang B, Feng C (2022) Fast-RRT*: an improved motion planner for mobile robot in two-dimensional space. IEEJ Trans Electr Electron Eng 17:200–208
Karaman S, Walter MR, Perez A, Frazzoli E, Teller S (2011) Anytime motion planning using the RRT*. In: 2011 IEEE international conference on robotics and automation, IEEE, pp 1478–1483
Qi J, Yang H, Sun HX (2021) MOD-RRT*: a sampling-based algorithm for robot path planning in dynamic environment. IEEE Trans Ind Electron 68(8):7244–7251
Kang J, Lim D, Choi Y, Jang W, Jung J (2021) Improved RRT-connect algorithm based on triangular inequality for robot path planning. Sensors 21(333):1–32
Kuffner JJ Jr., LaValle SM (2000) RRT-connect: an efficient approach to single-query path planning. In: Proceedings of the 2000 IEEE international conference on robotics & automation, pp 995–1001
Liao B, Wan F, Hua Y, Ma R, Zhu S, Qing X (2021) F-RRT*: an improved path planning algorithm with improved initial solution and convergence rate. Expert Syst Appl 184:115457
Wang XY, Yang YP, Wang D, Zhang ZJ (2021) Mission-oriented cooperative 3D path planning for modular solar-powered aircraft with energy optimization. Chin J Aeronaut 35:98–109. https://doi.org/10.1016/j.cja.2021.04.015
Aiello G, Valavanis KP, Rizzo A (2022) Fixed-wing UAV energy efficient 3D path planning in cluttered Environments. J Intell Robot Syst 105:60. https://doi.org/10.1007/s10846-022-01608-1
Ji W, An J, Cho MG, Kim C (2021) Integration of path planning, trajectory generation and trajectory tracking control for aircraft mission autonomy. Aerosp Scie Technol 118:107014. https://doi.org/10.1016/j.ast.2021.107014
Luo Y, Lu JK, Zhang Y, Zheng K, Qin Q, He L, Liu Y (2022) Near-ground delivery drones path planning design based on BOA-TSAR algorithm. Drones 6(12):393. https://doi.org/10.3390/drones6120393