Algorithm for recognizing simple graphs by a collective of agents
DOI:
https://doi.org/10.17721/1812-5409.2025/2.33Keywords:
undirected graphs, graph exploration, agent collective, algorithm complexity, depth-first traversal methodAbstract
These days, automation and robotization across various processes are developing rapidly. Naturally, this trend also extends to exploring environments where human operation is more difficult – or even dangerous – than operating under the same conditions with specialized robotic systems. This makes research on exploring unknown graphs (map construction) by mobile agents particularly relevant. This paper proposes a new algorithm for exploring finite, undirected, simple graphs by two different types of agents. One agent, the researcher, moves through the graph, reads and modifies marks on graph elements, and transmits information about its actions to the other agent – the experimenter. The researcher's operation is based on a depth-first graph traversal method. The researcher agent has finite memory that does not depend on the dimension of the graph. The experimenter agent operates outside the explored graph. Its main task is to build an internal representation of the explored graph (as a list of edges and nodes) based on information received from the researcher agent. The experimenter agent has finite but unboundedly growing memory, the size of which depends on the number of nodes in the explored graph. This paper examines in detail the researcher's modes of operation, indicating the priority of their activation depending on local conditions, and lists the messages exchanged by the agents during the algorithm. The complete algorithm for the experimenter to process the received messages – on the basis of which graph exploration takes place – is also provided. Additionally, the paper analyzes the time, space, and communication complexity of the algorithm and the number of edge traversals performed by the researcher during graph traversal. It is shown that the proposed algorithm has quadratic (from the number of nodes of the explored graph) time, space and communication complexity. The upper estimate of the number of transitions along the edges performed by the researcher agent is estimated as O(n2), where n is the number of nodes in the graph. For the work of proposed graph exploration algorithm, the researcher agent needs two paints of different colors and one stone.
Pages of the article in the issue: 211 - 216
Language of the article: EnglishReferences
Banfi, J., Quattrini Li, A., Rekleitis, I., Amigoni, F., & Basilico, N. (2018). Strategies for coordinated multirobot exploration with recurrent connectivity constraints. Autonomous Robots, 42, 875–894. https://doi.org/10.1007/s10514-017-9652-y
Das, S., Flocchini, P., Kutten, S., Nayak, A., & Santoro, N. (2007). Map construction of unknown graphs by multiple agents. Theoretical Computer Science, 385(1–3), 34–48. https://doi.org/10.1016/j.tcs.2007.05.011
Dopp, K. (1971). Automaten in labirinthen. Electronische Informationsverarbeitung und Kybernetik, 7(2), 79–94.
Dudek, G., & Jenkin, M. (2024). Computational principles of mobile robotics (3rd ed.). Cambridge University Press. https://doi.org/10.1017/9781108682404
Dudek, G., Jenkin, M., Milios, E., & Wilkes, D. (1993). Map validation in a graphlike world. International Joint Conference on Artifical Intelligence: Proceedings of the 13th International Conference, Chambery (France), San Fransisco (USA), (pp. 1648–1653).
Dudek, G., Jenkin, M., Milios, E., & Wilkes, D. (1998). Topological exploration with multiple robots. Robotics with Application (ISORA): Proceedings of the 7th International Symposium, Alaska.
Fraigniaud, P., Jecincas, D., Peer, G., Pelc, A., & Peleg, D. (2004). Graph Exploration by a finite automaton. Proceedings of the 29th International Symposium on Mathematical Foundation of Computer Science (MFCS), (pp. 451–462).
Nagavarapu, S. C., Vachhani, L., Sinha, A., & Buriuly, S. (2020). Generalizing Multi-agent Graph Exploration Techniques. International Journal of Control, Automation and Systems, 19, 491–504. Springer. https://doi.org/10.1007/s12555-019-0067-8
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. Springer. https://doi.org/10.1007/s10846-015-0309-9
Stepkin, A. (2015). Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and Systems Analysis, 51(2), 223–233. https://doi.org/10.1007/s10559-015-9715-z
Wang, H., Jenkin, M., & Dymond, P. (2009). It can be beneficial to be ‘lazy' when exploring graph-like worlds with multiple robots. Advances in Computer Science and Engineering (ACSE): In Proceedings of the IASTED International Conference, (pp. 55–60).
Zhang, C. (2010). Parallelizing Depth-First Search for Robotic Graph Exploration. Harvard University.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Andrij Stopkin, Tetiana Turka
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
