Control Systems and Computers

https://doi.org/10.15407/csc.2024.04.019

Novikov O.A., Yanovsky V.V. Analysis of Search and Multi-Agent Algorithms in the Pac-Man Game. Control Systems and Computers. 2024. 4. С. 19-33.

УДК 004.94

А.О. Новіков, аспірант ННІ комп’ютерних наук та штучного інтелекту кафедри математичного моделювання та аналізу даних, Харківський національний університет ім. В.Н. Каразіна, пл. Свободи, 4, Харків, Україна, 61022, ORCID: https://orcid.org/0009-0004-5914-7098, artem.slick@gmail.com

В.В. Яновський, доктор фіз.-мат. наук, професор, завідувач теоретичним відділом, “Інститут монокристалів” Національної Академії наук України, просп. Науки, 60, Харків, Україна, 61001,
ORCID: https://orcid.org/0000-0003-0461-749X, yanovsky@isc.kharkov.ua

АНАЛІЗ ПОШУКОВИХ І МУЛЬТИАГЕНТНИХ АЛГОРИТМІВ У ГРІ PAC-MAN

Вступ. У даній роботі досліджується ефективність пошукових та мультиагентних алгоритмів у контексті гри Pac-Man. Гра 0 моделює завдання управління автономними системами у двовимірному середовищі, де агент стикається з динамічними перешкодами. Використання класичних пошукових алгоритмів, таких як A*, BFS, а також мультиагентних підходів, таких як Alpha-Beta, Expectimax та Monte Carlo Tree Search (MCTS), дозволяє дослідити різні стратегії для вирішення задач оптимізації шляху та ухилення від динамічних загроз (привидів).

Мета статті. Метою даного дослідження є аналіз продуктивності різних алгоритмів у різних за складністю лабіринтах, зокрема за показниками середнього балу, часу виконання та відсотка перемог. Це дослідження спрямоване на порівняння ефективності пошукових та мультиагентних алгоритмів в умовах змінного середовища.

Методи. У дослідженні використано системний підхід та метод експериментального моделювання. Ефективність алгоритмів оцінювалася шляхом проведення численних експериментів у лабіринтах з різним рівнем складності.

Результати. Отримані результати показують, що пошукові алгоритми (A* та BFS) демонструють високу продуктивність у менш динамічних середовищах, тоді як мультиагентні алгоритми (Expectimax, Alpha-Beta, MCTS) більш ефективні в складніших лабіринтах з багатьма динамічними загрозами. Expectimax продемонстрував найкращі результати в середовищах із випадковими діями супротивників, тоді як MCTS показав високу продуктивність у великих та складних середовищах.

Висновки. Дослідження виявило, що вибір алгоритму залежить від складності лабіринту та необхідності врахування дій динамічних супротивників. Пошукові алгоритми є ефективними у спрощених умовах, тоді як мультиагентні підходи є перспективними для складних середовищ з динамічними загрозами.

Завантажити повний текст! (українською)

Ключові слова: алгоритми пошуку, мультиагентні алгоритми, Pac-Man, оптимізація шляху, Alpha-Beta, Expectimax, MCTS.

