An Effective Way for Repositioning the Beacon Nodes of Fast RRT Results Utilizing Grey Wolf Optimization

Heru Suwoyo; Andi Adriansyah; Julpri Andika; Abu Ubaidah Shamsudin; Yingzhong Tian

doi:10.18196/jrc.v6i1.22062

Authors

Heru Suwoyo Universitas Mercu Buana https://orcid.org/0000-0002-8762-4996
Andi Adriansyah Universitas Mercu Buana
Julpri Andika Universitas Mercu Buana
Abu Ubaidah Shamsudin Universiti Tun Hussein Onn Malaysia
Yingzhong Tian Shanghai University

DOI:

https://doi.org/10.18196/jrc.v6i1.22062

Keywords:

Fast-RRT, Grey Wolf Optimization, Path Planning, Convergence Rate, Optimality

Abstract

Conceptually, Fast-RRT applies fast sampling and random steering which makes the initial path quickly obtained. Referring to the initial path, the optimality of the path is improved by applying path fusion and path optimization. Theoretically, path fusion will only be optimal if there is always a unique/different path to be fused with the previously obtained path. However, in the conditions of solving path planning problems in narrow corridors, the potential for obtaining a different path from the previous one is very small. So that fusion does not run properly, but checking the relationship between nodes to nodes still occurs. Instead of getting an optimal path in conditions like this, the computation will increase, the solution time will be long, and the resulting path will still be sub-optimal. As an effort to solve this problem, Grey Wolf Optimization (GWO) is involved through this study. While an initial path is found, the beacons are repositioned. From the path, the number of nodes is unpredictable, causing the decision variables in optimization to become large. For this reason, the GWO is chosen because it is independent of population representation and is not affected by the number of decision variables. This proposed method is claimed to be more effective in solving path planning problems in terms of convergence rate and optimality. Therefore, the proposed method is evaluated and compared with previous methods and gives the result that the average working speed of Fast-RRT is improved by 90.25% and the optimality average increased by 5.67%.

Author Biography

Heru Suwoyo, Universitas Mercu Buana

Heru Suwoyo is a lecturer at Department of Electrical Engineering, Universitas Mercu Buana, Indonesia. He revieced his Ph.D. from Department of Mechatronic Engineering, School of Mechatronic Engineering and Automation, Shanghai University, China. His research interest include Behavior Based Robotic, Path Planning and Path Tracking, Mobile Robot Navigation, Simultaneous Localization and Mapping, Fuzzy Logic Controller, Probability-Based Filtering Method such as Extended Kalman Filter and Smooth Variable Structure Filter, Adaptive-Filtering and Population-Based Metaheuristic Optimization such as Ant Colony Optimization, Genetic Algorithm and Particle Swarm Optimization

References

H. Suwoyo et al., “Maximum likelihood estimation-assisted ASVSF through state covariance-based 2D SLAM algorithm,” Telkomnika Telecommun. Comput. Electron. Control, vol. 19, no. 1, pp. 327–338, 2020, doi: 10.12928/TELKOMNIKA.V19I1.16223.

Y. Tian, H. Suwoyo, W. Wang, D. Mbemba, and L. Li, “An AEKF-SLAM Algorithm with Recursive Noise Statistic Based on MLE and EM,” J. Intell. Robot. Syst. Theory Appl., vol. 97, pp. 339-355, 2020, doi: 10.1007/s10846-019-01044-8.

Y. Tian, H. Suwoyo, W. Wang, and L. Li, “An ASVSF-SLAM Algorithm with Time-Varying Noise Statistics Based on MAP Creation and Weighted Exponent,” Math. Probl. Eng., vol. 2019, pp. 28–34, 2019, doi: 10.1155/2019/2765731.

T. Bailey and H. Durrant-whyte, “Simultaneous Localisation and Mapping ( SLAM ): Part II State of the Art,” Robotics and Automation Magazine, pp. 1–10, 2006.

W. Burgard, C. Stachniss, K. Arras, and M. Bennewitz, “Introduction to Mobile Robotics SLAM : Simultaneous Localization and Mapping What is SLAM ?,” University of Freiburg, 2012.

