RRT- Dijkstra: An Improved Path Planning Algorithm for Mobile Robots

Abstract

The path planning problem is one of the most researched topics in autonomous vehicles. During the last decade, sampling-based algorithms for path planning have acquired significant attention from the research community. Rapidly exploring Random Tree (RRT) is a sampling-based planning approach, which is a concern to researchers due to its asymptotic optimality. However, the use of samples close to obstacles in path planning and the path with sharp turns does not make it efficient for real-time path tracking applications. For the purposes of overcoming these limitations, this paper proposes a combination of RRT and Dijkstra algorithms. The RRT-Dijkstra guarantees a shorter path planning to the optimum and collision-free solution. The optimality is measured by various factors such as path length, execution time, and the total number of turns. The aim here is review and performance comparison of these planners based on metrics, i.e., path length, execution time, and the total number of turning points. The algorithms are tested in complex structured with obstacles environments. The experimental performance shows that RRT-Dijkstra requires less turning point and execution time in 2D environments. These are advantages of the proposed method. The proposed method is suitable for off-line path planning and path-following.

Keywords

• Optimal criteria
• Path planning
• RRT
• Dijkstra
• Sampling-based algorithms

References

1. F. Duchoň et al., “Path Planning with Modified a Star Algorithm for a Mobile Robot,” Procedia Eng., vol. 96, pp. 59–69, 2014, doi: 10.1016/j.proeng.2014.12.098.
2. E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol. 1, no. 1, pp. 269–271, Dec. 1959, doi: 10.1007/BF01386390.
3. S. A. Fadzli, S. I. Abdulkadir, M. Makhtar, and A. A. Jamal, “Robotic Indoor Path Planning using Dijkstra ’ s Algorithm with Multi-Layer Dictionaries,” pp. 1–4, 2015.
4. P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Trans. Syst. Sci. Cybern., vol. 4, no. 2, pp. 100–107, 1968, doi: 10.1109/TSSC.1968.300136.
5. J. J. Kuffner and S. M. La Valle, “RRT-connect: an efficient approach to single-query path planning,” in Proceedings - IEEE International Conference on Robotics and Automation, 2000, doi: 10.1109/robot.2000.844730.
6. J. Bruce and M. Veloso, “Real-time randomized path planning for robot navigation,” in IEEE/RSJ International Conference on Intelligent Robots and System, 2002, vol. 3, pp. 2383–2388, doi: 10.1109/IRDS.2002.1041624.
7. A. Bry and N. Roy, “Rapidly-exploring random belief trees for motion planning under uncertainty,” in Proceedings - IEEE International Conference on Robotics and Automation, 2011, doi: 10.1109/ICRA.2011.5980508.
8. T. Weerakoon, K. Ishii, and A. A. F. Nassiraei, “An Artificial Potential Field Based Mobile Robot Navigation Method To Prevent From Deadlock,” J. Artif. Intell. Soft Comput. Res., vol. 5, no. 3, pp. 189–203, Jul. 2015, doi: 10.1515/jaiscr-2015-0028.

