Українська   Русский

Abstract

Contents

Introduction

At the present time in the world there is a huge number of different kinds of environments that need to be studied (starting with the study of the environment with the help of nanobots and ending with the study of the surfaces of distant planets with the help of planet-walkers). This is one of the reasons for the active development of such a direction of mathematical cybernetics as the theory of discrete dynamical systems. The study of the environment is a kind of discrete system, represented as a model of interaction between a control and control system (control automaton and operating environment), the interaction of which is often represented as the process of moving the control automaton through the graph of the controlled system.

When nothing is known about the graph, the task can be compared to traversing a labyrinth by a person or a device inside it and not having a labyrinth plan. The arc of the graph corresponds to the corridor of the labyrinth, and to the top - the intersection. While at the intersection, we see the corridors coming out of it, but we do not know where the corridor leads to, until they passed through it to the next intersection. To fulfill our task, we first have some internal memory (a notebook in the hands of a person), where we can record the information obtained about the passed part of the labyrinth, and, secondly, make notes in the crossroads and corridors passed. The oriented graph corresponds to a labyrinth in which all corridors are "one-way". If the internal memory is limited to a finite number of states, we have a robot (finite state machine) on the graph as a kind of Turing machine [1].

1. Theme urgency.

In the field of information technology, the task of graph research can be applied to verification and testing of software and hardware systems, as well as research of networks, including Internet networks and GRID based on formal models. The model of a system or network, ultimately, reduces to a transition graph, the properties of which need to be investigated. In recent years, the size of the really used systems and networks and, consequently, the size of their models and, consequently, the size of the graphs being researched, is continuously growing. Problems arise when the study of a graph by one automaton (computer) either requires an unacceptably long time, or the graph does not fit in the memory of one computer, or both. Therefore, the problem of parallel and distributed study of graphs arises. This problem is formalized as the task of investigating a graph by a team of automata (several computers running concurrently with sufficient total memory) [ 2 ].

In this master's work, the analysis and development of the algorithm for investigating the graph by several agents is carried out in order to minimize its capacitive and time complexity.

Under capacitive complexity, we mean the amount of memory used by the algorithm, and the number of times the agents are moved along the arcs of the graph.

2. Purpose and objectives of the study, planned results

The aim of the research is to develop an algorithm for investigating a graph by a team of agents with less time complexity or less memory usage than existing algorithms

The main objectives of the study:

  1. Study the basic concepts and notation of graph theory.
  2. Analyze ways to reduce the complexity of the algorithm.
  3. Learn how to restore the graph.
  4. Development of an improved method for recognizing the graph.

3. Basic definitions

For a better understanding of the subject domain, consider its main concepts.

Graph theory is a section of discrete mathematics that studies the properties of graphs. In general, a graph is represented as a set of vertices (nodes) connected by edges. In a strict definition, a graph is a pair of sets. G = (V, E), where V is a subset of any countable set, and E is a subset of VxV.

Example graph

Figure 1 - Example of a graph with five vertices and six edges

The incident is the junction of the vertex and the edge (usually used by the pair - incidentor from the initial vertex and incidence at the final vertex).

The incidence matrix is one of the forms of the graph representation, in which the connections between the incident elements of the graph (edge (arc) and vertex) are indicated. The columns of the matrix correspond to the edges, the rows to the vertices. A nonzero value in the cell of the matrix indicates the relationship between the vertex and the edge (their incidence). In the case of an oriented graph, each arc is associated with "-1" in the row of the vertex x and the arc column and "1" in the row of the vertex y and the arc column; if there is no connection between the vertex and the edge, the corresponding cell is set to "0".

The incident is the place where the vertex and the edge are joined.

A team of agents is a collection of agents investigating a graph.

The agent is an agent-agent who walks around the environment and marks the vertices, simultaneously transmitting information to the experimenter.

The agent is an experimenter - an agent that restores a graph based on data transmitted by agents to researchers.

Search in depth - one of the methods of traversing the graph. The strategy of searching in depth, as the name implies, is to go deeper into the graph, as far as possible. The search algorithm is described recursively: we go through all the outgoing edges from the considered vertex. If an edge leads to a vertex that was not considered earlier, then we start the algorithm from this unexamined vertex, and then return and continue to sort out the edges.

