Modifikasi algoritma a* untuk pencarian jalur tercepat dengan multi-skema prioritas, tie breaker dan force straight

Randi Farmana  Putra

doi:10.53842/juki.v5i1.173

Authors

Randi Farmana Putra Universitas Pertamina

DOI:

https://doi.org/10.53842/juki.v5i1.173

Keywords:

algortima A*, force straight, multi-skema prioritas, tie breaker, time periode

Abstract

In a robot that moves in 4 directions, the travel time is the accumulated time for moving from one node to another and the rotation time for changing directions. The A* algorithm can be used to determine the shortest distance to a point but cannot get the path with the fastest travel time because of the rotation factor. In this study using a modification of the A* Algorithm by adding the multi-priority scheme method, tie breaker and force straight. Modification of the A* Algorithm with multi-priority schemes produces 4 paths with different travel times then the fastest is selected, then the tie breaker plays the role of determining the parent node based on the actual value (g) and heuristics (h), then force straight when backtracking can minimize the number of turns. The modification of the A* algorithm can be used on a robot that moves in 4 directions to get the path with the fastest travel time

Downloads

Download data is not yet available.

References

Alhayali S., Ucan O., Bayat O., 2018. Genetic Algorithm for finding shortest paths Problem. ICEMIS '18: Proceedings of the Fourth International Conference on Engineering & MIS. Juni 2018. ISBN 978-1-4503-6392-1. Hal. 1-6. https://doi.org/10.1145/3234698.3234725

B. Liu and L. Li, "A Novel Tie-breaking Strategy for the A* Algorithm," Proceedings of the 2019 IEEE International Conference on Systems, Man and Cybernetics, pp. 2724-2729, 2019.

Batmetan, J. R. (2016). Algoritma Ant Colony Optimization (ACO) untuk Pemilihan Jalur Tercepat Evakuasi Bencana Gunung Lokon Sulawesi Utara. AITI, 13(1), 31-48.

Chaudhari, A. M., Apsangi, M. R., Kudale, A. B. 2017. Improved A-star algorithm with least turn for robotic rescue operations. Communications in Computer and Information Science. Vol. 776:614–627. https://doi.org/10.1007/978-981-10-6430-2_48

Dalem, I. B. G. W. A. (2018). Penerapan algoritma A*(Star) menggunakan graph untuk menghitung jarak terpendek. Jurnal RESISTOR (Rekayasa Sistem Komputer), 1(1), 41-47.

Erke, S., Bin, D., Yiming, N., Qi, Z., Liang, X., Dawei, Z. 2020. An improved A-Star based path planning algorithm for autonomous land vehicles. International Journal of Advanced Robotic Systems. Vol. 17(5): 1–13. https://doi.org/10.1177/1729881420962263

Garret D. F. 2014. Aircraft Route Optimization Using the a-Star Algorithm. Air Force Institute of Technology. Hal 11-13. https://apps.dtic.mil/sti/pdfs/ADA600125.pdf

J. Y. Choi, H. Kim, and B. C. Jung, "A* Algorithm with Force Straight: Enhancing Pathfinding Efficiency in Grid Maps," Proceedings of the 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2947-2952, 2019.

Mustaqov, M. A., & Megawaty, D. A. (2020). Penerapan Algoritma A-Star Pada Aplikasi Pencarian Lokasi Fotografi Di Bandar Lampung berbasis Android. Jurnal Teknoinfo, 14(1), 27-34.

R. Zuo, H. Zhang, and S. Li, "Enhancing A* algorithm with multi-criteria priorities for robot path planning," Robotics and Autonomous Systems, vol. 139, pp. 103720, 2021.

Tran, H. A. M., Ngo, H. Q. T., Nguyen, T. P., Nguyen, H. 2018. Implementation of vision-based autonomous mobile platform to control by A∗ algorithm. 2018 2nd International Conference on Recent Advances in Signal Processing, Telecommunications and Computing (SIGTELCOM). Januari 2018. Hal. 39–44. https://doi.org/10.1109/SIGTELCOM.2018.8325802

Wang, S. X. 2012. The improved Dijkstra’s shortest path algorithm and its application. Procedia Engineering. Vol. 29:1186–1190. https://doi.org/10.1016/j.proeng.2012.01.110

Wang, X., Liu, X., Wang, Y., & Liang, S. 2020. Research on Path Planning of Mobile Robot Based on Improved A* Algorithm. IE&EM 2019:153–161. https://doi.org/10.1007/978-981-15-4530-6_16

Y. Bjornsson and A. I. Maier, "Speeding Up Grid Pathfinding with Hierarchical Expansion, Multiple Searches, and Forced Paths," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 28, no. 1, pp. 526-532, 2014.

Y. Li, H. Li, and X. Zhang, "A fast A* algorithm for global path planning of mobile robot," Measurement, vol. 181, pp. 25-35, 2021.

Y. Tian, L. Lu, and W. Zhang, "A Fast and Adaptive A* Algorithm with Multiple Heuristics for Robot Path Planning," Applied Sciences, vol. 11, no. 7, pp. 3038, 2021.

Z. Yu, L. Cheng, and Y. Zhang, "An Efficient A* Algorithm for Robot Path Planning Based on Obstacle Distance Map," Journal of Intelligent & Robotic Systems, pp. 1-14, 2022.