Journals / Journal of Soft Computing and Artificial Intelligence / 2020 / Cilt: 1 - Sayı: 2

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

Pages
69–77
Publication Date
2020-12-29
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The proposed method is suitable for off-line path planning and path-following.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The path planning problem is one of the most researched topics in autonomous vehicles.
📊
Key Findings & Data: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.
💡
Conclusion & Impact:The proposed method is suitable for off-line path planning and path-following.
🔬Design:Review & Systematic Survey
📍Scope:Comprehensive Sample
⚙️Variables:Optimal criteria · Path planning · RRT

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.

🔖

Cite This Article

DİRİK, M., KOCAMAZ, F. (2020). RRT- Dijkstra: An Improved Path Planning Algorithm for Mobile Robots. Journal of Soft Computing and Artificial Intelligence, Cilt: 1 - Sayı: 2, 69–77. https://ajindex.com/articles/779582

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (3)

  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. 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. 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.
  2. 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. 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. 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. 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. 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. 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. 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.
  3. 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. 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. A. I. Panov, K. S. Yakovlev, and R. Suvorov, “Grid path planning with deep reinfor