GRAPH EXPLORATION OF CONNECTED UNDIRECTED GRAPHSBY A MOBILE AGENT
DOI:
https://doi.org/10.35546/kntu2078-4481.2025.1.2.29Keywords:
graph exploration, undirected graph, mobile agent, exploration complexities, depth-first traversal methodAbstract
The research addresses the problem of exploring finite connected undirected graphs without loops and multiple edges by a mobile agent. The goal of the study is to develop a new efficient method for graph exploration and an algorithm based on this method. The proposed methodology involves the use of a mobile agent capable of traversing the graph, reading, and leaving markers on graph elements. The agent has finite memory at each step, but its capacity can grow unboundedly depending on the graph being explored. The exploration process is performed using a single color of paint.Based on the data collected during graph traversal, the mobile agent gradually constructs a representation of the explored graph in its memory in the form of an edge list and a node list. The graph exploration algorithm based on the depth-first traversal method. The article provides a detailed analysis of the operational modes of the mobile agent, highlighting the priority of activating these modes during the exploration process. Additionally, the study analyzes the time and space complexities of the proposed algorithm and evaluates the number of edge transitions required for the mobile agent to fully explore the graph. The scientific novelty lies in the development of a new efficient method and algorithm for graph exploration. This method requires only a single color of paint and serves as a foundation for the development of multi-agent systems in the future. The algorithm demonstrates quadratic time and quadratic memory complexities, while the upper bound of the number of edge transitions performed by the mobile agent is estimated as O(n2).
References
Goth G. Exploring new frontiers. Communications of the ACM. 2009. 52(11). P. 21–23.
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. V 109. 2019 https://doi.org/10.1016/j.automatica.2019.108558
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. https://doi.org/10.3390/app122312337
Стьопкін А. В. Алгоритм розпізнавання простих неорієнтованих графів колективом агентів. Вчені записки таврійського національного університету імені В. І. Вернадського Серія: Технічні науки. Київ, 2024. Т. 35(74) № 5. C. 303–309. https://doi.org/10.32782/2663-5941/2024.5.1/43
Стьопкін А. В. Мультиагентна система розпізнавання неорієнтованих графів. Інформаційні технології та суспільство. Київ, 2024. Вип. 3(14). 38–43 с.
Stopkin A. V. Finite graph exploration by a mobile agent. Mathematical Modeling and Computing. 2025 Vol. 12, No. 1, pp. 75–82.
Shannon C. E. Presentation of a maze-solving machine. Cybernetics Trans, of the 8th Conf. of the JosiahMacy Jr. Found / Editor: H. Foerster. 1951. pp. 173–180.
Dopp K. Automaten in labirinthen. Electronische Informationsverarbeitung und Kybernetik. 1971. V. 7, № 2. pp. 79–94.
Dudek G., Jenkin M., Milios E., Wilkes D. Map validation in a graphlike world. Proceedings of the 13th International Joint Conference on Artifical Intelligence (Chambery, France, August 1993). San Fransisco: Morgan Kaufmann Publishers Inc., 1993. pp. 1648–1653.
Сапунов С. В., Сенченко А. С. Лингвистическое представление графов с помеченными вершинами. Доповіді Національної академії наук України, 2019. № 11. С. 17–24.
Dudek G., Jenkin M., Milios E., Wilkes D. A taxonomy for swarm robots. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Yokohama, Japan, 1993. pp. 441–447.
Dudek G., Jenkin M., Milios E., Wilkes D. Topological exploration with multiple robots. Proc. 7th International Symposium on Robotics with Application (ISORA). Anchorage, Alaska, USA, 1998.
Грунский И. С., Татаринов Е. А. Распознавание конечного графа блуждающим по нему агентом. Вестник ДонНУ, 2009, Вып.1. С. 492–497.
Грунский И. С., Стёпкин А. В. Распознавание конечного графа коллективом агентов. Труды ИПММ НАН Украины, 2009. Т.19. C. 43−52.
Стёпкин А. В. Распознавание конечных графов тремя агентами / А. В. Стёпкин // Искусственный интеллект. 2011. № 2. С. 84–93.
Stepkin A. Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and Systems Analysis. 2015. V.51, № 2. pp. 223–233. https://doi.org/10.1007/s10559-015-9715-z
Cormen Т., Leiserson Ch., Rivest R., Stein C. Introduction to Algorithms. Cambridge, 2009. 1292 p.
Aho, A. V., Hopcroft, J. E., Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Reading, Mass.: Addison-Wesley.