I. Karabegović and V. Doleček, Mobile Robotics. in Detecting and Mitigating Robotic Cyber Security Risks, 2017, doi: 10.4018/978-1-5225-2154-9.ch016.

R. Kuemmerle. State Estimation and Optimization for Mobile Robot Navigation. Doctoral dissertation, Verlag nicht ermittelbar, 2013.

I. Noreen, A. Khan, and Z. Habib, “A Comparison of RRT, RRT* and RRT*-Smart Path Planning Algorithms,” IJCSNS Int. J. Comput. Sci. Netw. Secur., vol. 16, no. 10, pp. 20–27, 2016.

J. Cong, J. Hu, Y. Wang, Z. He, L. Han, and M. Su, “FF-RRT*: a sampling-improved path planning algorithm for mobile robots against concave cavity obstacle,” Complex Intell. Syst., vol. 9, no. 6, pp. 7249–7267, Dec. 2023, doi: 10.1007/s40747-023-01111-6.

L. Zhu, P. Duan, L. Meng, and X. Yang, “GAO-RRT*: A path planning algorithm for mobile robot with low path cost and fast convergence,” AIMS Math., vol. 9, no. 5, pp. 12011–12042, 2024, doi: 10.3934/math.2024587.

N. Kumar and A. Kumar, “Multi-Point Path Planning Using Bidirectional Path Search In Static And Dynamic Environments,” Educ. Adm. Theory Pract., Apr. 2023, doi: 10.53555/kuey.v29i4.6468.

L. Liu, X. Wang, X. Yang, H. Liu, J. Li, and P. Wang, “Path planning techniques for mobile robots: Review and prospect,” Expert Syst. Appl., vol. 227, p. 120254, Oct. 2023, doi: 10.1016/j.eswa.2023.120254.

A. Orthey, C. Chamzas, and L. E. Kavraki, “Sampling-Based Motion Planning: A Comparative Review,” Annu. Rev. Control Robot. Auton. Syst., vol. 7, no. 1, pp. 285–310, Jul. 2024, doi: 10.1146/annurev-control-061623-094742.

G. Sotirchos and Z. Ajanovic, “Search-based versus Sampling-based Robot Motion Planning: A Comparative Study,” J arXiv preprint arXiv:2406.09623, 2024, doi: 10.48550/arXiv.2406.09623.

Z. M. Al-Zubaidi, S. Ay, and M. Al-Khafaji, “A Comparative Study of Various Path Planning Algorithms for Pick-and-Place Robots,” Research Square, pp. 1-27, 2023, doi: 10.21203/rs.3.rs-2808265/v1.

Z. Feng, L. Zhou, J. Qi, and S. Hong, “DBVS-APF-RRT*: A global path planning algorithm with ultra-high speed generation of initial paths and high optimal path quality,” Expert Syst. Appl., vol. 249, p. 123571, Sep. 2024, doi: 10.1016/j.eswa.2024.123571.

S. Ganesan and S. K. Natarajan, “A novel directional sampling-based path planning algorithm for ambient intelligence navigation scheme in autonomous mobile robots,” J. Ambient Intell. Smart Environ., vol. 15, no. 3, pp. 269–284, Sep. 2023, doi: 10.3233/AIS-220292.

X. Jiang, Z. Wang, and C. Dong, “A Path Planning Algorithm Based on Improved RRT Sampling Region,” Comput. Mater. Contin., vol. 80, no. 3, pp. 4303–4323, 2024, doi: 10.32604/cmc.2024.054640.

X. Wang, Y. Feng, J. Tang, Z. Dai, and W. Zhao, “A UAV path planning method based on the framework of multi-objective jellyfish search algorithm,” Sci. Rep., vol. 14, no. 1, p. 28058, Nov. 2024, doi: 10.1038/s41598-024-79323-0.

M. Faroni, N. Pedrocchi, and M. Beschi, “Adaptive hybrid local–global sampling for fast informed sampling-based optimal path planning,” Auton. Robots, vol. 48, no. 2–3, p. 6, May 2024, doi: 10.1007/s10514-024-10157-5.

Y. Shi, S. Huang, and M. Li, “An Improved Global and Local Fusion Path-Planning Algorithm for Mobile Robots,” Sensors, vol. 24, no. 24, p. 7950, Dec. 2024, doi: 10.3390/s24247950.

