2. Home
  3. ARCHIVE
  4. 2025
  5. VOL 47, NO 2 (2025)
  6. pp. 36-47

AN ALGORITHM FOR RECOGNIZING UNDIRECTED GRAPHS BY A MULTIAGENT SYSTEM

A.V. Stopkin

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

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

ABSTRACT

The problems of graph recognition by multi-agent systems are considered. An algorithm for recognizing simple undirected graphs by a team of agents consisting of two agents of different types: a researcher agent and an experimenter agent is proposed. A researcher agent can move around the graph, read and change the color of graph elements, and exchange messages with another agent. The experimenter agent is an agent that is outside the graph and can exchange messages with the research agent, based on which it builds a map of the graph in its memory in the form of lists of edges and vertices. The researcher agent has a finite memory and uses only one paint. The experimental agent has a finite and unlimitedly growing memory at each step, the amount of which depends on the graph's dimension. The algorithm has quadratic time, capacity, communication complexity, and the number of edge transitions made by the research agent. The algorithm is based on the depth-first method.

KEYWORDS

algorithm complexity, depth-first traversal method, graph exploration, multi-agent system.

REFERENCES

  1. Banfi, J., Quattrini Li, A., Rekleitis, I., & Bekris, K.E. (2018). Strategies for coordinated multirobot exploration with recurrent connectivity constraints. Autonomous Robots, 42, 875-894. https://doi.org/10.1007/s10514-017-9652-y
  2. Nagavarapu, S.C., Vachhani, L., Sinha, A., & Natarajan, B. (2020). Generalizing multi-agent graph exploration techniques. International Journal of Control, Automation and Systems. https://doi.org/10.1007/s12555-019-0067-8
  3. Stopkin, A.V. (2024). Algorithm for exploring simple undirected graphs by a collective of agents. Scientific Notes of V.I. Vernadsky Taurida National University. Series: Technical Sciences, 35(74)(5), 303-309. https://doi.org/10.32782/2663-5941/2024.5.1/43
  4. Stopkin, A.V. (2024). Multi-agent system for exploring undirected graphs. Information Technologies and Society, 3(14), 38-43. https://doi.org/10.32689/maup.it.2024.3.5
  5. Nagavarapu, S.C., Vachhani, L., & Sinha, A. (2016). Multi-robot graph exploration and map building with collision avoidance: A decentralized approach. Journal of Intelligent & Robotic Systems, 83, 503-523. https://doi.org/10.1007/s10846-015-0309-9
  6. Zhang, C. (2010). Parallelizing depth-first search for robotic graph exploration. Harvard College, Cambridge, Massachusetts.
  7. Sapunov, S.V. (2020). Minimal deterministic traversable vertex labelling of infinite square grid graph. Pratsi IPMM NAN Ukrayiny, 34, 118-132. https://doi.org/10.37069/1683-4720-2020-34-12
  8. Sapunov, S.V. (2021). Experiments on recognition of infinite grid graph labelling. Pratsi IPMM NAN Ukrayiny, 35(1), 67-78. https://doi.org/10.37069/1683-4720-2021-35-6
  9. Sapunov, S.V. (2024). Directional movement of a collective of compassless automata on a square lattice of width 2. Cybernetics and Systems Analysis, 60(6), 899-906. https://doi.org/10.1007/s10559-024-00727-x
  10. Dey, S., & Xu, H. (2023). Intelligent distributed swarm control for large-scale multi-UAV systems: A hierarchical learning approach. Electronics, 12(1), 89. https://doi.org/10.3390/electronics12010089
  11. Selden, M., Zhou, J., Campos, F., Lambert, N., Drew, D., & Pister, K.S.J. (2021). BotNet: A simulator for studying the effects of accurate communication models on multi-agent and swarm control. In 2021 International Symposium on Multi-Robot and Multi-Agent Systems (MRS) Cambridge, United Kingdom. pp. 101-109. https://doi.org/10.1109/MRS50823.2021.9620611
  12. Li, D., Ge, S.S., He, W., Ma, G., & Xie, L. (2019). Multilayer formation control of multi-agent systems. Automatica, 109, 108558. https://doi.org/10.1016/j.automatica.2019.108558
  13. Xiao, F., Wang, L., Chen, J., & Gao, Y. (2009). Finite-time formation control for multi-agent systems. Automatica, 45(11), 2605-2611. https://doi.org/10.1016/j.automatica.2009.07.012
  14. Amirkhani, A., & Barshooi, A.H. (2022). Consensus in multi-agent systems: A review. Artificial Intelligence Review, 55, 3897-3935. https://doi.org/10.1007/s10462-021-10097-x
  15. Zhang, T., Ma, X., Li, H., Wang, Z., Xie, S., & Luo, J. (2022). Ordered-bipartite consensus of multi-agent systems under finite time control. Applied Sciences, 12(23), 12337. https://doi.org/10.3390/app122312337

Full text: PDF