МУЛЬТИАГЕНТНА СИСТЕМА РОЗПІЗНАВАННЯ НЕОРІЄНТОВАНИХ ГРАФІВ
DOI:
https://doi.org/10.32689/maup.it.2024.3.5Ключові слова:
розпізнавання графів, прості скінчені графи складність алгоритму, обхід в глибину, колектив агентівАнотація
Робота присвячена проблемі розпізнавання простих неорієнтованих графів мобільними агентами. Метою роботи є побудова нового ефективного алгоритму розпізнавання скінчених неорієнтованих графів без петель та кратних ребер мультиагентною системою. В статті запропоновано наступну методологію до досягнення поставленої мети: використати мультиагентну систему, що складається з трьох агентів двох різних типів. Перший тип – це агенти-дослідники, які рухаються по графу, можуть зчитувати мітки на елементах графу й змінювати забарвлення цих елементів. Також ці агенти можуть обмінюватися повідомленнями з агентом другого типу. Агенти-дослідники мають скінчену пам’ять та для розпізнавання графу використовують по дві фарби різного кольору кожен (всього три фарби різного кольору). Другий тип – це агент-експериментатор – нерухомий агент, що знаходиться поза межами графу, в пам’яті якого на кожному кроці фіксується результат функціонування агентів-дослідників. На основі отриманої інформації агент-експериментатор в своїй пам’яті поступово вибудовує представлення досліджуваного графа списком ребер і списком вершин. У статті детально розглянуто режими роботи агентів-дослідників із зазначенням пріоритетності активації цих режимів в процесі роботи. Також наведено алгоритм роботи агента-експериментатора з детальним описом процедур обробки отриманих повідомлень, на підставі яких і відбувається розпізнавання досліджуваного графа. Також в статті проведено аналіз часової, ємнісної, комунікаційної складності побудованого алгоритму та проаналізовано кількість переходів по ребрах, які необхідно виконати агентам-дослідникам для повного розпізнавання графа. Науковою новизною є отримання більш ефективного алгоритму розпізнавання графів, який дозволяє використовувати агентів-дослідників зі скінченою пам’яттю та дає можливість в подальшому масштабувати розглянуту мультиагентну систему до k агентів. Висновки. Таким чином, в роботі запропоновано новий алгоритм розпізнавання графів, який має квадратичні (від числа вершин досліджуваного графа) часову, ємнісну та комунікаційну складності. Кількість переходів по ребрах, які виконують агенти-дослідники оцінюється як On де n – кількість вершин досліджуваного графа. Робота запропонованого алгоритму розпізнавання ґрунтується на методі обходу графа в глибину.
Посилання
Albers S., Henzinger M. R. Exploring unknown environments. SIAM Journal on Computing. 2000. 29 (4). P. 1164–1188.
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
Cormen Ò., Leiserson Ch., Rivest R., Stein C. Introduction to Algorithms Cambridge, 2009. 1292 p.
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.
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
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
Dopp K. Automaten in labirinthen. Electronische Informationsverarbeitung und Kybernetik. 1971. V.7, № 2. P. 79–94.
Dudek G., Jenkin M. Computational principles of mobile robotics. Cambridge Univ. press. 2000. 280 p.
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.
Dudek G., Jenkin M., Milios E., Wilkes D. Topological exploration with multiple robots. Robotics with Application (ISORA): Proc. 7th International Symposium. Alaska, 1998
Feng Xiao, Long Wang, Jie Chen, Yanping Gao. Finite-time formation control for multi-agent systems. Automatica. V 45, Issue 11. 2009. P. 2605–2611. https://doi.org/10.1016/j.automatica.2009.07.012
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
Piña-García C., Rechy Ericka, Garcia-Vega Virginia. Using an Alternative Model in a Complex Environment for Nanorobotics Navigation. Proceedings of the 16th International Conference on Computing. Mexico City, Mexico, 2007. URL: http://magno-congreso.cic.ipn.mx/cd-2007/IEEE/paper_103.pdf
Selden M., Zhou J., Campos F., Lambert N., Drew D. and Pister K. S. J. BotNet: A Simulator for Studying the Effects of Accurate Communication Models on Multi-Agent and Swarm Control. 2021 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), Cambridge, United Kingdom, 2021, pp. 101–109, doi: 10.1109/MRS50823.2021.9620611.
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.
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
Zhang C. Parallelizing Depth-First Search for Robotic Graph Exploration. Harvard College, Cambridge, Massachusetts. 2010.
Zhang T, Ma X, Li H, Wang Z, Xie S, Luo J. Ordered-Bipartite Consensus of Multi-Agent Systems under Finite Time Control. Applied Sciences. 2022; 12(23):12337. https://doi.org/10.3390/app122312337ц