I. A. Hassan, I. A. Abed, and W. A. Al-Hussaibi, “Path Planning and Trajectory Tracking Control for Two-Wheel Mobile Robot,” J. Robot. Control JRC, vol. 5, no. 1, pp. 1–15, Dec. 2023, doi: 10.18196/jrc.v5i1.20489.

H. Suwoyo, A. Adriansyah, J. Andika, A. U. Shamsudin, and M. F. Zakaria, “An Integrated Rrt*Smart-a* Algorithm for Solving the Global Path Planning Problem in a Static Environment,” IIUM Eng. J., vol. 24, no. 1, pp. 269–284, 2023, doi: 10.31436/iiumej.v24i1.2529.

S. Al-Ansarry and S. Al-Darraji, “Hybrid RRT-A*: An Improved Path Planning Method for an Autonomous Mobile Robots,” Iraqi J. Electr. Electron. Eng., vol. 17, no. 1, pp. 1–9, 2021, doi: 10.37917/ijeee.17.1.13.

W. Xin, L. Wanlin, F. Chao, and H. Likai, “Path Planning Research Based on An Improved A* Algorithmfor Mobile Robot,” IOP Conf. Ser. Mater. Sci. Eng., vol. 569, no. 5, p. 052044, Jul. 2019, doi: 10.1088/1757-899X/569/5/052044.

D. Fan and P. Shi, “Improvement of Dijkstra’s algorithm and its application in route planning,” in 2010 Seventh International Conference on Fuzzy Systems and Knowledge Discovery, pp. 1901–1904, 2010, doi: 10.1109/FSKD.2010.5569452.

M. A. Javaid, “Understanding Dijkstra Algorithm,” SSRN Electron. J., 2013, doi: 10.2139/ssrn.2340905.

M. A. Khan, “A Comprehensive Study of Dijkstra’s Algorithm,” SSRN Electron. J., 2023, doi: 10.2139/ssrn.4559304.

A. Tilanterä, J. Sorva, O. Seppälä, and A. Korhonen, “Students Struggle with Concepts in Dijkstra’s Algorithm,” in Proceedings of the 2024 ACM Conference on International Computing Education Research - Volume 1, pp. 154–165, 2024, doi: 10.1145/3632620.3671096.

D. Rachmawati and L. Gustin, “Analysis of Dijkstra’s Algorithm and A∗ Algorithm in Shortest Path Problem,” J. Phys. Conf. Ser., vol. 1566, no. 1, 2020, doi: 10.1088/1742-6596/1566/1/012061.

A. Rk, P. Reddy, and M. Yamuna, “Research On The Optimization Of Dijkstra’s Algorithm And Its Applications,” International Journal of Science, Technology & Management, vol. 4, no. 1, pp. 304-309, 2015.

R. Mashayekhi, M. Y. I. Idris, M. H. Anisi, and I. Ahmedy, “Hybrid RRT: A semi-dual-tree RRT-based motion planner,” IEEE Access, vol. 8, pp. 18658–18668, 2020, doi: 10.1109/ACCESS.2020.2968471.

H. Suwoyo, A. Burhanudin, Y. Tian, and J. Andika, “Problem solving path planning and path tracking in a 3 DOF hexapod robot using the RRT* algorithm with path optimization and Pose-to-Pose,” Sinergi Indones., vol. 28, no. 2, pp. 265–276, 2024, doi: 10.22441/sinergi.2024.2.007.

S. Klemm et al., “RRT*-Connect: Faster, asymptotically optimal motion planning,” in 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 1670–1677, 2015, doi: 10.1109/ROBIO.2015.7419012.

I. B. Jeong, S. J. Lee, and J. H. Kim, “RRT*-Quick: A motion planning algorithm with faster convergence rate,” Adv. Intell. Syst. Comput., vol. 345, pp. 67–76, 2015, doi: 10.1007/978-3-319-16841-8_7.

I. Noreen, A. Khan, K. Asghar, and Z. Habib, “A path-planning performance comparison of RRT*-AB with MEA* in a 2-Dimensional Environment,” Symmetry, vol. 11, no. 7, 2019, doi: 10.3390/sym11070945.

