Алгоритм розпізнавання неорієнтованих графів мультиагентною системою

А.В. Стьопкін, канд. фіз.-мат. наук
Державний вищий навчальний заклад
«Донбаський державний педагогічний університет»
Україна, 49010, Дніпро, вул. Наукова, 13
e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.

Èlektron. model. 2025, 47(2):36-47

https://doi.org/10.15407/emodel.47.02.036

АНОТАЦІЯ

Розглянуто проблеми розпізнавання графів мультиагентними системами. Запропоновано алгоритм розпізнавання простих неорієнтованих графів колективом агентів, що скла-дається з двох агентів різного типу: агент-дослідник та агент-експериментатор. Агент-дослідник може пересуватися по графу, зчитувати та змінювати колір елементів графа, а також може обмінюватися повідомленнями з іншим агентом. Агент-експериментатор — це агент який знаходиться за межами графа та може обмінюватися з агентом-дослідни-ком повідомленнями, на основі яких і будує мапу графа в своїй пам’яті у вигляді списків ребер та вершин. Агент-дослідник має скінчену пам’ять та для роботи використовує од-ну фарбу. Агент-експериментатор має скінчену на кожному кроці та необмежено зрос-таючу пам’ять, об’єм якої залежить від розмірності графа. Алгоритм має квадратичні ча-сову, ємнісну, комунікаційну складності та кількість переходів по ребрах, що здійснює агент-дослідник. Алгоритм ґрунтується на методі обходу в глибину.

КЛЮЧОВІ СЛОВА:

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

СПИСОК ЛІТЕРАТУРИ

1. Stopkin A.V. Finite graph exploration by a mobile agent. Mathematical Modeling and Compu-ting, 2025. Vol. 12, No. 1, pp. 75—82. URL: https://doi.org/10.23939/mmc2025.01.075 (дата звернення: 05.02.2025).
2. Stepkin A.V. Using a collective of agents for exploration of undirected graphs. Cyberne-tics and Systems Analysis. 2015. Т. 51, № 2. P. 223—233. URL: https://doi.org/10.1007/s10559-015-9715-z (дата звернення: 05.02.2025).
3. Banfi, J., Quattrini Li, A., Rekleitis, I. et al. Strategies for coordinated multirobot explora-tion with recurrent connectivity constraints. Autonomous Robots. 2018. 42. P. 875—894. URL: https://doi.org/10.1007/s10514-017-9652-y (дата звернення: 05.02.2025).
4. Nagavarapu, S.C., Vachhani, L., Sinha, A. et al. Generalizing Multi-agent Graph Explora-tion Techniques. International Journal of Control, Automation and Systems. 2020. URL: https://doi.org/10.1007/s12555-019-0067-8 (дата звернення: 05.02.2025).
5. Стьопкін А.В. Алгоритм розпізнавання простих неорієнтованих графів колективом агентів. Вчені записки таврійського національного університету імені В.І. Вер-надського Серія: Технічні науки. Київ, 2024. Т. 35 (74) № 5. C. 303—309. URL: https://doi.org/10.32782/2663-5941/2024.5.1/43 (дата звернення: 05.02.2025).
6. Стьопкін А.В. Мультиагентна система розпізнавання неорієнтованих графів. Інфо-рмаційні технології та суспільство. Київ, 2024. Вип. 3 (14). 38—43 с. URL: https://doi.org/10.32689/maup.it.2024.3.5 (дата звернення: 05.02.2025).
7. 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. URL: https://doi.org/10.1007/s10846-015-0309-9 (дата звернення: 05.02.2025).
8. Zhang C. Parallelizing Depth-First Search for Robotic Graph Exploration. Harvard Col-lege, Cambridge, Massachusetts. 2010.
9. Sapunov S.V. Minimal Deterministic Traversable Vertex Labelling of Infinite Square Grid Graph. Праці ІПММ НАН України, 2020. 34, 118—132. URL: https://doi.org/10.37069/1683-4720-2020-34-12 (дата звернення: 05.02.2025).
10. Sapunov S.V. Experiments on Recognition of Infinite Grid Graph Labelling. Праці ІПММ НАН України, 2021. 35 (1), 67—78. URL: https://doi.org/10.37069/1683-4720-2021-35-6 (дата звернення: 05.02.2025).
11. Sapunov S.V. Directional Movement of a Collective of Compassless Automata on a Square Lattice of Width 2. Cybernetics and Systems Analysis, 2024. 60(6), 899—906. URL: https://doi.org/10.1007/s10559-024-00727-x (дата звернення: 05.02.2025).
12. Dey, S.; Xu, H. Intelligent Distributed Swarm Control for Large-Scale Multi-UAV Systems: A Hierarchical Learning Approach. Electronics 2023, 12(1):89. URL: https://doi.org/10.3390/electronics12010089 (дата звернення: 05.02.2025).
13. 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. URL: https://doi.org/10.1109/MRS50823.2021.9620611 (дата звернення: 05.02.2025).
14. Dongyu Li, Shuzhi Sam Ge, Wei He, Guangfu Ma, Lihua Xie. Multilayer formation control of multi-agent systems. Automatica. V 109. 2019. URL: https://doi.org/10.1016/j.automatica.2019.108558 (дата звернення: 05.02.2025).
15. 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. URL: https://doi.org/10.1016/j.automatica.2009.07.012 (дата звернення: 05.02.2025).
16. Amirkhani, A., Barshooi, A.H. Consensus in multi-agent systems: a review. Artif Intell Rev, 2022. 55, 3897—3935. URL: https://doi.org/10.1007/s10462-021-10097-x (дата звернення: 05.02.2025).
17. 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. URL: https://doi.org/10.3390/app122312337 (дата звернення: 05.02.2025).

Повний текст: PDF