Search for the best route on a GPS-based autonomous electric vehicle using the A-Star algorithm

• Autorzy: Suprapto Bhakti Yudho , Dwijayanti Suci , Iskandar Muhammad Naufal Ghiffari , Rendyansyah Rendyansyah , Dini Diah Rahmah , Wijaya Patrick Kusuma

Identyfikatory

DOI

10.15199/48.2024.08.57

Warianty tytułu

PL

Wyszukaj najlepszą trasę w autonomicznym pojeździe elektrycznym opartym na GPS, korzystając z algorytmu A-Star

• Języki publikacji: EN

Abstrakty

EN

Route search is critical for autonomous vehicles because the vehicle can decide what path to follow to a destination while driving. Route search can use different algorithms, but the algorithms in previous studies require a long computational time. Therefore, in this study, an autonomous electric vehicle uses the A* algorithm to perform mapping to find the best route with the fastest path to a given destination. The A* algorithm is a shortest route search algorithm that uses a heuristic function to obtain optimal results, and is the most effective algorithm for finding the shortest route using static routing. Based on the results of research conducted on two routes at the Palembang and Inderalaya campuses of Sriwijaya University, the A* algorithm can be used to perform mapping for the best route to a destination using input from the latitude and longitude positions provided by the Global Positioning System (GPS). The shortest route taken in the research results for the Palembang campus is an ABCFG route, while the shortest route on the Inderalaya campus is ABCDGHI. A comparison of the actual distance with the measurement of the distance obtained by the A* algorithm shows a small error of 5.9 m on the Inderalaya campus. These results indicate that the A* algorithm can be used for mapping by autonomous vehicles, enabling the vehicles to determine the best routes.

PL

Wyszukiwanie trasy ma kluczowe znaczenie w przypadku pojazdów autonomicznych, ponieważ pojazd może podczas jazdy decydować, jaką ścieżką podążać do celu. Wyszukiwanie tras może wykorzystywać różne algorytmy, ale algorytmy z poprzednich badań wymagają długiego czasu obliczeniowego. Dlatego w niniejszym badaniu autonomiczny pojazd elektryczny wykorzystuje algorytm A* do wykonania mapowania w celu znalezienia najlepszej trasy z najszybszą ścieżką do danego miejsca docelowego. Algorytm A* to algorytm wyszukiwania najkrótszej trasy, który wykorzystuje funkcję heurystyczną w celu uzyskania optymalnych wyników i jest najskuteczniejszym algorytmem wyszukiwania najkrótszej trasy przy użyciu routingu statycznego. W oparciu o wyniki badań przeprowadzonych na dwóch trasach w kampusach Palembang i Inderalaya Uniwersytetu Sriwijaya, algorytm A* może zostać wykorzystany do wykonania mapowania najlepszej trasy do miejsca docelowego przy użyciu danych wejściowych z pozycji szerokości i długości geograficznej dostarczonych przez Global Positioning Systemu (GPS). Najkrótsza trasa wybrana w wynikach badań dla kampusu Palembang to trasa ABCFG, natomiast najkrótsza trasa na terenie kampusu Inderalaya to ABCDGHI. Porównanie odległości rzeczywistej z pomiarem odległości uzyskanej za pomocą algorytmu A* wykazuje na terenie kampusu Inderalaya niewielki błąd wynoszący 5,9 m. Wyniki te wskazują, że algorytm A* może być wykorzystany do mapowania przez pojazdy autonomiczne, umożliwiając tym pojazdom wyznaczanie najlepszych tras.

Słowa kluczowe

EN

A-star algorithm; best route; route search; unstructured road

PL

algorytm A-star; najlepsza trasa; wyszukiwanie trasy; droga nieustrukturyzowana

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2024
• Tom: R. 100, nr 8
• Strony: 284--291
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Suprapto Bhakti Yudho

• Electrical Engineering, Jl Raya Palembang-Prabumulih KM 32, Inderalaya, Ogan Ilir, South of Sumatera, Indonesia

• https://orcid.org/0000-0002-3995-6347

autor

Dwijayanti Suci

• Electrical Engineering, Jl Raya Palembang-Prabumulih KM 32, Inderalaya, Ogan Ilir, South of Sumatera, Indonesia

• https://orcid.org/0000-0003-2060-6408

autor

Iskandar Muhammad Naufal Ghiffari

• Electrical Engineering, Jl Raya Palembang-Prabumulih KM 32, Inderalaya, Ogan Ilir, South of Sumatera, Indonesia

autor

Rendyansyah Rendyansyah

• Electrical Engineering, Jl Raya Palembang-Prabumulih KM 32, Inderalaya, Ogan Ilir, South of Sumatera, Indonesia

autor

Dini Diah Rahmah

• Electrical Engineering, Jl Raya Palembang-Prabumulih KM 32, Inderalaya, Ogan Ilir, South of Sumatera, Indonesia

autor

Wijaya Patrick Kusuma

• Electrical Engineering, Jl Raya Palembang-Prabumulih KM 32, Inderalaya, Ogan Ilir, South of Sumatera, Indonesia

Bibliografia

