ВИКОРИСТАННЯ КОЛЕКТИВУ МОБІЛЬНИХ АГЕНТІВ ДЛЯ РОЗПІЗНАВАННЯ НЕОРІЄНТОВАНИХ ГРАФІВ
DOI:
https://doi.org/10.32689/maup.it.2025.1.32Ключові слова:
розпізнавання графів, неорієнтований граф, складність алгоритму, обхід в глибину, колектив агентівАнотація
Дослідження, запропоноване в роботі присвячено вивченню проблеми розпізнавання графів колективом агентів, що складається з одного нерухомого агента, що виконує необхідні обчислення та двох мобільних агентів, що рухаються графом та збирають інформацію про його структуру. Метою роботи є побудова нового ефективного алгоритму розпізнавання скінчених неорієнтованих графів без петель та кратних ребер колективом агентів. В статті запропоновано наступну методологію до досягнення поставленої мети: використати колектив агентів, що складається з трьох агентів. Два агенти є агентами-дослідниками, які можуть переміщуватися по графу, зчитувати мітки на елементах графу й залишати або видаляти ці мітки. Агенти-дослідники мають скінчену пам’ять, яка не залежить від кількості вершин досліджуваного графа та для розпізнавання графу використовують по дві фарби кожен (всього три фарби різного кольору). Під час роботи агенти-дослідники відправляють повідомлення третьому агенту – агенту-експериментатору, який представляє собою нерухомого агента, в пам’яті якого фіксується результат функціонування агентів-дослідників. На основі цієї інформації він поступово вибудовує в своїй пам’яті представлення досліджуваного графа списками ребер і вершин. У статті наведено режими роботи агентів-дослідників з їх детальним описом. Також детально розглянуто алгоритм обробки агентом-експериментатором повідомлень, отриманих від агентів-дослідників в процесі роботи, на підставі яких відбувається побудова мапи досліджуваного графа. В роботі проаналізовано часову, ємнісну, комунікаційну складності побудованого алгоритму та проведено аналіз кількості переходів по ребрах, які необхідно здійснити агентам для розпізнавання графа. Науковою новизною є отримання ефективного алгоритму розпізнавання графів колективом агентів. Висновки. В роботі запропоновано новий алгоритм розпізнавання графів, який має квадратичні часову, ємнісну та комунікаційну складності та кількість переходів по ребрах, які виконують агенти-дослідники, що оцінюється як On2 де n – кількість вершин досліджуваного графа. Робота запропонованого алгоритму розпізнавання ґрунтується на методі обходу графа в глибину.
Посилання
Banfi J., Quattrini Li, A., Rekleitis I. et al. Strategies for coordinated multirobot exploration with recurrent connectivity constraints. Autonomous Robots. 2018. Vol. 42. P. 875–894. https://doi.org/10.1007/s10514-017-9652-y
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.
Goth G. Exploring new frontiers. Communications of the ACM. 2009. 52(11). С. 21–23.
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
Sapunov S. V. Experiments on Recognition of Infinite Grid Graph Labelling. Праці ІПММ НАН України, 2021. 35 (1), 67–78. https://doi.org/10.37069/1683-4720-2021-35-6
Sapunov S. V. Minimal Deterministic Traversable Vertex Labelling of Infinite Square Grid Graph. Праці ІПММ НАН України, 2020. 34, 118–132. https://doi.org/10.37069/1683-4720-2020-34-12
Sapunov S. V. Directional Movement of a Collective of Compassless Automata on a Square Lattice of Width 2. Cybernetics and Systems Analysis, 2024. vol. 60, iss. 6, pp. 899–906. https://doi.org/10.1007/s10559-024-00727-x
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
Stopkin A. V. Algorithm for exploration of a simple undirected graph by a collective of agents. Scientific Notes of Taurida VI Vernadsky National University, 2024, vol. 35 (74), no. 5, pp. 303–309. https://doi.org/10.32782/2663-5941/2024.5.1/43
Stopkin A. V. Multi-agent system for non-oriented graphs exploration. Information Technology and Society, Kyiv, 2024, vol. 3, no. 14, pp. 38–43. https://doi.org/10.32689/maup.it.2024.3.5
Stopkin A. V. Finite graph exploration by a mobile agent. Mathematical Modeling and Computing, 2025, vol. 12, no. 1, pp. 75–82. https://doi.org/10.23939/mmc2025.01.075
Wang H., Jenkin M., Dymond P. Enhancing exploration in graph-like worlds. Proceedings of the Canadian Conference on Computer and Robot Vision (CRV). 2008. P. 53–60.