A New Strategy to Improve the Performance of Informed RRT* Algorithm in Solving the Global Path Planning of Mobile Robot
DOI:
https://doi.org/10.37385/jaets.v7i1.6194Keywords:
Informed RRT*, Bias Technique, Constraint Sampling, Convergence Rate, OptimalityAbstract
Informed RRT* has been mentioned as a great method to find feasible and optimal solution of path planning. Technically, it uses the prolate hyper-spheroid and a centralized optimization strategy to gain the optimality of path. This optimization process is started when the initial feasible solution is found. Conventionally, the traditional procedure of RRT* is used to connecting starting point and goal point feasibly. Therefore, it is not suppressing if the optimization process begins later in large coverage of path planning problem. For this reason, a new strategy needs to propose with an objective to speed up the convergence rate by reducing the inefficiency of its blind sampling. Sequentially, it is conducted by integrating the bias technique and constraint sampling to replace the traditional sampling method. Next, the nearest node's ancestor is taken into consideration up until the first stage of choosing the parent is less expensive then RRT*. Regarding to these offers and the comparative results, the performance of the proposed method has shown better performance compared to its predecessor in terms of optimality, indicated by a decrease in finding the initial path by an average acceleration of 47.90% and a convergence rate indicated by an average path cost decrease value of 3.94%.
Downloads
References
Adriansyah, A., Suwoyo, H., Tian, Y., & Deng, C. (2019). IMPROVING THE WALL-FOLLOWING ROBOT PERFORMANCE USING PID-PSO CONTROLLER. Jurnal Teknologi (Sciences & Engineering), 81(3), 119–126. https://doi.org/10.11113/JT.V81.13098
Agrawal, S., & Shrivastava, V. (2017). Particle swarm optimization of BLDC motor with fuzzy logic controller for speed improvement. 8th International Conference on Computing, Communications and Networking Technologies, ICCCNT 2017. https://doi.org/10.1109/ICCCNT.2017.8204006
Al-Ansarry, S., & Al-Darraji, S. (2021). Hybrid RRT-A*: An Improved Path Planning Method for an Autonomous Mobile Robots. Iraqi Journal for Electrical and Electronic Engineering, 17(1), 1–9. https://doi.org/10.37917/ijeee.17.1.13
Bailey, T., Nieto, J., Guivant, J., Stevens, M., & Nebot, E. (2006). Consistency of the EKF-SLAM algorithm. IEEE International Conference on Intelligent Robots and Systems, 1, 3562–3568. https://doi.org/10.1109/IROS.2006.281644
Bastapure, A. A., Chiddarwar, S. S., & Goyal, A. (2023). A Comparative Study of A*, RRT, and RRT* Algorithm for Path Planning in 2D Warehouse Configuration Space. Lecture Notes in Electrical Engineering, 1066 LNEE, 95–107. https://doi.org/10.1007/978-981-99-4634-1_8
Bingul, Z., Ertunc, H. M., & Oysu, C. (2005). Applying Neural Network to Inverse Kinematic Problem for 6R Robot Manipulator with Offset Wrist. Adaptive and Natural Computing Algorithms, 112–115. https://doi.org/10.1007/3-211-27389-1_27
Bozorg-Haddad, O., Solgi, M., & Loáiciga, H. A. (2017). Meta-Heuristic and Evolutionary Algorithms for Engineering Optimization. In Meta-Heuristic and Evolutionary Algorithms for Engineering Optimization. https://doi.org/10.1002/9781119387053
Caceres, C., Rosario, J. M., & Amaya, D. (2017). Approach of Kinematic Control for a Nonholonomic Wheeled Robot using Artificial Neural Networks and Genetic Algorithms. 2017 International Work Conference on Bio-Inspired Intelligence: Intelligent Systems for Biodiversity Conservation, IWOBI 2017 - Proceedings. https://doi.org/10.1109/IWOBI.2017.7985533
Chen, C., Du, H., & Lin, S. (2017). Mobile robot wall-following control by improved artificial bee colony algorithm to design a compensatory fuzzy logic controller. ECTI-CON 2017 - 2017 14th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology, 856–859. https://doi.org/10.1109/ECTICon.2017.8096373
Chen, J., Zhao, Y., & Xu, X. (2021). Improved RRT-Connect Based Path Planning Algorithm for Mobile Robots. IEEE Access, 9, 145988–145999. https://doi.org/10.1109/ACCESS.2021.3123622
Chen, W., & Qin, H. (2011). Path planning of mobile robot based on hybrid cascaded genetic algorithm. Proceedings of the World Congress on Intelligent Control and Automation (WCICA), 501–504. https://doi.org/10.1109/WCICA.2011.5970564
Dain, R. A. (1998). Developing Mobile Robot Wall-Following Algorithms Using Genetic Programming. Applied Intelligence, 8(1), 33–41. https://doi.org/10.1023/A:1008216530547
El-Ghoul, S., Hussein, A. S., Wahab, M. S. A., Witkowski, U., & Ruckert, U. (2008). A Modified Multiple Depth First Search Algorithm for Grid Mapping Using Mini-Robots Khepera. Journal of Computing Science and Engineering, 2(4), 321–338. https://doi.org/10.5626/jcse.2008.2.4.321
Ginting, S. E. (Sakaria), & Sembiring, A. S. (Abdul). (2019). Comparison of Breadth First Search (BFS) and Depth-First Search (DFS) Methods on File Search in Structure Directory Windows. Login, 13(1), 26–31. https://doi.org/10.24224/LOGIN.V13I1.23
Ginting, S. E., & Sembiring, A. S. (2019). Jurnal Teknologi Komputer Comparison of Breadth First Search (BFS) and Depth-First Search (DFS) Methods on File Search in Structure Directory Windows. 13(1), 26–31.
Ibarra-Pérez, T., Ortiz-Rodríguez, J. M., Olivera-Domingo, F., Guerrero-Osuna, H. A., Gamboa-Rosales, H., & Martínez-Blanco, M. del R. (2022). A Novel Inverse Kinematic Solution of a Six-DOF Robot Using Neural Networks Based on the Taguchi Optimization Technique. Applied Sciences (Switzerland), 12(19). https://doi.org/10.3390/app12199512
Islam, F., Nasir, J., Malik, U., Ayaz, Y., & Hasan, O. (2012). RRT*-Smart: Rapid convergence implementation of RRT* towards optimal solution. 2012 IEEE International Conference on Mechatronics and Automation, ICMA 2012, 1651–1656. https://doi.org/10.1109/ICMA.2012.6284384
Jeong, I. B., Lee, S. J., & Kim, J. H. (2015). RRT*-Quick: A motion planning algorithm with faster convergence rate. Advances in Intelligent Systems and Computing, 345, 67–76. https://doi.org/10.1007/978-3-319-16841-8_7
Jiang, G., Luo, M., Bai, K., & Chen, S. (2017). A precise positioning method for a puncture robot based on a PSO-optimized BP neural network algorithm. Applied Sciences (Switzerland), 7(10). https://doi.org/10.3390/app7100969
Juang, C. F., Jhan, Y. H., Chen, Y. M., & Hsu, C. M. (2018). Evolutionary Wall-Following Hexapod Robot Using Advanced Multiobjective Continuous Ant Colony Optimized Fuzzy Controller. IEEE Transactions on Cognitive and Developmental Systems, 10(3), 585–594. https://doi.org/10.1109/TCDS.2017.2681181
Kuffner, J. J., & La Valle, S. M. (2000). RRT-connect: an efficient approach to single-query path planning. Proceedings - IEEE International Conference on Robotics and Automation, 2, 995–1001. https://doi.org/10.1109/ROBOT.2000.844730
Li, J., Liu, S., Zhang, B., & Zhao, X. (2014). RRT-A* motion planning algorithm for non-holonomic mobile robot. Proceedings of the SICE Annual Conference, 1833-1838. https://doi.org/10.1109/SICE.2014.6935304
Li, L., Li, A., Tian, Y., Wang, W., Chen, W., Fan, Y., & Xi, F. (2018). A Robust Visual SLAM System Based on RGB-D Camera Used in Various Indoor Scenes. 2018 IEEE International Conference on Robotics and Biomimetics (ROBIO), 1632–1637.
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 Transactions on Electrical and Electronic Engineering, 17(2), 200–208. https://doi.org/10.1002/tee.23502
Mashayekhi, R., Idris, M. Y. I., Anisi, M. H., & Ahmedy, I. (2020). Hybrid RRT: A semi-dual-tree RRT-based motion planner. IEEE Access, 8, 18658–18668. https://doi.org/10.1109/ACCESS.2020.2968471
https://doi.org/10.1109/ACCESS.2020.2968471
Mashayekhi, R., Idris, M. Y. I., Anisi, M. H., Ahmedy, I., & Ali, I. (2020). Informed RRT*-Connect: An Asymptotically Optimal Single-Query Path Planning Method. IEEE Access, 8, 19842–19852. https://doi.org/10.1109/ACCESS.2020.2969316
Min, H., Lin, Y., Wang, S., Wu, F., & Shen, X. (2015). Path planning of mobile robot by mixing experience with modified artificial potential field method. Advances in Mechanical Engineering, 7(11), 6–10. https://doi.org/10.1177/1687814015619276
Naderi, K., Rajamaki, J., & Hamalainen, P. (2015). RT-RRT*: A real-time path planning algorithm based on RRT*. Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games, MIG 2015, November, 113–118. https://doi.org/10.1145/2822013.2822036
Nasir, J., Islam, F., Malik, U., Ayaz, Y., Hasan, O., Khan, M., & Muhammad, M. S. (2013). RRT*-SMART: A Rapid Convergence Implementation of RRT*. International Journal of Advanced Robotic Systems, 10. https://doi.org/10.5772/56718
Ni, J., Wang, K., Huang, H., Wu, L., & Luo, C. (2016). Robot path planning based on an improved genetic algorithm with variable length chromosome. 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery, ICNC-FSKD 2016, 145–149. https://doi.org/10.1109/FSKD.2016.7603165
Noreen, I., Khan, A., & Habib, Z. (2016). A Comparison of RRT, RRT* and RRT*-Smart Path Planning Algorithms. IJCSNS International Journal of Computer Science and Network Security, 16(10), 20–27. http://cloud.politala.ac.id/politala/1. Jurusan/Teknik Informatika/19. e-journal/Jurnal Internasional TI/IJCSNS/2016 Vol. 16 No. 10/20161004_A Compar ison of RRT, RRT and RRT - Smart Path Planning Algorithms.pdf
Rachmawati, D., & Gustin, L. (2020). Analysis of Dijkstra’s Algorithm and A* Algorithm in Shortest Path Problem. Journal of Physics: Conference Series, 1566(1). https://doi.org/10.1088/1742-6596/1566/1/012061
Ran, D., Ma, J., Peng, F., & Li, H. (2021). SUMMARY OF RESEARCH ON PATH PLANNING BASED ON A* ALGORITHM. IET Conference Proceedings, 2020(2), 84–89. https://doi.org/10.1049/ICP.2021.1291
Sun, Z., Wang, J., & Meng, M. Q. H. (2022). Multi-Tree Guided Efficient Robot Motion Planning. Procedia Computer Science, 209, 31–39. https://doi.org/10.1016/J.PROCS.2022.10.096
Suwoyo, H., Adriansyah, A., Andika, J., Shamsudin, A. U., & Zakaria, M. F. (2023). an Integrated Rrt*Smart-a* Algorithm for Solving the Global Path Planning Problem in a Static Environment. IIUM Engineering Journal, 24(1), 269–284. https://doi.org/10.31436/iiumej.v24i1.2529
Suwoyo, H., Deng, C., Tian, Y., & Adriansyah, A. (2018). Improving a wall-following robot performance with a PID-genetic algorithm controller. International Conference on Electrical Engineering, Computer Science and Informatics (EECSI), 2018-Octob, 314–318. https://doi.org/10.1109/EECSI.2018.8752907
Suwoyo, H., Hajar, M. H. I., Indriyanti, P., & Febriandirza, A. (2024). The use of Fuzzy Logic Controller and Artificial Bee Colony for optimizing adaptive SVSF in robot localization algorithm. Sinergi (Indonesia), 28(2), 231–240. https://doi.org/10.22441/sinergi.2024.2.003
Tian, Y., Suwoyo, H., Wang, W., & Li, L. (2019). An ASVSF-SLAM Algorithm with Time-Varying Noise Statistics Based on MAP Creation and Weighted Exponent. Mathematical Problems in Engineering, 2019, 28–34. https://doi.org/10.1155/2019/2765731
Tian, Y., Suwoyo, H., Wang, W., Mbemba, D., & Li, L. (2019). An AEKF-SLAM Algorithm with Recursive Noise Statistic Based on MLE and EM. Journal of Intelligent and Robotic Systems: Theory and Applications. https://doi.org/10.1007/s10846-019-01044-8
Wang, H., Qi, X., Lou, S., Jing, J., He, H., & Liu, W. (2021). An efficient and robust improved a* Algorithm for path planning. Symmetry, 13(11). https://doi.org/10.3390/sym13112213
Wang, H., Yan, Y., & Wang, D. W. (2010). A GA based SLAM with range sensors only. 2010 11th International Conference on Control Automation Robotics & Vision, 1796–1802.
Wen, S., Chen, X., Ma, C., Lam, H.-K., & Hua, S. (2015). The Q-learning obstacle avoidance algorithm based on EKF-SLAM for NAO autonomous walking under unknown environments. Robotics and Autonomous Systems, 72, 29–36.
Wu, D., Wei, L., Wang, G., Tian, L., & Dai, G. (2022). APF-IRRT*: An Improved Informed Rapidly-Exploring Random Trees-Star Algorithm by Introducing Artificial Potential Field Method for Mobile Robot Path Planning. Applied Sciences (Switzerland), 12(21). https://doi.org/10.3390/app122110905
Wu, Z., Meng, Z., Zhao, W., & Wu, Z. (2021a). Fast-RRT: A RRT-Based Optimal Path Finding Method. Applied Sciences 2021, Vol. 11, Page 11777, 11(24), 11777. https://doi.org/10.3390/APP112411777
Wu, Z., Meng, Z., Zhao, W., & Wu, Z. (2021b). Fast-RRT: A RRT-based optimal path finding method. Applied Sciences (Switzerland), 11(24). https://doi.org/10.3390/app112411777
Xinying, X., Jun, X., & Keming, X. (2006). Path planning and obstacle-avoidance for soccer robot based on artificial potential field and genetic algorithm. Proceedings of the World Congress on Intelligent Control and Automation (WCICA), 1, 3494–3498. https://doi.org/10.1109/WCICA.2006.1713018
Yu, F., Sun, Q., Lv, C., Ben, Y., & Fu, Y. (2014). A SLAM algorithm based on adaptive cubature Kalman filter. Mathematical Problems in Engineering, 2014. https://doi.org/10.1155/2014/171958
Yusuf, L. I., & Musdholifah, A. (2024). A new hybrid parallel genetic algorithm for multi-destination path planning problem. Indonesian Journal of Electrical Engineering and Computer Science, 34(1), 584–591. https://doi.org/10.11591/ijeecs.v34.i1.pp584-591
Zhang, D., Xu, Y., & Yao, X. (2018). An Improved Path Planning Algorithm for Unmanned Aerial Vehicle Based on RRT-Connect. Chinese Control Conference, CCC, 2018-July, 4854–4858. https://doi.org/10.23919/ChiCC.2018.8483405
Zhou, Y., Zheng, L., & Li, Y. (2012). An improved genetic algorithm for mobile robotic path planning. Proceedings of the 2012 24th Chinese Control and Decision Conference, CCDC 2012, 3255–3260. https://doi.org/10.1109/CCDC.2012.6244515
CITEDNESS IN SCOPUS
CITEDNESS IN WOS
