All issues

Problem of exploration finite undirected graphs by a collective of agents is considered in this work. Two agents-researchers simultaneously move on graph, they read and change marks of graph elements, transfer the information to the agent-experimenter (it builds explored graph representation). It was constructed an algorithm linear (from amount of the graph’s nodes) time complexity, quadratic space complexity and communication complexity, that is equal to O(n²·log(n)). Two agents (which move on graph) need two different colors (in total three colors) for graph exploration. An algorithm is based on depth-first traversal method.

The study presented in the paper is devoted to the problem of finite graph exploration using a collective of agents. Finite non-oriented graphs without loops and multiple edges are considered in this paper. The collective of agents consists of two agents-researchers, who have a finite memory independent of the number of nodes of the graph studied by them and use two colors each (three colors are used in the aggregate) and one agentexperimental, who has a finite, unlimitedly growing internal memory. Agents-researches can simultaneously traverse the graph, read and change labels of graph elements, and also transmit the necessary information to a third agent — the agent-experimenter. An agent-experimenter is a non-moving agent in whose memory the result of the functioning of agents-researchers at each step is recorded and, also, a representation of the investigated graph (initially unknown to agents) is gradually built up with a list of edges and a list of nodes.

The work includes detail describes of the operating modes of agents-researchers with an indication of the priority of their activation. The commands exchanged between agents-researchers and an agent-experimenter during the execution of procedures are considered. Problematic situations arising in the work of agentsresearchers are also studied in detail, for example, staining a white vertex, when two agents simultaneously fall into the same node, or marking and examining the isthmus (edges connecting subgraphs examined by different agents-researchers), etc. The full algorithm of the agent-experimenter is presented with a detailed description of the processing of messages received from agents-researchers, on the basis of which a representation of the studied graph is built. In addition, a complete analysis of the time, space, and communication complexities of the constructed algorithm was performed.

The presented graph exploration algorithm has a quadratic (with respect to the number of nodes of the studied graph) time complexity, quadratic space complexity, and quadratic communication complexity. The graph exploration algorithm is based on the depth-first traversal method.

Collective behavior can serve as a mechanism of thermoregulation and play a key role in the joint survival of a group of organisms. In higher animals, such phenomena are usually the subject of study of biology since sudden transitions to collective behavior are difficult to differentiate from the psychological and social adaptation of animals. However, in this paper, we indicate several important examples when a flock of higher animals demonstrates phase transitions similar to known phenomena in liquids and gases. This issue can also be studied experimentally within the framework of synthetic systems consisting of self-propelled robots that act according to a certain given algorithm. Generalizing both of these cases, we consider the problem of phase transitions in a dense group of interacting selfpropelled agents. Within the framework of microscopic theory, we propose a mathematical model of the phenomenon, in which agents are represented as bodies interacting with each other in accordance with an effective potential of a special type, expressing the desire of agents to move in the direction of the gradient of the joint thermal field. We show that the number of agents in the group, the group power, is the control parameter of the problem. A discrete model with individual dynamics of agents reproduces most of the phenomena observed both in natural flocks of higher animals engaged in collective thermoregulation and in synthetic complex systems. A first-order phase transition is observed, which symbolizes a change in the aggregate state in a group of agents. One observes the self-assembly of the initial weakly structured mass of agents into dense quasi-crystalline structures. We demonstrate also that, with an increase in the group power, a second-order phase transition in the form of thermal convection can occur. It manifests in a sudden liquefaction of the group and a transition to vortex motion, which ensures more efficient energy consumption in the case of a synthetic system of interacting robots and the collective survival of all individuals in the case of natural animal flocks.With an increase in the group power, secondary bifurcations occur, the vortex structure in agent medium becomes more complicated.