GRAPH EXPLORATION ALGORITHM BY A TEAM OF AGENTS
DOI:
https://doi.org/10.35546/kntu2078-4481.2026.1.46Keywords:
graph exploration, undirected graph, mobile agent, exploration complexities, depth-first traversal methodAbstract
This paper addresses the problem of the graph exploration of finite connected undirected graphs without loops and multiple edges by a team of agents. The aim of the study is to develop a new method for the exploration of undirected graphs by a team of agents and to construct an algorithm based on this method. The following methodology is proposed to achieve the stated objective. The exploration process involves two agents. The first one is a stationary agent – the agentexperimenter – located outside the graph and responsible for constructing a map of the explored graph in the form of node and edge lists. All computations are performed on the basis of messages received from the second agent. The agent-experimenter possesses finite memory at each step, which may grow without bound over time. The second agent – the agent-researcher – is a mobile agent capable of traversing the explored graph, reading and modifying marks on graph elements, and sending messages to the agent-experimenter. During the execution of the algorithm, the agent-researcher colors the explored graph elements black, and upon completion all graph elements are colored. The agent-researcher has finite memory independent of the size of the explored graph and uses a single black color. The functioning of the agent team is ensured by the interaction of two fundamentally different algorithms: a graph traversal algorithm executed by the agentresearcher and a graph mapping algorithm executed by the agent-experimenter. The scientific novelty of the work lies in the development of a new method and algorithm for graph exploration by a team of agents that requires only a single color for exploration and can serve as a foundation for further extensions involving multiple agent-researchers. The algorithm has cubic time complexity, quadratic space complexity, and cubic communication complexity for the graph exploration problem. The upper bound on the number of edge traversals performed by the agent-researcher is estimated as O(n3).
References
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
Стьопкін А. В. Розпізнавання зв’язних неорієнтованих графів мобільним агентом. Вісник Херсонського національного технічного університету. Одеса, 2025. Т.2 1(92). С. 215–221. DOI: https://doi.org/10.35546/kntu2078-4481.2025.1.2.29
Kuipers B. The spatial semantic hierarchy. Artificial Intelligence. 2000. V. 119, № 1–2. pp. 191–233.
Dudek G, Jenkin M. Computational principles of mobile robotics. Cambridge, 2000. – 280 p.
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
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
Стьопкін А. В. Алгоритм розпізнавання простих неорієнтованих графів колективом агентів. Вчені записки таврійського національного університету імені В. І. Вернадського Серія: Технічні науки. Київ, 2024. Т. 35 (74) № 5. C. 303–309. https://doi.org/10.32782/2663-5941/2024.5.1/43
Stopkin A. V. Exploration of simple graphs by a collective of agents. Mathematical Modeling and Computing, 2025. Vol. 12, No. 2, pp. 603–610 https://doi.org/10.23939/mmc2025.02.603
Dey, S.; Xu, H. Intelligent Distributed Swarm Control for Large-Scale Multi-UAV Systems: A Hierarchical Learning Approach. Electronics 2023, 12(1):89. https://doi.org/10.3390/electronics12010089
Dhar A.K., Gorain B., Mondal K., Patra Sh., Singh R. Edge exploration of anonymous graph by mobile agent with external help. Computing, 2023. V.105, 483-506. https://doi.org/10.1007/s00607-022-01136-8
Dey, S.; Xu, H. Intelligent Distributed Swarm Control for Large-Scale Multi-UAV Systems: A Hierarchical Learning Approach. Electronics 2023, 12(1):89. https://doi.org/10.3390/electronics12010089
Dongyu Li, Shuzhi Sam Ge, Wei He, Guangfu Ma, Lihua Xie. Multilayer formation control of multi-agent systems. Automatica, 2019. V 109. https://doi.org/10.1016/j.automatica.2019.108558
Amirkhani, A., Barshooi, A.H. Consensus in multi-agent systems: a review. Artif Intell. Rev 55, 3897–3935 (2022). https://doi.org/10.1007/s10462-021-10097-x
Стьопкін А. В. Мультиагентна система розпізнавання неорієнтованих графів. Інформаційні технології та суспільство. Київ, 2024. Вип. 3 (14). 38-43 с. DOI: https://doi.org/10.32689/maup.it.2024.3.5
Grunsky, I. S., & Tatarinov, E. A. (2009). Recognition of a finite graph by a wandering agent. Bulletin of Donetsk National University, 1, 492–497.