B. Liao, F. Wan, Y. Hua, R. Ma, S. Zhu, and X. Qing, “F-RRT*: An improved path planning algorithm with improved initial solution and convergence rate,” Expert Syst. Appl., vol. 184, pp. 115457–115457, 2021, doi: 10.1016/j.eswa.2021.115457.

A. Perez, S. Karaman, A. Shkolnik, E. Frazzoli, S. Teller, and M. R. Walter, “Asymptotically-optimal path planning for manipulation using incremental sampling-based algorithms,” IEEE Int. Conf. Intell. Robots Syst., pp. 4307–4313, 2011, doi: 10.1109/IROS.2011.6048640.

A. H. Qureshi and Y. Ayaz, “Potential functions based sampling heuristic for optimal path planning,” Auton. Robots, vol. 40, no. 6, pp. 1079–1093, 2016, doi: 10.1007/s10514-015-9518-0.

J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, "Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic," 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2997-3004, 2014, doi: 10.1109/IROS.2014.6942976.

J. Chen, Y. Zhao, and X. Xu, “Improved RRT-Connect Based Path Planning Algorithm for Mobile Robots,” IEEE Access, vol. 9, pp. 145988–145999, 2021, doi: 10.1109/ACCESS.2021.3123622.

X. Li and Y. Tong, “Path Planning of a Mobile Robot Based on the Improved RRT Algorithm,” Appl. Sci., vol. 14, no. 1, p. 25, Dec. 2023, doi: 10.3390/app14010025.

E. H. Bes. Path Planning with Homotopic Constraints for Autonomous Underwater Vehicles. Doctoral dissertation, Universitat de Girona, 2012.

L. G. D. O. Veras, F. L. L. Medeiros, and L. N. F. Guimaraes, “Systematic Literature Review of Sampling Process in Rapidly-Exploring Random Trees,” IEEE Access, vol. 7, pp. 50933–50953, 2019, doi: 10.1109/ACCESS.2019.2908100.

W. Burzyński and W. Stecz, “Trajectory planning with multiplatform spacetime RRT*,” Appl. Intell., vol. 54, no. 19, pp. 9524–9541, Oct. 2024, doi: 10.1007/s10489-024-05650-4.

A. Almalaq, K. Alqunun, R. Abbassi, Z. M. Ali, M. M. Refaat, and S. H. E. Abdel Aleem, “Integrated transmission expansion planning incorporating fault current limiting devices and thyristor-controlled series compensation using meta-heuristic optimization techniques,” Sci. Rep., vol. 14, no. 1, p. 13046, Jun. 2024, doi: 10.1038/s41598-024-63331-1.

O. Maruyama and A. Chihara, “NWE: Node-weighted expansion for protein complex prediction using random walk distances,” Proteome Sci., vol. 9, 2011, doi: 10.1186/1477-5956-9-S1-S14.

A. Felner et al., “Partial-Expansion A* with Selective Node Generation,” Proc. AAAI Conf. Artif. Intell., vol. 26, no. 1, pp. 471–477, Sep. 2021, doi: 10.1609/aaai.v26i1.8137.

J. Qi, Q. Yuan, C. Wang, X. Du, F. Du, and A. Ren, “Path planning and collision avoidance based on the RRT*FN framework for a robotic manipulator in various scenarios,” Complex Intell. Syst., vol. 9, no. 6, pp. 7475–7494, Dec. 2023, doi: 10.1007/s40747-023-01131-2.

H. Qin, S. Shao, T. Wang, X. Yu, Y. Jiang, and Z. Cao, “Review of Autonomous Path Planning Algorithms for Mobile Robots,” Drones, vol. 7, no. 3, p. 211, Mar. 2023, doi: 10.3390/drones7030211.

C. Li, C. Wang, J. Wang, Y. Shen, and M. Q. H. Meng, “Sliding-window informed RRT∗: A method for speeding up the optimization and path smoothing,” 2021 IEEE Int. Conf. Real-Time Comput. Robot. RCAR 2021, pp. 141–146, 2021, doi: 10.1109/RCAR52367.2021.9517672.

