Finite Undirected Graphs Exploration by a Mobile Agent

Since any environment can be represented as a graph, the problem of graph exploration remains highly relevant.  This paper investigates the exploration of finite, connected, simple, and undirected graphs by a mobile agent.  A new graph exploration method is proposed, along with an algorithm that enables the mobile agent to traverse the graph, read and modify labels of its elements, and incrementally reconstruct the graph structure in its memory.  The algorithm is based on the depth-first search approach and uses an implicit node numbering technique.  It is proven that the graph reconstructed by the mobile agent is isomorphic to the explored graph.  The proposed algorithm has quadratic time and space complexities with respect to the number of nodes.  The number of required edge transitions is also estimated to be quadratic.  The algorithm operates using paint of a single color.

undirected graph
mobile agent
graphs exploration
  1. Albers S., Henzinger M. R.  Exploring unknown environments.  SIAM Journal on Computing.  29 (4), 1164–1188 (2000).
  2. Dopp K.  Automaten in Labyrinthen.  Electronische Informationsverarbeitung und Kybernetik.  7 (2), 79–94 (1971).
  3. Dudek G., Jenkin M., Milios E., Wilkes D.  Map Validation and Self-lo cation in a Graph-like World. Proceedings of the 13th International Joint Conference on Artifical Intelligence (Chambery, France, August 1993).  1648–1653 (1993).
  4. Stopkin A. V.  Finite graph exploration by a mobile agent.  Mathematical Modeling and Computing.  12 (1), 75–82 (2025).
  5. Dhar A. K., Gorain B., Mondal K., Patra Sh., Singh R.  Edge exploration of anonymous graph by mobile agent with external help.  Computing.  105, 483–506 (2023).
  6. 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).
  7. Stopkin A. V.  Exploration of simple graphs by a collective of agents.  Mathematical Modeling and Computing.  12 (2), 603–610 (2025).
  8. 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).
  9. Sapunov S. V.  Directional Movement of a Col-lective of Compassless Automata on a Square Lattice of Width 2.  Cybernetics and Systems Analysis.  60 (6), 899–906 (2024).
  10. 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).
  11. Li Dongyu, Sam Ge Shuzhi, He Wei, Ma Guangfu, Xie Lihua.  Multilayer formation control of multi-agent systems.  Automatica.  109, 899–906 (2019).
  12. Amirkhani A., Barshooi A. H.  Consensus in multi-agent systems: a review.  Artificial Intelligence Review.  55, 3897–3935 (2022).
  13. Shannon C. E.  Presentation of a maze-solving machine.  Cybernetics Trans, of the 8th Conf. of the JosiahMacy Jr. Found / Editor: H. Foerster.  173–180 (1951).
  14. Dudek G., Jenkin M., Milios E., Wilkes D.  A taxonomy for swarm robots.  Proceedings of 1993 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '93).  441–447 (1993).
  15. 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).
  16. Stepkin A. Using a Collective of Agents for Exploration of Undirected Graphs.  Cybernetics and Systems Analysis.  51 (2), 223–233 (2015).
  17. Stopkin A. V.  The use of a collective of mobile agents for the exploration of undirected graphs.  Information Technology and Society.  1 (16), 249–255. (2025).
  18. Grunskiy I. S., Tatarinov E. A.  Recognition of a finite graph by an agent wandering on it.  Bulletin of DonNU.  1, 492–497 (2009).
  19. Dudek G., Jenkin M., Milios E., Wilkes D.  Topological exploration with multiple robots.  Proceedings of the Seventh Intl. Symposium on Robotics with Applications (1998).