The order of passing the vertices of the graph in depth

Figure 2 - The order of passing the vertices of the graph to the depth of
(animation: 10 frames, 10 repetitions, 7 kilobytes)

Isomorphism of a graph. In graph theory, a bijection between sets of vertices of graphs f: VG → VH is called an isomorphism of graphs G = (VG, EG) and H = (VH, EH) such that any two vertices u and v of G are adjacent if and only if vertices f (u) and f (v) are adjacent in the graph H. Here the graphs are understood to be undirected and have no weights of vertices and edges. If the notion of isomorphism is applied to oriented or weighted graphs, additional restrictions are imposed on preserving the orientation of the arcs and the values of the weights. If an isomorphism of graphs is established, they are said to be isomorphic and are denoted by G≈H.

Example of isomorphic graphs

Figure 3 - Example of isomorphic graphs

Isthmus is the apex in which agents meet researchers.

The adjacency matrix is a square matrix A of size n, in which the value of the element aij is equal to the number of edges from the ith vertex of the graph to the jth vertex.

A loop is an edge whose beginning and end are at the same vertex.

Hanging vertex - the vertex is called hanging if it has a power of one [10].

4. Review of research and development on the topic

4.1 Overview of international sources

The problem of examining the graph by a finite robot was posed by M.O. Rabin back in the distant 1967.

In 1978, K. Kobayashi presented an article describing a stopping algorithm for traversing exponential complexity based on the idea of DFS [ 11 ]. In 1988, S. Kutten [12] proposed an algorithm for traversing the minimum complexity O (nm), but his robot was not finite, since he used the cells of a graph with a logarithmic vertices) by the number of memory bits. In 1993, Y.Afek and E. Gafni [ 13 ] offered the final robot A (which they called Traversal-3), based on depth-first search (DFS), with an estimate of the length of the traversal O (nm + n2 logn). According to their method, the label is placed on all 4 vertices of the out-path, except for its end, and the parity of the number of marked vertices is determined. The next pass removes the labels from the vertices of the opposite parity and re-determines the parity of the number of vertices that have been labeled, and so on, until there is one vertex left - the next-to-last vertex of the out-path. Due to this "parity method" O (logn) passages are sufficient instead of O (n) passages.

4.2 Overview of national sources

I. Burdonov, A. Kosachev are engaged in the research of the graph. They pay attention to the study of oriented graphs by automata [1-5]. Their work often refers to the application of graph studies by automata in system testing. So they compare the system to be tested with the graph, and the automata in it under arc transitions have a test effect on it.

4.3 Overview of local sources

In the works of I. Grunsky , A. Stepkin, E. Tatarinov methods of recognizing the graph by one agent and the team of agents are considered [6-9].

Consider the method of recognizing the graph by three agents, proposed by I. Grunsky and A. Stepkin. This method involves the use of two agent-researchers and one agent-experimenter. Agents-researchers can move along a graph from one vertex to another through connecting ribs, while they can change the color of vertices, edges and incidents. Being in a certain vertex of the graph AI can learn information about the labels on the elements in the vicinity of a given vertex and on the basis of this information make decisions about the further movement and coloring of the graph elements. The experimenter agent can receive and transmit messages from the AI. The AE has a finite constantly growing memory, in which it stores the results of all AI actions at each step and gradually builds a map of the investigated graph, previously unknown.

This algorithm is based on a depth-first search strategy. This means that the agents will go "deep" to the graph as long as possible, then go back and continue to search for paths with as yet unexcept visited vertices and not traversed edges. In case of finding an adjacent vertex that is colored by another AI on its way, it is necessary to mark all the isthmus leading to someone else's area and inform the other AI through the experimenter's agent about the need to return and recognize all marked isthmuses, and information on their number is also transmitted. The selection of the further movement for the first AI from this point is changed until the second agent recognizes all the marked isthmus. If there are no options to move, the agent will wait on the spot before the second agent recognizes all the isthmuses.

