Finite graph exploration by a mobile agent

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.

mobile agent
finite graph
graph exploration
  1. Glushkov V. M., Letichevsky A. A. Theory of Discrete Converters (Selected Topics of Algebra and Logic).  Novosibirsk, Nauka. 5–20 (1973).
  2. Stepkin A. V.  Finite Graphs Exploration by Three Agents.  Artificial Intelligence.  2, 84–93 (2011).
  3. Kuipers B.  The spatial semantic hierarchy.  Artificial Intelligence.  119 (1–2), 191–233 (2000).
  4. Dudek G., Jenkin M.  Computational principles of mobile robotics.  Cambridge, Cambridge University Press (2000).
  5. Shannon C. E.  Presentation of a Maze-Solving Machine.  Cybernetics, Transactions of the 8th Conference, Editor: H. von Foerster.  173–180 (1951).
  6. Dopp K.  Automaten in labirinthen.  Electronische Informationsverarbeitung und Kybernetik.  7 (2), 79–94 (1971).
  7. 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).
  8. Grunskiy I. S., Tatarinov E. A.  Recognition of a finite graph by an agent wandering on it.  Bulletin of DonNU.  1, 492–497 (2009).
  9. 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).
  10. 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).
  11. 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).
  12. Zhang C.  Parallelizing Depth-First Search for Robotic Graph Exploration.  Harvard College, Cambridge, Massachusetts (2010).
  13. 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).
  14. Stepkin A.  Using a Collective of Agents for Exploration of Undirected Graphs.  Cybernetics and Systems Analysis.  51 (2), 223–233 (2015).
  15. Stepkin A.  Exploration of the graph structure by two agents.  Proceedings of IAMM of NASU.  30, 111–121 (2016).
  16. 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).
  17. 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).
  18. 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).
  19. Stepkin A. V.  Possibility and complexity of graph exploration by three agents.  Tavricheskiy Vestnik Informatics and Mathematics.  1 (20), 88–98 (2012).
  20. Goth G.  Exploring new frontiers.  Communications of the ACM.  52 (11), 21–23 (2009).
  21. Cormen Т., Leiserson Ch., Rivest R., Stein C.  Introduction to Algorithms.  MIT Press (2009).
  22. Aho A., Hopcroft J., Ullman J.  Design and Analysis of Computer Algorithms.  Addison-Wesley (1974).