Analisis Kinerja Algoritma Path Planning Klasik dan Heuristik pada Robot Bergerak dalam Lingkungan Dinamis
DOI:
https://doi.org/10.46962/snte.25.081Keywords:
A*, ANOVA, Dijkstra, Genetic Algorithm, multi-robot pathfinding, simulasi dinamisAbstract
Penelitian ini membahas pengembangan dan evaluasi algoritma pathfinding untuk sistem multi-robot dalam lingkungan grid dinamis menggunakan Python dengan antarmuka Tkinter. Latar belakang penelitian berangkat dari kebutuhan efisiensi navigasi robot otonom dalam menghadapi kondisi lingkungan yang kompleks, khususnya pada area dengan rintangan statis maupun dinamis. Tiga algoritma utama dibandingkan dalam studi ini, yaitu A*, Dijkstra, dan Genetic Algorithm (GA), dengan fokus pada performa waktu pencarian jalur yang diukur dalam satuan ticks. Metode penelitian dilakukan melalui simulasi berbasis grid 100 x 100, di mana tiga robot bergerak secara simultan dalam kondisi adanya hambatan yang berubah posisi. Data hasil simulasi dianalisis menggunakan Analysis of Variance (ANOVA) untuk menguji perbedaan signifikan antar algoritma, serta divisualisasikan melalui grafik perbandingan. Hasil penelitian menunjukkan bahwa Genetic Algorithm memiliki performa terbaik dengan rata-rata 45,05 ticks dan standar deviasi 3,97, diikuti oleh A* dengan rata-rata 49,06 ticks dan standar deviasi 4,50. Sementara itu, Dijkstra menjadi algoritma dengan performa terendah (59,27 ticks, sampai dengan 5,59). Analisis ANOVA mengonfirmasi adanya perbedaan signifikan antar model. Temuan ini menegaskan bahwa algoritma berbasis optimasi evolusioner lebih adaptif dalam kondisi dinamis, sehingga dapat diimplementasikan pada sistem navigasi robot otonom di lingkungan nyata yang memerlukan fleksibilitas tinggi.
References
. S. M. LaValle, Planning Algorithms. Cambridge: Cambridge University Press, 2006.
. S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics. Cambridge, MA: MIT Press, 2005.
. P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.
. A. Nash, K. Daniel, S. Koenig, and A. Felner, “Theta*: Any-Angle Path Planning on Grids,” in Proceedings of the 22nd AAAI Conference on Artificial Intelligence, 2007, pp. 1177–1183.
. S. Koenig and M. Likhachev, “D* Lite,” in Proceedings of the 18th National Conference on Artificial Intelligence (AAAI), 2002, pp. 476–483.
. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA: Addison-Wesley, 1989.
. M. Likhachev, G. Gordon, and S. Thrun, “ARA*: Anytime A* with Provable Bounds on Sub-Optimality,” in Advances in Neural Information Processing Systems (NIPS), 2003, pp. 767–774.
. H. S. Purnomo and M. A. Ma’sum, “Path Planning of Mobile Robot using Genetic Algorithm in Dynamic Environment,” Procedia Computer Science, vol. 135, pp. 460–467, 2018.
. M. Dorigo, G. Theraulaz, and V. Trianni, “Reflections on the Future of Swarm Robotics,” Science Robotics, vol. 5, no. 49, eaas9435, 2020.
. M. Bennewitz, W. Burgard, and S. Thrun, "Optimizing schedules for prioritized path planning of multi-robot systems," IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 271–276, 2001.
. G. Sharon, R. Stern, A. Felner, and N. Sturtevant, "Conflict-based search for optimal multi-agent pathfinding," Artificial Intelligence, vol. 219, pp. 40–66, 2015.
. E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, pp. 269–271, 1959.
. P. E. Hart, N. J. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths," IEEE Trans. Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.
. D. Silver, "Cooperative pathfinding," AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), pp. 117–122, 2005.
. M. Wooldridge, An Introduction to MultiAgent Systems. Chichester: Wiley, 2002.
. H. Van Dyke Parunak, S. Brueckner, and J. Sauter, "Digital pheromones for coordination of unmanned vehicles," Workshop on Autonomy in Unmanned Vehicles, 2002.
. M. Dorigo and T. Stützle, Ant Colony Optimization. Cambridge: MIT Press, 2004.
. S. Koenig and M. Likhachev, "Fast replanning for navigation in unknown terrain," IEEE Trans. Robotics and Automation, vol. 21, no. 3, pp. 354–363, 2005.
. A. Stentz, "Optimal and efficient path planning for partially known environments," IEEE Int. Conf. Robotics and Automation (ICRA), pp. 3310–3317, 1994.
. Y. Zhu et al., "Target-driven visual navigation in indoor scenes using deep reinforcement learning," IEEE Int. Conf. Robotics and Automation (ICRA), pp. 3357–3364, 2017.
. R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed. Cambridge: MIT Press, 2018.
. M. Quigley et al., "ROS: An open-source Robot Operating System," ICRA Workshop on Open Source Software, 2009.
. J. Zelle, Python Programming: An Introduction to Computer Science, 3rd ed. Franklin, Beedle & Associates, 2016
. Zhou, N., Stentz, A., & Smith, T. "Cooperative A* for multi-robot pathfinding in static environments," Proc. of IEEE ICRA, 2012.
. Koenig, S., & Likhachev, M. "D* Lite," AAAI Conference on Artificial Intelligence, pp. 476–483, 2002.
. Silver, D. "Cooperative Pathfinding," Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE), 2005.
. Wagner, G., & Choset, H. "Subdimensional expansion for multirobot path planning," Artificial Intelligence, vol. 219, pp. 1–24, 2015.
. Li, Y., Chen, J., & Zhao, X. "Multi-Robot Path Planning in Dynamic Environments Using Reinforcement Learning," IEEE Access, vol. 8, pp. 185000–185010, 2020.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Seminar Nasional Teknik Elektro
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
