Cover
Vol. 17 No. 1 (2021)

Published: June 30, 2021

Pages: 107-115

Original Article

Hybrid RRT-A*: An Improved Path Planning Method for an Autonomous Mobile Robots

Suhaib Al-Ansarry 1 Salah Al-Darraji
1Department of Computer Science, College of Education for Pure Sciences, University of Basrah, Basrah, Iraq
History
  • Received: April 5, 2021
  • Revised: May 7, 2021
  • Accepted: May 8, 2021
  • Available Online: May 9, 2021
DOI

https://doi.org/10.37917/ijeee.17.1.13

Abstract

Although the Basic RRT algorithm is considered a traditional search method, it has been widely used in the field of robot path planning (manipulator and mobile robot), especially in the past decade. This algorithm has many features that give it superiority over other methods. On the other hand, the Basic RRT suffers from a bad convergence rate (it takes a long time until finding the goal point), especially in environments with cluttered obstacles, or whose targets are located in narrow passages. Many studies have discussed this problem in recent years. This paper introduces an improved method called (Hybrid RRT-A*) to overcome the shortcomings of the original RRT, specifically slow convergence and cost rate. The heuristic function of A-star algorithm is combined with RRT to decrease tree expansion and guide it towards the goal with less nodes and time. Various experiments have been conducted with different environment scenarios to compare the proposed method with the Basic RRT and A-star under the same conditions, which have shown remarkable performance. The time consumed to find the path of the worst one of these scenarios is about 4.9 seconds, whereas it is 18.3 and 34 for A-star and RRT, respectively.

Keywords

References

  1. Abdulwahab Kheerallah Yousif, Ali Fadhil Marhoon, Mofeed Turky Rashid, and Abdulmuttalib Turky Rashid. "Self-Organization of Multi-Robot System Based on External Stimuli." Iraqi Journal for Electrical & Electronic Engineering Vol. 15, No. 2, pp. 101-114, (2019). DOI: 10.37917/ijeee. 15.2.11
  2. Thrun, Sebastian, Wolfram Burgard, and Dieter Fox. "Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)." (2005).
  3. Alexis, Kostas, George Nikolakopoulos, Anthony Tzes, and Leonidas Dritsas. "Coordination of helicopter UAVs for aerial forest-fire surveillance." In Applications of intelligent control to engineering systems, pp. 169-193. Springer, Dordrecht, 2009.
  4. Doherty, Patrick, and Piotr Rudol. "A UAV search and rescue scenario with human body detection and geolocalization." In Australasian Joint Conference on Artificial Intelligence, pp. 1-13. Springer, Berlin, Heidelberg, 2007.
  5. Möls, Märt. Linear mixed models with equivalent predictors. Tartu University Press, 2004.
  6. Injarapu, Anantha Sai Hari Haran V., and Suresh Kumar Gawre. "A survey of autonomous mobile robot path planning approaches." In 2017 International conference on recent innovations in signal processing and embedded systems (RISE), pp. 624-628. IEEE, 2017.
  7. LaValle, Steven M. "Rapidly-exploring random trees: A new tool for path planning.", pp. 98-11 (1998).
  8. LaValle, Steven M., and James J. Kuffner Jr. "Randomized kinodynamic planning." The international journal of robotics research Vol. 20, No. 5, pp. 378-400 (2001).
  9. Karaman, Sertac, Matthew R. Walter, Alejandro Perez, Emilio Frazzoli, and Seth Teller. "Anytime motion planning using the RRT." In 2011 IEEE International Conference on Robotics and Automation, pp. 1478- 1483. IEEE, 2011.
  10. Atramentov, Anna, and Steven M. LaValle. "Efficient nearest neighbor searching for motion planning." In Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No. 02CH37292), Vol. 1, pp. 632-637. IEEE, 2002.
  11. Kuffner, James J., and Steven M. LaValle. "RRT- connect: An efficient approach to single-query path planning." In Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), Vol. 2, pp. 995-1001. IEEE, 2000.
  12. Cui, Shi-Gang, Hui Wang, and Li Yang. "A simulation study of A-star algorithm for robot path planning." In 16th international conference on mechatronics technology, pp. 506-510. 2012.
  13. Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum Al-Ansarry & Al-Darraji | 115 cost paths." IEEE transactions on Systems Science and Cybernetics Vol. 4, No. 2, pp. 100-107 (1968).
  14. Nilsson, Nils J. The quest for artificial intelligence. Cambridge University Press, 2009.
  15. Dijkstra, Edsger Wybe. "A note on two problems in connexion with graphs:(Numerische Mathematik, 1 (1959))", pp. 269-271 (1959).
  16. Karaman, Sertac, and Emilio Frazzoli. "Incremental sampling-based algorithms for optimal motion planning." Robotics Science and Systems Vol. 104, No. 2 (2010).
  17. Karaman, Sertac, and Emilio Frazzoli. "Sampling-based algorithms for optimal motion planning." The international journal of robotics research Vol. 30, No. 7, pp. 846-894 (2011).
  18. Jordan, Matthew, and Alejandro Perez. "Optimal bidirectional rapidly-exploring random trees." (2013).
  19. Islam, Fahad, Jauwairia Nasir, Usman Malik, Yasar Ayaz, and Osman Hasan. "Rrt∗-smart: Rapid convergence implementation of rrt∗ towards optimal solution." In 2012 IEEE international conference on mechatronics and automation, pp. 1651-1656. IEEE, 2012.
  20. Nasir, Jauwairia, Fahad Islam, Usman Malik, Yasar Ayaz, Osman Hasan, Mushtaq Khan, and Mannan Saeed Muhammad. "RRT*-SMART: A rapid convergence implementation of RRT." International Journal of Advanced Robotic Systems Vol. 10, No. 7, pp. 299 (2013).
  21. Dirik, Mahmut, and Fatih KOCAMAZ. "RRT-Dijkstra: An Improved Path Planning Algorithm for Mobile Robots," Journal of Soft Computing and Artificial Intelligence Vol. 1, No. 2, pp. 11-19 (2020).
  22. Ayawli, Ben Beklisi Kwame, Xue Mei, Moquan Shen, Albert Yaw Appiah, and Frimpong Kyeremeh. "Optimized RRT-A* Path Planning Method for Mobile Robots in Partially Known Environment." Information Technology and Control Vol. 48, No. 2, pp. 179-194 (2019).
  23. Zhang, Zhen, Defeng Wu, Jiadong Gu, and Fusheng Li. "A path-planning strategy for unmanned surface vehicles based on an adaptive hybrid dynamic stepsize and target attractive force-RRT algorithm." Journal of Marine Science and Engineering Vol. 7, No. 5, pp. 132 (2019).
  24. Zhang, Pengchao, Chao Xiong, Wenke Li, Xiaoxiong Du, and Chuan Zhao. "Path planning for mobile robot based on modified rapidly exploring random tree method and neural network." International Journal of Advanced Robotic Systems Vol. 15, No. 3 (2018).