Artificial intelligence

Abstract: The article considers the problem of simple undirected graphs exploration by multi-agent systems. The system considered in the article consists of three agents: two agents-researchers, that can move through the graph, read and change the labels of the graph elements, and exchange information with the third agent - the agent-experimenter, which builds a map of the explored graph in its memory. An algorithm for exploration of quadratic (from the number of graph nodes) time, space and communication complexities is proposed. The number of transitions along the edges that should be made by agents-researchers is estimated as . The paper also provides a procedure for finding new subgraphs for exploration, in the case when one of the agents-researchers has finished exploring its part, and the second one continues to work. That allows to reduce time consumption and more evenly use the resources of agents-researchers for graph exploration. The algorithm uses three different colors. The method is based on the depth-first graph traversal method.

Keywords: graph exploration, multi-agent system, graph traversal, algorithm complexity, depth-first traversal method.

References:

1. Albers S., Henzinger M. R. Exploring unknown environments. SIAM Journal on Computing, 2000. 29 (4). P. 1164–1188.
2. Dudek G., Jenkin M., Milios E., Wilkes D. Map validation in a graphlike world. Proceedings of the 13th International Joint Conference on Artifical Intelligence. San Fransisco: Morgan Kaufmann Publishers Inc., 1993. P. 1648–1653.
3. Stepkin A. V. Raspoznavanie konechnykh hrafov tremya ahentami. Iskusstvennyy intellekt, 2011. #2. S. 84 – 93.
4. Nagavarapu S. C., Vachhani L., Sinha A. et al. Generalizing Multi-agent Graph Exploration Techniques. International Journal of Control, Automation and Systems. 2020. https://doi.org/10.1007/s12555-019-0067-8
5. 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
6. 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
7. Amirkhani, A., Barshooi, A. H. Consensus in multi-agent systems: a review. Artif Intell Rev 55, 3897–3935 (2022). https://doi.org/10.1007/s10462-021-10097-x
8. Shannon C. E. Presentation of a maze-solving machine. Cybernetics Trans, of the 8 th Conf. of the JosiahMacy Jr. Found / Editor: H. Foerster. 1951. P. 173–180.
9. Dopp K. Automaten in labirinthen. Electronische Informationsverarbeitung und Kybernetik. 1971. V.7, №2. P. 79–94.
10. Dudek G., Jenkin M., Milios E., Wilkes D. Topological exploration with multiple robots. Robotics with Application (ISORA): Proc. 7th International Symposium. Alaska, 1998
11. Wang H., Jenkin M., Dymond P. 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. 2009. P. 55–60.
12. Zhang C. Parallelizing Depth-First Search for Robotic Graph Exploration. Harvard College, Cambridge, Massachusetts. 2010.
13. 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. 2016. 83. P. 503–523 https://doi.org/10.1007/s10846-015-0309-9
14. Das S., Flocchini P., Kutten S., Nayak A., Santoro N. Map construction of unknown graphs by multiple agents. Theoretical Computer Science. 2007. V.385, 1–3. P. 34 – 48.
15. Stepkin A. Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and Systems Analysis. V.51, 2. 2015 223–233. https://doi.org/10.1007/s10559-015-9715-z