MULTI-AGENT SYSTEM FOR NON-ORIENTED GRAPHS EXPLORATION

Abstract

The work is devoted to the problem of simple undirected graphs exploration by mobile agents. The purpose of this work is to develop a new effective algorithm for exploring undirected graphs without loops and multiple edges by a multi-agent system. The article proposes the next methodology to achieve the goal: to use a multi-agent system that consists of three agents of two different types. The first type is agents-researchers, that move along the graph, can read the labels on the graph elements and color these elements. Also, these agents can exchange messages with the second type of agent. Agents-researchers have a finite memory and use two different colors each (total of three different colors) to a graph exploration. The second type is an agent-experimenter is a stationary agent located outside the graph, in whose memory the result of the functioning of the agents-researchers is recorded at each step. On the basis of the received information, the agentexperimenter in his memory gradually builds a map of the investigated graph. In the article in detail examines the modes of operation of agents-researchers with an indication of the priority of activation of these modes. Also given the algorithm of the agent-experimenter with a detailed description of the procedures for processing the received messages, on the basis of which the graph is explored. Also, the article analyzes the time, space, and communication complexity of the algorithm and analyzes the number of transitions along the edges that must be performed by agents-researchers for complete the graph exploration. A scientific novelty is the development of a more efficient graph exploration algorithm, which allows the use of agentsresearchers with finite memory and makes it possible to further scale the considered multi-agent system up to k agents. Conclusions. Thus, the paper proposes a new graph exploration algorithm that has quadratic (from the number of nodes of the graph) time, space and communication complexities. The number of edge transitions performed by agents-researchers is estimated as O(n), where n is the number of nodes of the investigated graph. The algorithm is based on depth-first traversal method.