Reverse Tracking Graph Based on Dynamic Path Planning

Devanta Abraham Tarigan, Muhammad Zarlis, Rahmat Widia Sembiring

Abstract


This paper gives substance to Dynamic Path Planning focusing on reverse tracking method. The development of this method are proposed and expected to reduce the algorithm scanning the whole graph repeatedly. In this paper, several approachment will be presented sequentially. First, analysis and modeling of the obstacle and environment, pre-path planning, Depth First Search for availability path planning, and improvement of the Dijkstra algorithm for the shortest path. There-in the proposed model is defined by adopting the reverse feature in the Depth First Search algorithm in the finding of the availability path on the graph.


Keywords


Reverse Tracking; Dijkstra Algorithm; Depth First Search Algorithm; pre path planning; availability path planning;

Full Text:

PDF

References


L. Liu et al., "Global Dynamic Path Planning Fusion Algorithm Combining Jump-A* Algorithm and Dynamic Window Approach", IEEE Access, vol. 9, 2021, pp. 19632-19638.

Z. Zhu, J. Xie and Z. Wang, "Global Dynamic Path Planning Based on Fusion of A* Algorithm and Dynamic Window Approach", Chinese Automation Congress (CAC), 2019, pp. 5572 – 5576.

Risald, A. Mirino and Suyoto, "Best routes selection using Dijkstra and Floyd-Warshall algorithm", 11th International Conference on Information & Communication Technology and System (ICTS), 2017, pp. 155 -158.

Qian, C., Qisong, Z. and Li, H., 2018. Improved artificial potential field method for dynamic target path planning in LBS. Chinese Control And Decision Conference (CCDC), 2018, pp.2710 -2714.

Z. Wang and X. Xiang, "Improved Astar Algorithm for Path Planning of Marine Robot", 2018 37th Chinese Control Conference (CCC), 2018, pp. 5410 – 5414.

C. Wu, D. Liaw and H. Lee, "A Method for Finding the Routes of Mazes", 2018 International Automatic Control Conference (CACS), 2018.

H. Shen and P. Li, "Unmanned Aerial Vehicle (UAV) Path Planning Based on Improved Pre-planning Artificial Potential Field Method", 2020 Chinese Control And Decision Conference (CCDC), 2020, pp. 2727 – 2732.

A. Hidayatullah, A. Jati and C. Setianingsih, "Realization of depth first search algorithm on line maze solver robot", 2017 International Conference on Control, Electronics, Renewable Energy and Communications (ICCREC), 2017, pp. 247 – 251

S. Eng, O. Penangsang, R. Wibowo, I. Suryawati and C. Chhlonh, "Distribution System Restoration Using Spanning Tree Based on Depth First Search Visual in GUI", 2019 5th International Conference on Science and Technology (ICST), 2019.

E. Žunić, A. Djedović and B. Žunić, "Software solution for optimal planning of sales persons work based on Depth-First Search and Breadth-First Search algorithms," 2016 39th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2016, pp. 1248-1253.

G. Qing, Z. Zheng and X. Yue, "Path-planning of automated guided vehicle based on improved Dijkstra algorithm," 2017 29th Chinese Control And Decision Conference (CCDC), 2017, pp. 7138-7143.

J. Ji, A. Khajepour, W. Melek and Y. Huang, "Path Planning and Tracking for Vehicle Collision Avoidance Based on Model Predictive Control With Multiconstraints", IEEE Transactions on Vehicular Technology, vol. 66, no. 2, pp. 952-964, 2017.




DOI: https://doi.org/10.30743/infotekjar.v6i1.4355

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 Devanta Abraham Tarigan, Muhammad Zarlis, Rahmat Widia Sembiring

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

InfoTekJar (Jurnal Nasional Informatika dan Teknologi Jaringan)

Program Studi Teknik Informatika - Universitas Islam Sumatera Utara
Website : http://jurnal.uisu.ac.id/index.php/infotekjar/index
Email : infotekjar@ft.uisu.ac.id

InfoTekJar : Jurnal Nasional Informatika dan Teknologi Jaringan) is licensed under a Creative Commons Attribution 4.0 International License