Штучний інтелект

Анотація: В статті розглядається проблема розпізнавання простих неорієнтованих графів мультиагентними системами. Система, що розглядається в статті, складається з трьох агентів: два агенти-дослідники, які можуть рухатись графом, зчитувати та змінювати помітки елементів графа та обмінюватись інформацією з третім агентом – агентом-експериментатором, який і будує мапу досліджуваного графу в своїй пам’яті у вигляді списків ребер та вершин. Запропоновано алгоритм розпізнавання квадратичної (від числа вершин графа) часової, ємнісної та комунікаційної складностей. Число переходів по ребрах, які треба здійснити агентам-дослідникам, оцінюється як . Також у роботі наведено процедуру пошуку нових підграфів для розпізнавання, у випадку, коли один з агентів-дослідників закінчив розпізнавання своєї частини, а другий продовжує роботу, що дозволяє зменшити витрати часу та більш рівномірно використовувати ресурси агентів-дослідників для розпізнавання графа. Для роботи алгоритму використовується три фарби різного кольору. Метод базується на методі обходу графа у глибину.

Ключові слова: розпізнавання графа, мультиагентна система, обхід графа, складність алгоритму, обхід в глибину.

Посилання:

1. Albers S., Henzinger M. R. Exploring unknown environments. SIAM Journal on Computing, 2000. 29 (4). P. 1164–1188.
2. Dudek G., Jenkin M., Milios E., Wilkes D. Map validation in a graphlike world. Proceedings of the 13th International Joint Conference on Artifical Intelligence. San Fransisco: Morgan Kaufmann Publishers Inc., 1993. P. 1648–1653.
3. Стёпкин А. В. Распознавание конечных графов тремя агентами. Искусственный интеллект, 2011. №2. С. 84 – 93.
4. Nagavarapu S. C., Vachhani L., Sinha A. et al. Generalizing Multi-agent Graph Exploration Techniques. International Journal of Control, Automation and Systems. 2020. https://doi.org/10.1007/s12555-019-0067-8
5. Dey, S.; Xu, H. Intelligent Distributed Swarm Control for Large-Scale Multi-UAV Systems: A Hierarchical Learning Approach. Electronics 2023, 12(1):89. https://doi.org/10.3390/electronics12010089
6. Dongyu Li, Shuzhi Sam Ge, Wei He, Guangfu Ma, Lihua Xie. Multilayer formation control of multi-agent systems. Automatica. V 109. 2019 https://doi.org/10.1016/j.automatica.2019.108558
7. Amirkhani, A., Barshooi, A.H. Consensus in multi-agent systems: a review. Artif Intell Rev 55, 3897–3935 (2022). https://doi.org/10.1007/s10462-021-10097-x
8. Shannon C. E. Presentation of a maze-solving machine. Cybernetics Trans, of the 8 th Conf. of the JosiahMacy Jr. Found / Editor: H. Foerster. 1951. P. 173–180.
9. Dopp K. Automaten in labirinthen. Electronische Informationsverarbeitung und Kybernetik. 1971. V.7, №2. P. 79–94.
10. Dudek G., Jenkin M., Milios E., Wilkes D. Topological exploration with multiple robots. Robotics with Application (ISORA): Proc. 7th International Symposium. Alaska, 1998
11. Wang H., Jenkin M., Dymond P. It can be beneficial to be ‘lazy’ when exploring graph-like worlds with multiple robots. Advances in Computer Science and Engineering (ACSE): In Proceedings of the IASTED International Conference. 2009. P. 55–60.
12. Zhang C. Parallelizing Depth-First Search for Robotic Graph Exploration. Harvard College, Cambridge, Massachusetts. 2010.
13. Nagavarapu, S. C., Vachhani, L. & Sinha, A. Multi-Robot Graph Exploration and Map Building with Collision Avoidance: A Decentralized Approach. Journal of Intelligent & Robotic Systems. 2016. 83. P. 503–523 https://doi.org/10.1007/s10846-015-0309-9
14. Das S., Flocchini P., Kutten S., Nayak A., Santoro N. Map construction of unknown graphs by multiple agents. Theoretical Computer Science. 2007. V.385, 1–3. P. 34 – 48.
15. Stepkin A. Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and Systems Analysis. V.51, 2. 2015 223–233. https://doi.org/10.1007/s10559-015-9715-z