The paper considers the task of finite connected graph exploration by a mobile agent. The mobile agent moves along the graph, reads and changes marks of the graph elements, and explores the graph based on this information. A new algorithm for finite undirected graph exploration of time complexity $O(n^{3})$, space complexity $O(n^{2})$ and the upper estimate of the number of transitions along the edges made by the agent $O(n^{3})$ is proposed. For the algorithm to work, the agent needs one color. The algorithm is based on depth-first traversal method.
- Glushkov V. M., Letichevsky A. A. Theory of Discrete Converters (Selected Topics of Algebra and Logic). Novosibirsk, Nauka. 5–20 (1973).
- Stepkin A. V. Finite Graphs Exploration by Three Agents. Artificial Intelligence. 2, 84–93 (2011).
- Kuipers B. The spatial semantic hierarchy. Artificial Intelligence. 119 (1–2), 191–233 (2000).
- Dudek G., Jenkin M. Computational principles of mobile robotics. Cambridge, Cambridge University Press (2000).
- Shannon C. E. Presentation of a Maze-Solving Machine. Cybernetics, Transactions of the 8th Conference, Editor: H. von Foerster. 173–180 (1951).
- Dopp K. Automaten in labirinthen. Electronische Informationsverarbeitung und Kybernetik. 7 (2), 79–94 (1971).
- 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. 1648–1653 (1993).
- Grunskiy I. S., Tatarinov E. A. Recognition of a finite graph by an agent wandering on it. Bulletin of DonNU. 1, 492–497 (2009).
- 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).
- Dudek G., Jenkin M., Milios E., Wilkes D. Topological exploration with multiple robots. Proceedings of the 7th International Symposium on Robotics with Application (ISORA). Anchorage, Alaska, USA (1998).
- 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).
- Zhang C. Parallelizing Depth-First Search for Robotic Graph Exploration. Harvard College, Cambridge, Massachusetts (2010).
- 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).
- Stepkin A. Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and Systems Analysis. 51 (2), 223–233 (2015).
- Stepkin A. Exploration of the graph structure by two agents. Proceedings of IAMM of NASU. 30, 111–121 (2016).
- Nagavarapu S. C., Vachhani L., Sinha A. Multi-Robot Graph Exploration and Map Building with Collision Avoidance: A Decentralized Approach. Journal of Intelligent & Robotic Systems. 83, 503–523 (2016).
- Banfi J., Quattrini Li A., Rekleitis I., Amigoni F., Basilico N. Strategies for coordinated multirobot exploration with recurrent connectivity constraints. Autonomous Robots. 42, 875–894 (2018).
- 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 (2021).
- Stepkin A. V. Possibility and complexity of graph exploration by three agents. Tavricheskiy Vestnik Informatics and Mathematics. 1 (20), 88–98 (2012).
- Goth G. Exploring new frontiers. Communications of the ACM. 52 (11), 21–23 (2009).
- Cormen Т., Leiserson Ch., Rivest R., Stein C. Introduction to Algorithms. MIT Press (2009).
- Aho A., Hopcroft J., Ullman J. Design and Analysis of Computer Algorithms. Addison-Wesley (1974).