1. Foderaro G., Swingler A., Ferrari S. “A Model-Based Approach to Optimizing Ms. Pac-Man Game Strategies in Real Time.” IEEE Transactions on Computational Intelligence and AI in Games, 2017, 9 (2), pp. 153-165. DOI: https://doi.org/10.1109/TCIAIG.2016.2523508.
2. Rohlfshagen P., Liu J., Perez-Liebana D., Lucas S. M. “Pac-Man Conquers Academia: Two Decades of Research Using a Classic Arcade Game.” IEEE Transactions on Games, 2018, 10 (3), pp. 233-256. DOI: https://doi.org/10.1109/TG.2017.2737145.
3. Gallagher M., Ryan A. “Learning to play Pac-Man: an evolutionary, rule-based approach.” The 2003 Congress on Evolutionary Computation, 2003, Canberra, ACT, Australia, pp. 2462-2469, Vol. 4. doi: https://doi.org/10.1109/CEC.2003.1299397.
4. Foderaro G., Raju V., Ferrari S. “A cell decomposition approach to online evasive path planning and the video game Ms. Pac-Man.” 2011 IEEE International Symposium on Intelligent Control, 2011, Denver, CO, USA, pp. 191-197. DOI: https://doi.org/10.1109/ISIC.2011.6045414.
5. Tucnik P., Nachazel T., Cech P., Bures V. “Comparative analysis of selected path-planning approaches in large-scale multi-agent-based environments.” Expert Systems with Applications, 2018, 113, pp. 415-427. DOI: https://doi.org/10.1016/j.eswa.2018.07.001.
6. Sajid Q., Luna R., Bekris K. “Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives.” Proceedings of the 5th Annual Symposium on Combinatorial Search, 2012, pp. 88-96. DOI: http://doi.org/10.1609/socs.v3i1.18243.
7. Saccon E., Palopoli L., Roveri M. “Comparing Multi-Agent Path Finding Algorithms in a Real Industrial Scenario.” In: Dovier, A., Montanari, A., Orlandini, A. (eds) AIxIA 2022 – Advances in Artificial Intelligence. AIxIA 2022. Lecture Notes in Computer Science, vol 13796. Springer, Cham, 2023. DOI: https://doi.org/10.1007/978-3-031-27181-6_13.
8. Erdem E., Kisa D., Oztok U., Schüller P. “A General Formal Framework for Pathfinding Problems with Multiple Agents.” Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013.
9. Hewawasam H., Ibrahim Y., Appuhamillage G. “Past, Present and Future of Path-Planning Algorithms for Mobile Robot Navigation in Dynamic Environments.” IEEE Open Journal of the Industrial Electronics Society, 2022, 3 (1), pp. 353-365. DOI: http://doi.org/10.1109/OJIES.2022.3179617.
10. Lu Y., Huo X., Arslan O., Tsiotras P. “Incremental Multi-Scale Search Algorithm for Dynamic Path Planning With Low Worst-Case Complexity.” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2012, 41, pp. 1556-1570. DOI: http://doi.org/10.1109/TSMCB.2011.2157493.
11. Saffidine A., Finnsson H., Buro M. “Alpha-Beta Pruning for Games with Simultaneous Moves.” Proceedings of the National Conference on Artificial Intelligence, 2012, 1.
12. Lee S. “Exploring to Learn Winning Strategy.” International Conferences Interfaces and Human Computer Interaction, Game and Entertainment Technologies, and Computer Graphics, Visualization, Computer Vision and Image Processing, 2019, pp. 377-380. DOI: http://dx.doi.org/10.33965/g2019_201906C052.
13. Dam T., D’Eramo C., Peters J., Pajarinen J. “A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search.” ArXiv abs/2202.07071, 2022.
14. Mirsoleimani S. A., Plaat A., van den Herik J., Vermaseren J. A. M. “Ensemble UCT Needs High Exploitation.” ArXiv abs/1509.08434, 2015.
15. Felner A., Stern R., Shimony S. E., Boyarski E., Goldenberg M., Sharon G., Sturtevant, N. R., Wagner, G., Surynek, P. “Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges.” Symposium on Combinatorial Search, 2021. DOI: https://doi.org/10.1609/socs.v8i1.18423.
16. Khandelwal P., Liebman  E., Niekum S., Scott A., Stone P. “On the Analysis of Complex Backup Strategies in Monte Carlo Tree Search.” International Conference on Machine Learning, 2016, pp. 1319-1328.
17. Ou T., Cao J., Lu Y., Wang Y.-P., Wu, X. “A New Decision-Making Approach via Monte Carlo Tree Search and A2C.” 2023 3rd International Conference on Computer Science, Electronic Information Engineering and Intelligent Control Technology (CEI), 2023, pp. 204-210. DOI: https://doi.org/10.1109/CEI60616.2023.10527918.
18. Silva M. A. L., Souza S. R. de, Freitas Souza M. J., Felizardo de França Filho M. “Hybrid metaheuristics and multi-agent systems for solving optimization problems: A review of frameworks and a comparative analysis.” Applied Soft Computing, 2018, 71, pp. 433-459. DOI: https://doi.org/10.1016/j.asoc.2018.06.050.

Надійшла 21.08.2024