D. Wu, L. Wei, G. Wang, L. Tian, and G. Dai, “APF-IRRT*: An Improved Informed Rapidly-Exploring Random Trees-Star Algorithm by Introducing Artificial Potential Field Method for Mobile Robot Path Planning,” Appl. Sci. Switz., vol. 12, no. 21, 2022, doi: 10.3390/app122110905.

Q. Zhou and G. Liu, “UAV Path Planning Based on the Combination of A-star Algorithm and RRT-star Algorithm,” in 2022 IEEE International Conference on Unmanned Systems (ICUS), pp. 146–151, 2022, doi: 10.1109/ICUS55513.2022.9986703.

F. Islam, J. Nasir, U. Malik, Y. Ayaz, and O. Hasan, “RRT*-Smart: Rapid convergence implementation of RRT* towards optimal solution,” 2012 IEEE Int. Conf. Mechatron. Autom. ICMA 2012, pp. 1651–1656, 2012, doi: 10.1109/ICMA.2012.6284384.

Z. Wu, Z. Meng, W. Zhao, and Z. Wu, “Fast-RRT: A RRT-based optimal path finding method,” Appl. Sci. Switz., vol. 11, no. 24, 2021, doi: 10.3390/app112411777.

Q. Gu, X. Li, S. Jiang, and H. Mora, “Hybrid Genetic Grey Wolf Algorithm for Large-Scale Global Optimization,” Complexity, vol. 2019, 2019, doi: 10.1155/2019/2653512.

J. Liu, X. Wei, and H. Huang, “An Improved Grey Wolf Optimization Algorithm and its Application in Path Planning,” IEEE Access, vol. 9, pp. 121944–121956, 2021, doi: 10.1109/ACCESS.2021.3108973.

N. Mittal, U. Singh, and B. S. Sohi, “Modified Grey Wolf Optimizer for Global Engineering Optimization,” Appl. Comput. Intell. Soft Comput., vol. 2016, 2016, doi: 10.1155/2016/7950348.

J. Zhao and Z. M. Gao, “An improved grey wolf optimization algorithm with multiple tunnels for updating,” J. Phys. Conf. Ser., vol. 1678, no. 1, 2020, doi: 10.1088/1742-6596/1678/1/012096.

J. A. Abdor-Sierra, E. A. Merchán-Cruz, F. A. Sánchez-Garfias, R. G. Rodríguez-Cañizo, E. A. Portilla-Flores, and V. Vázquez-Castillo, “Particle swarm optimization for inverse kinematics solution and trajectory planning of 7-dof and 8-dof robot manipulators based on unit quaternion representation,” J. Appl. Eng. Sci., vol. 19, no. 3, pp. 592–599, 2021, doi: 10.5937/jaes0-30557.

S. Dereli and R. Köker, “IW-PSO approach to the inverse kinematics problem solution of a 7-DOF serial robot manipulator,” Sigma J Eng Nat Sci, vol. 36, no. 1, pp. 77–85, 2018.

R. Havangi, “Mobile robot localization based on PSO estimator,” Asian J. Control, vol. 21, no. 4, pp. 2167–2178, 2019, doi: 10.1002/asjc.2004.

B. Song, Z. Wang, and L. Zou, “An improved PSO algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve,” Appl. Soft Comput., vol. 100, p. 106960, Mar. 2021, doi: 10.1016/j.asoc.2020.106960.

J. Xin, Z. Li, Y. Zhang, and N. Li, "Efficient real-time path planning with self-evolving particle swarm optimization in dynamic scenarios," Unmanned Systems, vol. 12, no. 2, pp. 215-226, 2024.

H. T. Najm, N. S. Ahmad, and A. S. Al-Araji, “Enhanced path planning algorithm via hybrid WOA-PSO for differential wheeled mobile robots,” Syst. Sci. Control Eng., vol. 12, no. 1, p. 2334301, Dec. 2024, doi: 10.1080/21642583.2024.2334301.

A. J. Mohammed, K. I. Ghathwan, and Y. Yusof, “Optimal Robot Path Planning using Enhanced Particle Swarm Optimization algorithm,” Iraqi J. Sci., pp. 178–184, Jan. 2020, doi: 10.24996/ijs.2020.61.1.20.