9. E. Rimon and D. E. Koditschek, “Exact robot navigation using artificial potential functions,” IEEE Trans. Robot. Autom., vol. 8, no. 5, pp. 501–518, Oct. 1992, doi: 10.1109/70.163777.
10. H. Kaluder, M. Brezak, and I. Petrović, “A visibility graph based method for path planning in dynamic environments,” in MIPRO 2011 - 34th International Convention on Information and Communication Technology, Electronics and Microelectronics - Proceedings, 2011.
11. R. Wein, J. P. Van Den Berg, and D. Halperin, “The visibility-Voronoi complex and its applications,” in Computational Geometry: Theory and Applications, 2007, doi: 10.1016/j.comgeo.2005.11.007.
12. P. Yap, “Grid-based path-finding,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2002, doi: 10.1007/3-540-47922-8_4.
13. A. I. Panov, K. S. Yakovlev, and R. Suvorov, “Grid path planning with deep reinforcement learning: Preliminary results,” in Procedia Computer Science, 2018, doi: 10.1016/j.procs.2018.01.054.
14. E. Donmez, A. F. Kocamaz, and M. Dirik, “Bi-RRT path extraction and curve fitting smooth with visual based configuration space mapping,” in International Artificial Intelligence and Data Processing Symposium (IDAP), Sep. 2017, pp. 1–5, doi: 10.1109/IDAP.2017.8090214.
15. R. Sadeghian, S. Shahin, and M. T. Masouleh, “An experimental study on vision based controlling of a spherical rolling robot,” in Iranian Conference on Intelligent Systems and Signal Processing (ICSPIS), Dec. 2017, pp. 23–27, doi: 10.1109/ICSPIS.2017.8311583.
16. L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom., vol. 12, no. 4, pp. 566–580, 1996, doi: 10.1109/70.508439.
17. C. Lamini, S. Benhlima, and A. Elbekri, “Genetic Algorithm Based Approach for Autonomous Mobile Robot Path Planning,” Procedia Comput. Sci., vol. 127, pp. 180–189, 2018, doi: 10.1016/j.procs.2018.01.113.
18. Jianping Tu and S. X. Yang, “Genetic algorithm based path planning for a mobile robot,” in International Conference on Robotics and Automation (Cat. No.03CH37422), 2003, vol. 1, pp. 1221–1226, doi: 10.1109/ROBOT.2003.1241759.
19. L. Moreno, J. M. Armingol, S. Garrido, A. De La Escalera, and M. A. Salichs, “A genetic algorithm for mobile robot localization using ultrasonic sensors,” J. Intell. Robot. Syst. Theory Appl., 2002, doi: 10.1023/A:1015664517164.
20. J.-Y. Jhang, C.-J. Lin, C.-T. Lin, and K.-Y. Young, “Navigation Control of Mobile Robots Using an Interval Type-2 Fuzzy Controller Based on Dynamic-group Particle Swarm Optimization,” Int. J. Control. Autom. Syst., vol. 16, no. 5, pp. 2446–2457, Oct. 2018, doi: 10.1007/s12555-017-0156-5.
21. T. W. Liao, “A procedure for the generation of interval type-2 membership functions from data,” Appl. Soft Comput., vol. 52, pp. 925–936, Mar. 2017, doi: 10.1016/j.asoc.2016.09.034.
22. M. Dirik, “Development of vision-based mobile robot control and path planning algorithms in obstacled environments,” Inonu University, 2020.
23. M. Fu, J. Li, and Z. Deng, “A practical route planning algorithm for vehicle navigation system,” in Proceedings of the World Congress on Intelligent Control and Automation (WCICA), 2004, doi: 10.1109/wcica.2004.1343742.
24. M. Dirik and A. F. Kocamaz, “Global Vision Based Path Planning for AVGs Using A* Algorithm.” Journal of Soft Computing and Artificial Intelligence, 1, pp. 18–28, 2020.
25. X. Cao, X. Zou, C. Jia, M. Chen, and Z. Zeng, “RRT-based path planning for an intelligent litchi-picking manipulator,” Comput. Electron. Agric., vol. 156, pp. 105–118, Jan. 2019, doi: 10.1016/j.compag.2018.10.031.
26. S. M. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Iowa State Univ. Ames, IA 50011 USA, vol. 6, no. 2, p. 103, 1998.
27. N. Chao, Y. Liu, H. Xia, A. Ayodeji, and L. Bai, “Grid-based RRT∗ for minimum dose walking path-planning in complex radioactive environments,” Ann. Nucl. Energy, vol. 115, pp. 73–82, May 2018, doi: 10.1016/j.anucene.2018.01.007.
28. L. Jaillet, A. Yershova, S. M. La Valle, and T. Simeon, “Adaptive tuning of the sampling domain for dynamic-domain RRTs,” in IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005, pp. 2851–2856, doi: 10.1109/IROS.2005.1545607.
29. A. Viseras, D. Shutin, and L. Merino, “Robotic Active Information Gathering for Spatial Field Reconstruction with Rapidly-Exploring Random Trees and Online Learning of Gaussian Processes,” Jr. Sensors, vol. 19, no. 5, pp. 10–16, Feb. 2019, doi: 10.3390/s19051016.
30. G. Klančar, A. Zdešar, S. Blažič, and I. Škrjanc, Wheeled Mobile Robotics, From Fundamentals Towards Autonomous Systems. Butterworth-Heinemann, © 2017 Elsevier Inc., 2017.
31. F. Yaacoub, Y. Hamam, A. Abche, and C. Fares, “Convex Hull in Medical Simulations: A New Hybrid Approach,” in IECON 2006 - 32nd Annual Conference on IEEE Industrial Electronics, Nov. 2006, pp. 3308–3313, doi: 10.1109/IECON.2006.347668.