THE USE OF A COLLECTIVE OF MOBILE AGENTS FOR THE EXPLORATION OF UNDIRECTED GRAPHS
DOI:
https://doi.org/10.32689/maup.it.2025.1.32Keywords:
graph exploration, undirected graphs, algorithm complexity, depth-first traversal method, collective of agentsAbstract
The study proposed in this work is devoted to the problem of graph exploration by a collective of agents consisting of one stationary agent, which performs the necessary computations, and two mobile agents, which move through the graph and collect information about its structure. The purpose of this work is to develop a new efficient algorithm for the exploration of finite undirected graphs without loops and multiple edges by a collective of agents. The paper proposes the following methodology to achieve this goal: utilizing a collective of three agents. Two of them are agent-researchers, which can move through the graph, read labels on graph elements, and place or remove these labels. The agent-researchers have finite memory that does not depend on the number of nodes in the explored graph and use two colors each (three distinct colors in total) for graph exploration. During the process, the agent-researchers send messages to the third agent, the agent-experimenter, which is a stationary agent that stores the results of the agent-researchers' operations. Based on this information, the agent-experimenter gradually constructs a representation of the explored graph in its memory in the form of edge and node lists. The paper describes the working modes of the agent-researchers in detail. It also thoroughly examines the algorithm for processing the messages received by the agent-experimenter from the agent-researchers, which serves as the basis for constructing a map of the explored graph. The study analyzes the time, space, and communication complexities of the developed algorithm and evaluates the number of edge transitions required for agents to explore the graph. The scientific novelty lies in the development of an efficient algorithm for graph exploration by a collective of agents. Conclusions. The paper proposes a new graph exploration algorithm that has quadratic time, space, and communication complexities, with the number of edge transitions performed by the agent-researchers being estimated as On2 , where n is the number of nodes in the explored graph. The functioning of the proposed exploration algorithm is based on the depth-first traversal method.
References
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.