• [1] SAE J3016:JAN2014, “Taxonomy and Definitions for Terms Related to On-Road Motor Vehicle Automated Driving Systems,” Soc. Autom. Eng., 2014.
• [2] S. E. Shladover, “Connected and automated vehicle systems: Introduction and overview,” J. Intell. Transp. Syst. Technol. Planning, Oper., vol. 22, no. 3, pp. 190–200, 2018, doi: 10.1080/15472450.2017.1336053.
• [3] I. s. R. V. Tirumalapudi, Raviteja, “No Title,” J. Crit. Rev., vol. 7, no. 13, pp. 196–202, 2020, doi: 10.31838/jcr.07.13.33.
• [4] M. Martínez-Díaz and F. Soriguera, “Autonomous vehicles: Theoretical and practical challenges,” Transp. Res. Procedia, vol. 33, pp. 275–282, 2018, doi: 10.1016/j.trpro.2018.10.103.
• [5] M. Karova, I. Penev, and N. Kalcheva, “Comparative analysis of algorithms to search for the path in a maze,” 2016 IEEE Int. Black Sea Conf. Commun. Networking, BlackSeaCom 2016, pp. 0–3, 2017, doi: 10.1109/BlackSeaCom.2016.7901597.
• [6] W. Zhou and L. Wang, “The Energy-Efficient Dynamic Route Planning for Electric Vehicles,” J. Adv. Transp., vol. 2019, p. 2607402, 2019, doi: 10.1155/2019/2607402.
• [7] S. Erke, D. Bin, N. Yiming, Z. Qi, X. Liang, and Z. Dawei, “An improved A-Star based path planning algorithm for autonomous land vehicles,” Int. J. Adv. Robot. Syst., vol. 17, no. 5, pp. 1–13, 2020, doi: 10.1177/1729881420962263.
• [8] L. S. Liu et al., “Path Planning for Smart Car Based on Dijkstra Algorithm and Dynamic Window Approach,” Wirel. Commun. Mob. Comput., vol. 2021, 2021, doi: 10.1155/2021/8881684.
• [9] J. Cui and G. Nie, “Motion Route Planning and Obstacle Avoidance Method for Mobile Robot Based on Deep Learning,” J. Electr. Comput. Eng., vol. 2022, p. 5739765, 2022, doi: 10.1155/2022/5739765.
• [10] S. Nazari, M. R. Meybodi, M. A. SalehiGh, and S. Taghipour, “An advanced algorithm for finding shortest path in car navigation system,” in Proceedings - The 1st International Conference on Intelligent Networks and Intelligent Systems, ICINIS 2008, 2008, pp. 671–674, doi: 10.1109/ICINIS.2008.147.
• [11] D. Rachmawati and L. Gustin, “Analysis of Dijkstra’s Algorithm and A∗ Algorithm in Shortest Path Problem,” J. Phys. Conf. Ser., vol. 1566, no. 1, 2020, doi: 10.1088/1742- 6596/1566/1/012061.
• [12] J. Yu, J. Hou, and G. Chen, “Improved Safety-First A-Star Algorithm for Autonomous Vehicles,” pp. 2–6, 2020.
• [13] K. and S. D. B. Y. Suprapto, A. F. Aristz, E. Sean, “Smart manufacturing workplace safety with virtual training, AR and haptic technologies,” in Human Machine Collaboration and Interaction for Smart Manufacturing, London: The Institution of Engineering and Technology, 2022.
• [14] T. Zheng, Y. Xu, and D. Zheng, “AGV path planning based on improved A-star algorithm,” in 2019 IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC), 2019, pp. 1534– 1538.
• [15] G. Tang, C. Tang, C. Claramunt, X. Hu, and P. Zhou, “Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment,” IEEE Access, vol. 9, pp. 59196–59210, 2021, doi: 10.1109/ACCESS.2021.3070054.
• [16] R. Maddison and C. Ni Mhurchu, “Global positioning system: a new opportunity in physical activity measurement,” Int. J. Behav. Nutr. Phys. Act., vol. 6, no. 1, pp. 1–8, 2009.
• [17] F. Rovira-Más, “Vulnerability of GPS to provide vehicle states in real time,” IFAC Proc. Vol., vol. 46, no. 18, pp. 207–212, 2013.
• [18] D. González, J. Pérez, V. Milanés, and F. Nashashibi, “A Review of Motion Planning Techniques for Automated Vehicles,” IEEE Trans. Intell. Transp. Syst., vol. 17, no. 4, pp. 1135–1145, 2016, doi: 10.1109/TITS.2015.2498841.
• [19] Z. Boroujeni, D. Goehring, F. Ulbrich, D. Neumann, and R. Rojas, “Flexible unit A-star trajectory planning for autonomous vehicles on structured road maps,” 2017 IEEE Int. Conf. Veh. Electron. Safety, ICVES 2017, pp. 7–12, 2017, doi: 10.1109/ICVES.2017.7991893.
• [20] Q. Liu, L. Zhao, Z. Tan, and W. Chen, “Global path planning for autonomous vehicles in off-road environment via an A-star algorithm,” Int. J. Veh. Auton. Syst., vol. 13, no. 4, pp. 330–339, 2017, doi: 10.1504/IJVAS.2017.087148.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki i promocja sportu (2025).