Аналіз динамічних алгоритмів для пошуку шляху в умовах змінного середовища
Анотація
Здійснено дослідження основних проблем та запропоновано можливі варіанти вдосконалення динамічних алгоритмів пошуку шляху за умов змінних середовищ. Проаналізовано алгоритми A*, D*, D* Lite, які, незважаючи на здатність швидко оновлювати шляхи, стикаються зі значними проблемами ефективності у складних ігрових сценаріях з численними змінами в оточенні. Встановлено, що в таких випадках відбувається збільшення тривалості обчислень та значні витрати пам'яті на зберігання великої кількості проміжних станів і перерахунок нових маршрутів, що обмежує їх застосування в реальних умовах, де потрібні швидкі рішення та мала затримка. Досліджено алгоритми підкріплювального та глибокого навчання, які, хоча й мають значний потенціал до адаптації та самонавчання, потребують використання істотних обчислювальних ресурсів і великих обсягів навчальних даних, що ускладнює їх застосування в змінних ігрових середовищах із обмеженими обчислювальними та часовими ресурсами. Оцінено вплив гібридних алгоритмів, таких як поєднання A* з динамічними вікнами, які дають можливість значно зменшити кількість обчислень під час пошуку шляхів у динамічних середовищах. Виявлено, що гібридні алгоритми забезпечують гнучкість і дають змогу швидше адаптуватися до змін оточення, проте потребують додаткових витрат ресурсів для забезпечення оперативного обробляння змін. З'ясовано, що генетичні алгоритми мають здатність знаходити шляхи з високою точністю у статичних або змінних умовах середньої складності, але в реальному часі з високою динамікою середовища вони є повільнішими від евристичних алгоритмів приблизно на 30 %, що робить їх менш ефективними в ігрових умовах з великою кількістю змінних факторів. Охарактеризовано закономірності використання гібридних підходів, які поєднують класичні евристичні методи із сучасними підходами на підставі штучного інтелекту. Встановлено, що комбінації глибокого навчання з традиційними алгоритмами пошуку шляхів, такими як A*, дають змогу істотно підвищити точність і ефективність планування шляху в динамічних умовах. Зокрема, інтеграція сучасних методів машинного навчання з евристичними алгоритмами пошуку шляхів відкриває перспективи для їх ефективного використання у складних ігрових середовищах, де критично важлива швидка адаптація до змін. Такі гібридні підходи забезпечують більш оптимальний баланс між продуктивністю й адаптивністю алгоритмів, роблячи їх придатними для сценаріїв зі значною динамікою, що мають наукову та практичну цінність.
Завантаження
Посилання
Almazrouei, K., Kamel, I., & Rabie, T. (2023). Dynamic Obstacle Avoidance and Path Planning through Reinforcement Learning. Applied Sciences 2023, 13(14). https://doi.org/10.3390/app13148174
Cao, Y., Yang, Z., Liu, H., Zhao, J., & Fan, J. (2023). Improved A*-DWA fusion path planning algorithm with ideal path area constraints, 01 August 2023, PREPRINT (Version 1) available at Research Square. https://doi.org/10.21203/rs.3.rs-3184042/v1
Fox, D., Burgard, W., & Thrun, S. (1997). The dynamic window approach to collision avoidance. IEEE Robotics & Automation Magazine, 4, 23–33. https://doi.org/10.1109/100.580977
Grytsiuk, P. Y., Ivanyshyn, A. V., & Hrytsiuk, Y. I. (2023). Quality assurance of software products in accordance with IEEE 730-2014 standard within the project implementation lifecycle. Scientific Bulletin of UNFU, 33(2), 101–117. https://doi.org/10.36930/40330214
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
Hinton, G. E., Osindero, S., & Teh, Y. W. (2006). A fast learning algorithm for deep belief nets. Neural computation, 18(7), 1527–1554. https://doi.org/10.1162/neco.2006.18.7.1527
Huang, S., Ontañón, S., Bamford, C., & Grela, L. (2021). Gym-µRTS: Toward Affordable Full Game Real-time Strategy Games Research with Deep Reinforcement Learning. Conference on Games, 1–8. https://doi.org/10.1109/LRA.2020.3012511
Keselman, A., Ten, S., Ghazali, A., & Jubeh, M. (2018). Reinforcement Learning with A* and a Deep Heuristic. arXiv: Learning. https://doi.org/10.48550/arXiv.1811.07745
Koenig, S., & Likhachev, M. (2002). D* Lite. URL: https://idm-lab.org/bib/abstracts/papers/aaai02b.pdf
Krafft, Carina (2020). Implementation and comparison of pathfinding algorithms in a dynamic 3D space. URL: https://reposit.haw-hamburg.de/handle/20.500.12738/10700
LeCun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278–2324. https://doi.org/10.1109/5.726791
Machado, A. F. da V., Santos, U. O., Vale, H., Gonçalvez, R., Neves, T., Ochi, L. S., & Gonzalez Clua, E. W. (2011). Real Time Pathfinding with Genetic Algorithm. 2011 Brazilian Symposium on Games and Digital Entertainment, 215–222. https://doi.org/10.1109/SBGAMES.2011.23
Martinez, D., Riazuelo, L., & Montano, L. (2022). Deep reinforcement learning oriented for real world dynamic scenarios. Perception and Navigation for Autonomous Robotics in Unstructured and Dynamic Environments (PNARUDE) workshop in IROS 2022. https://doi.org/10.48550/arXiv.2210.11392
Rawat, S., Chowdhary, S., & Dwivedi, S. (2023). Advancing AI Pathfinding in Games: A Study of Pathfinding Algorithms and Novel Approaches for Immersive and Adaptive Navigation. https://doi.org/10.13140/RG.2.2.18594.40645
Robotic Motion Planning: A* and D* Search. (n.d.). 16-735, Howie Choset with slides from Ayorkor Mills-Tettey, Vincent Lee-Shue Jr. Prasad Narendra Atkar, Kevin Tantisevi. URL: https://www.cs.cmu.edu/~motionplanning/lecture/AppH-astar-dstar_howie.pdf
Rodriguez Torrado, R., Bontrager, P., Togelius, J., Liu, J., & Perez-Liebana, D. (2018). Deep Reinforcement Learning for General Video Game AI. Conference on Computational Intelligence and Games, 1–8. https://doi.org/10.48550/arXiv.1806.02448
Sandberg, O. (2024). Pathfinding Algorithm Comparison in Dynamic Congested Environment. URL: https://www.diva-portal.org/smash/record.jsf?pid=diva2%3A1879887&dswid=942
Stentz, A. (1994). Optimal and efficient path planning for unknown and dynamic environments. Intelligent Unmanned Ground Vehicles, 203–220. https://doi.org/10.1007/978-1-4615-6325-9_11
Sutton, R. S., & Barto, A. G. (1992). Reinforcement learning: An introduction. IEEE Transactions on Neural Networks, 9(1), 1054–1059. https://doi.org/10.1007/BF00992698
Zehua, A., Xiaoping, R., & Chaojie, G. (2023). Improved A* Navigation Path-Planning Algorithm Based on Hexagonal Grid. ISPRS International Journal of Geo-Information, 13, 166. https://doi.org/10.3390/ijgi13050166
Переглядів анотації: 86 Завантажень PDF: 107
