1. MMC
  2. All Volumes and Issues
  3. Volume 12, Number 2, 2025
  4. Exploration of simple graphs by a collective of agents

Exploration of simple graphs by a collective of agents

MMC.
2025;
Volume 12, Number 2
: pp. 603–610
https://doi.org/10.23939/mmc2025.02.603
Received: January 27, 2025
Accepted: May 04, 2025

Stopkin A. V.  Exploration of simple graphs by a collective of agents.  Mathematical Modeling and Computing. Vol. 12, No. 2, pp. 603–610 (2025)

Authors:
  1. A. V. Stopkin
1
SHEI "Donbas State Pedagogical University"

The article addresses the problem of exploring simple undirected graphs using a multi-agent system consisting of two agents: an agent-researcher, which can traverse the graph, read and modify the labels of its elements, and exchange information with the second agent – an agent-experimenter, which constructs a map of the explored graph in its memory in the form of edge and node lists.  An algorithm is proposed with quadratic time, space, and communication complexities (with respect to the number of nodes in the graph).  The upper estimate of the number of transitions along the edges made by the agent-researcher is estimated as $O(n^2)$.  The algorithm operates using one color and one stone.  An algorithm is based on depth-first traversal method.

graph exploration
multi-agent system
graph traversal
algorithm complexity
depth-first traversal method
  1. Glushkov V. M., Letichevsky A. A.  Theory of Discrete Converters (Selected Topics of Algebra and Logic).  Nauka. 5–20 (1973).
  2. Stopkin A. V.  Finite graph exploration by a mobile agent.  Mathematical Modeling and Computing.  12 (1), 75–82 (2025).
  3. Kuipers B.  The spatial semantic hierarchy.  Artificial Intelligence.  119 (1–2), 191–233 (2000).
  4. Fraigniaud P., Jecincas D., Peer G., Pelc A., Peleg D.  Graph Exploration by a Finite Automaton.  Mathematical Foundations of Computer Science 2004 (MFCS 2004).  451–462 (2004).
  5. Das S., Flocchini P., Kutten S., Nayak A., Santoro N.  Map construction of unknown graphs by multiple agents.  Theoretical Computer Science.  385 (1–3), 34–48 (2007).
  6. Wang H., Jenkin M., Dymond P.  It can be beneficial to be 'lazy' when exploring graph-like worlds with multiple robots.  Proceedings of the IASTED International Conference on Advances in Computer Science and Engineering (ACSE).  55–60 (2009).
  7. Nagavarapu S. C., Vachhani L., Sinha A., Buriuly S.  Generalizing Multi-agent Graph Exploration Techniques.  International Journal of Control, Automation and Systems.  19, 491–504 (2020).
  8. Stopkin A. V.  Algorithm for exploration of a simple undirected graph by a collective of agents.  Scientific notes of Taurida National V. I. Vernadsky University. Series: Technical Sciences.  35 (74 (5)), 303–309 (2024).
  9. Stopkin A. V.  Multi-agent system for non-oriented graphs exploration.  Information Technology and Society.  3 (14), 38–43 (2024).
  10. Stepkin A.  Using a Collective of Agents for Exploration of Undirected Graphs.  Cybernetics and Systems Analysis.  51 (2), 223–233 (2015).
  11. Selden M., Zhou J., Campos F., Lambert N., Drew D., 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).  101–109 (2021).
  12. Li D., Ge S. S., He W., Ma G., Xie L.  Multilayer formation control of multi-agent systems.  Automatica.  109, 108558 (2019).
  13. 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.  12 (23), 12337 (2022).