Multi-agent graph exploration system

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