L. Zheng, W. Yu, G. Li, G. Qin, and Y. Luo, “Particle Swarm Algorithm Path-Planning Method for Mobile Robots Based on Artificial Potential Fields,” Sensors, vol. 23, no. 13, p. 6082, Jul. 2023, doi: 10.3390/s23136082.

I. D. Fahmizal, M. Arrofiq, H. Maghfiroh, H. P. Santoso, P. Anugrah, and A. Molla, "Path Planning for Mobile Robots on Dynamic Environmental Obstacles Using PSO Optimization," Jurnal Ilmiah Teknik Elektro Komputer dan Informatika (JITEKI), vol. 10, no. 1, pp. 166-172, 2024.

T. Duckett, “A genetic algorithm for simultaneous localization and mapping,” Proc. - IEEE Int. Conf. Robot. Autom., vol. 1, pp. 434–439, 2003.

J. Ni, K. Wang, H. Huang, L. Wu, and C. Luo, “Robot path planning based on an improved genetic algorithm with variable length chromosome,” 2016 12th Int. Conf. Nat. Comput. Fuzzy Syst. Knowl. Discov. ICNC-FSKD 2016, pp. 145–149, 2016, doi: 10.1109/FSKD.2016.7603165.

S. T. Lian, K. Marzuki, and Y. Rubiyah, “Tuning of a neuro-fuzzy controller by genetic algorithms with an application to a coupled-tank liquid-level control system,” Eng. Appl. Artif. Intell., vol. 11, no. 4, pp. 517–529, 1998, doi: 10.1016/s0952-1976(98)00012-8.

Y. Li, J. Zhao, Z. Chen, G. Xiong, and S. Liu, “A Robot Path Planning Method Based on Improved Genetic Algorithm and Improved Dynamic Window Approach,” Sustainability, vol. 15, no. 5, p. 4656, Mar. 2023, doi: 10.3390/su15054656.

J. Wang, “Intelligent Path Planning of Mobile Robot Based on Genetic Algorithm,” J. Phys. Conf. Ser., vol. 2547, no. 1, p. 012001, Jul. 2023, doi: 10.1088/1742-6596/2547/1/012001.

W. Rahmaniar and A. E. Rakhmania, “Mobile Robot Path Planning in a Trajectory with Multiple Obstacles Using Genetic Algorithms,” J. Robot. Control JRC, vol. 3, no. 1, pp. 1–7, Jun. 2021, doi: 10.18196/jrc.v3i1.11024.

F. Liu, S. Liang, and D. X. Xian, “Optimal Path Planning for Mobile Robot Using Tailored Genetic Algorithm,” TELKOMNIKA Indones. J. Electr. Eng., vol. 12, no. 1, pp. 1–9, Jan. 2014, doi: 10.11591/telkomnika.v12i1.3127.

J. Liu, Z. Chen, Y. Zhang, and W. Li, “Path Planning of Mobile Robots based on Improved Genetic Algorithm,” in Proceedings of the 2020 2nd International Conference on Robotics, Intelligent Control and Artificial Intelligence, pp. 49–53, 2020, doi: 10.1145/3438872.3439054.

M. S. Abed, O. F. Lutfy, and Q. F. Al-Doori, “Adaptive weight grey wolf algorithm application on path planning in unknown environments,” Indones. J. Electr. Eng. Comput. Sci., vol. 27, no. 3, p. 1375, Sep. 2022, doi: 10.11591/ijeecs.v27.i3.pp1375-1387.

L. Liu, L. Li, H. Nian, Y. Lu, H. Zhao, and Y. Chen, “Enhanced Grey Wolf Optimization Algorithm for Mobile Robot Path Planning,” Electronics, vol. 12, no. 19, p. 4026, Sep. 2023, doi: 10.3390/electronics12194026.

R. Kumar, L. Singh, and R. Tiwari, “Path planning for the autonomous robots using modified grey wolf optimization approach,” J. Intell. Fuzzy Syst., vol. 40, no. 5, pp. 9453–9470, Apr. 2021, doi: 10.3233/JIFS-201926.

B. Tu, F. Wang, X. Han, and X. Fu, “Q-learning Guided Grey Wolf Optimizer for UAV 3D Path Planning,” Int. J. Adv. Comput. Sci. Appl., vol. 15, no. 7, 2024, doi: 10.14569/IJACSA.2024.0150747.