There are many known depth-search algorithms for a known graph. The same method works with an unknown graph for agents. Each agent at the first visit of the top color it in its color and puts her number corresponding to the counter of the agent's vertices. In this case, the first agent is numbered only by odd numbers, and the second is even. On the basis of this numbering of vertices, the graph is reconstructed by constructing another graph isomorphic to it. In the process of research, agents build implicit trees in search of depth, colored by a certain color. Concerning these trees, all the ribs are divided into their own (colored AI), not belonging to the trees (backward), their agents color black on the first pass through them, and the isthmus that connects the trees. The edges belonging to the trees are traversed at least twice and at the last transition are painted black, the reverse ones are traversed 1 time, and the isthmus is twice by each agent, the first agent that passes it marks with its own color. The second agent who crosses it, recognizes the isthmus and paints it in black.

Agents recognize woody ribs on first visit. Woody paths lengthen when you move to a new vertex and shorten when you go back. The vertex in which all the incident ribs are recognized is painted in black. When the graph does not leave the vertices that are not black, the algorithm finishes its work.

The process of recognizing a graph consists of two different algorithms: traversal (described above) and recovery. The second algorithm is performed by the experimenter and, as a result, gets the graph isomorphic to the given one. It should be noted that the algorithms work as follows: first the first agent walks, the AE records its actions, then the second agent walks and the AE writes down his actions [6].

Conclusions

Currently, one of the central areas of cybernetics is the recognition of an unknown medium, given by the graph. This paper is devoted to solving the problem of recognition by several agents of a medium given by a finite undirected graph.

In the course of the work, the features of the domain were analyzed. The method of recognition of the final graph by two agents, proposed by A.V. Stretching.

The temporary complexity of this recognition algorithm is O (n), capacitive - O n2, and communication - O n2 * log (n). The algorithm uses 3 colors.

References

  1. Бурдонов И.Б. Обход неизвестного ориентированного графа конечным роботом / И.Б. Бурдонов // Программирование, 2004 г., № 4, с. 11-34.
  2. Бурдонов И.Б., Косачев А.С. Обход неизвестного графа коллективом автоматов / И.Б. Бурдонов, А.С. Косачев // Труды Института системного программирования РАН, том 26, вып. 2, 2014, стр. 43-86.
  3. Бурдонов И.Б. Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом / И.Б. Бурдонов, А.С. Косачев // Программирование, 2004 г., № 6, с. 6-29.
  4. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Неизбыточные алгоритмы обхода ориентированных графов. Недетерминированный случай / И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин // Программирование, 2004 г., №1, с. 2-17.
  5. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай / И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин // Программирование, 2003 г., №5, с. 59-69.
  6. Грунский И.С., Стёпкин А.В. Распознавание конечного графа коллективом агентов. – Труды ИПММ НАН Украины. – 2009. – Т.19. – С. 43–52.
  7. Стёпкин А.В. Распознавание графов коллективом агентов / А.В. Стёпкин // Мат. IV мiжнар. наук.-практ. конф. Сучасна iнформацiйна Україна: iнформатика, економiка, фiлософiя 2010, Донецьк, – т.1 – С. 139–143.
  8. Грунский И.С., Татаринов Е.А. Алгоритм распознавания графов / И.С. Грунский, Е.А. Татаринов // Тр. 4 междунар. Конф. Параллельные вычисления и задачи управления PACO’2008, Москва, Ин-т Проблем Управления им. В.А. Трапезникова РАН, 2008 – С. 1483–1498.
  9. Грунский И.С. Распознавание конечного графа блуждающим по нему агентом / И.С. Грунский, Е.А. Татаринов // Вестник Донецкого университета. Сер. А. Естественные науки. – 2009. – № 1. – С. 492–497.
  10. Материал из свободной электронной библиотеки Википедия: словарь теории графов. Электронный ресурс. Режим доступа: http://ru.wikipedia.org/wiki/Глоссарий_теории_графов
  11. Kobayashi K. The firing squad synchronization problem for a class of polyautomata networks / K. Kobayashi // Journal of Computer and System Science, 17:300-318, 1978.
  12. Kutten S. Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks / S. Kutten // In J. Raviv, editor, Proceedings of the Ninth Internationak Conference on Computer Communication, pages 446-452, October 1988.
  13. Afek Y., Gafni E., Distributed Algorithms for Unidirectional Networks / Y. Afek, E. Gafni // SIAM J. Comput., Vol. 23, No. 6, 1994, pp. 1152-1178.