Content

• Introduction
• 1. Theme urgency
• 2. Goals and tasks of the research
• 3. Research of the reconstruction algorithm graphs by collective agents
• Conclusions
• References

Introduction

Currently, robots are penetrating all spheres of human life: it is installed in entertainment establishments and manufacturing. Robots learn space. Development of robots is not standing still and is constantly being upgraded, but it is very challenging sphere. Actual problem in the software development of mobile robots is the problem of recognizing graph by collective agents.

There are many different kinds of environments that require research. Research environment is a model of interaction of the control system. Interaction models are often represented as a process of moving through the graph automaton controlled system. As a model of the working environment of mobile robots we consider finite connected undirected graph which vertices are labeled with two colors.

Exploration of the graph by single agent is described in many papers, obtained many results concerning opportunities and challenges of such recognition. However, recognition of the graph remains little studied by several agents wandering around it. This makes the actual task of recognizing graph by several mobile agents wandering around it .

1. Theme urgency

One of the central and actual problems of robotics is the problem of recognizing an unknown environment by wandering robots [3]. There are many algorithms for solving this problem. The central point in recognizing the environment is that robots can interfere with or block each other. Actual problems are algorithms discrepancies two robots, as well as passing on someone else's robot path. Thus, there is need to develop an optimal algorithms for the robot, which could have a minimum capacitance, the communication and timing complexities.

Master's work is devoted of the study and development of graph recovery algorythm by team of agents. The work is aimed at reducing the time, capacitive and communication complexity of the algorithm. The target baseline is algorithm by Igor Grunsky – Basic graph recovery algorithm by collective agents. The tools of the research are Rational Rose and Java SE [12].

Actual problem is to restore the graph, i.e.the establishment of such routes of movement of agents in unknown graph; markup elements of the graph; collection and processing of local information about the graph; ways to construct a graph on this information to the robot not blocked from being repeated and not idle. As well as problems related to the optimization of resources consumption and time spent.

2. Goals and tasks of the research

The purpose of this research is to develop an algorithm of recovery graph by team of agents with less time complexity or fewer types of labels.

The main tasks of the research: development of an improved method of recovery graphs by collective agents.

Object of research: the process of moving agents involved in undirected, connected graph without hinges and arcs, marking its elements, recovery graph to isomorphism.

Subject of research: an algorithm to restore the graph by collective agents.

Scientific novelty is the using of two colors; using two researchers and one experimenter; determine the coordinates of the vertices. Recovery is performed by traversing the graph in depth and identification of edges with incidentors (a concept defined in incidentors basic definitions), necks with a query of coordinates in which agents fall simultaneously in the process of recognition.

 

3. Research of the reconstruction algorithm graphs by collective agents

 

In the master's work the following algorithm has been developed:

Input: a finite, undirected graph G(V) without hinges and multiple edges unknown AI and AE, all the elements of the graph are colored paint 1, AI₁ and AI₂ are placed in random vertexes.

Output: all elements of the graph.

Data: v₁ and v₂ - operating vertices of G, in which agents on.

Capabilities of mobile agents AI₁ and AI₂: robots move through the graph of initial random vertices v₁ and v₂ along the edges (v₁, u₁) and (v₂, u₂) respectively. Agents can change the color of vertices v₁ and u₁, v₂ and u₂, and also their intsedentors respectively ((v₁, u₁, u₁) and ((v₂, u₂, u₂) color 2.

Being at the vertex v, the AI sees the labels of all elements with vicinity Q(v). And based on these labels determines on which edge will move and how color wil use of graph elements. AE transmits, receives and identifies the messages received from the AI. AE has a finite, infinitely increasing internal memory, which is fixed the result of functioning AI at each step and construct a graph representation of G, initially unknown to agents, lists of edges and vertices.

After a finite number of steps AI1 finish markup vertices and AE restore unknown graph up to isomorphism, i.e. recognizes graph.

Actions of agents: AI: move forward, move back, use 2 colors to determine whether there were in the vertex AI. AE: has unlimited memory, receives a message from the AI. AE requests coordinates for recognition of isthmus and identification of vertices coordinates (x_i, y_i). The satellite determines the location of AI and sends coordinates to the experimenter.

Agents are needed the paint, that they can recognize the traversed path. Paint 2 and 3 agents mark out the respective vertices that have visited and final incidentors of edge, which passed.

There is following strategy to solve this problem:

1. 1. Put agents in random vertex v1 [rand] and v2 [rand]. Transition to Step 2.

2. 2. AI1 and Au2 marks out vertices 2 color, by 2 color AI marks out their final incidentors. Transition to Step 3.

i=0; j=0;
V[i] = 2;
V(v, u) = (false, true);
V[j] = 2;
V(v, u) = (false, true);

3. Transmits information («new vertex», if the vertex was the color of 1 or «vertex», if the vertex color was not equal to 1 color). Transition to step 4.

AI1.send("new vertex");
AI2.send("new vertex");

4. AE builds vertex AE associates vertex coordinates received through satellite. Transition to step 5.

getPosition(AI1);
drawVertex(getPosition(AI1).getX(), getPosition(AI1).getY());
AE.sendAI1("Go");
getPosition(AI2);
drawVertex(getPosition(AI2).getX(), getPosition(AI2).getY());
AE.sendAI2("Go");

5. AI1 goes deep into the graph until has vertices of color 1. Otherwise starts moving back end mark incidentors, while begins the search isthmuses. Go to step 2 if there is unallocated top, otherwise step 6.

6. When AI found Isthmus, it sends the information to AE («vertex»). AE receives the message, makes a request of coordinates of AI, and connects vertices by edge: by bringing the corresponding coordinates.

7. Way back lasts as long as the AI will not come to the initial vertex. Initial vertex will be considered as a vertex that does not have untagged adjacent vertices and incidentors.

Scheme of initialization and interaction of agents researchers and agent experimenter presented in printed version of work.

1. Initialize counters.

2. AE gives the command to start the restore.

3. AI installed in different from each other casual vertexes.

4. While AI do not stop checking ..

5. If the vertex is not signposted and its final incidentors not painted, then colorize vertex and end incidentors. AI sends the message "New vertex".

6. AE receives the coordinates of found vertices, and builds it.

7. AE sends to AI "Next".

8. If the vertex is marked, but not painted end incidentors, the AI sends a message "Vertex" (i.e. not new). AE recognizes vertex coordinates in which the waste is unknown edge and connects vertex edge of the AI which came with vertex, in which went unknown edge.

9. If the vertices are labeled, and there is no colored end- incidentors, the AE sends a command to the AI "back" (to go back). Taking a step back, the AI will search again untagged edges or vertices.

10. If one of the AI came to the top and the other AI continues the way forward, the command made Swapping in untagged free vertex with 2-neighborhood.

11. If one of the AI came to the top, and the other goes back to AI, the AI completes its work.

12. If one of the AI came to the top and the other AI has completed its work, the first AI also completes its work.

 

Conclusions

 

Proposed modification to the graph recovery algorithm of undirected connected graph without hinges and multiple edges by collective agents (two agents researchers and agent experimenter).

Evaluated the complexity of the basic algorithm and the algorithm jointly with modifications. Increased communication complexity, by requiring coordinate of agents experimenter to recognize the isthmus That does't affect on the speed of the algorithm as requests of coordinate performs by experimenter which has unlimited memory.

Results shows decrease the values of the time complexity and space complexity. These results are achieved by the following modifications:

1. Choosing and pass along the edge carried per unit time. In the basic algorithm, the time complexity of O(n3) – this is O(n): AI passing forward *O(n): passing AI back *O(n): recognition of the isthmus. The algorithm with modifications has time complexity O(n) – it is synchronous forward passing of AI (i.e. AI per unit time is reduced 2 vertixes) and back. Agents do not produce returns for recognition of the isthmus due conform vertex coordinates.

2. Capacitive complexity is determined by the size of the lists vertices of color 1 and color 2. AI use 2 colors, spacing 1 color vertex and incidentors. The third color is not used because the AI returns on marked end-incidentors.

3. Communication complexity increases due to the double messaging: first AI: found – AE: next or AI: end – AE: back, and AI: found (Isthmus) – AE Position Request – AE on.

Note:

Final work is not formed yet. Final surrender papers: December 2014. Full text of the work and materials on the topic can be obtained from the author or his scientific adviser after specified date.

References

1. R. Baldoni, F. Bonnet, A. Milani, M. Raynal "Anonymous graph exploration without collision by mobile robots". Publication interne. – 2008 – 10 pages.
2. Грунский И.С., Стёпкин А.В. Распознавание конечного графа коллективом агентов. – Труды ИПММ НАН Украины. – 2009. – Т.19. – С. 43–52.
3. Стёпкин А.В. Распознавание графов коллективом агентов. // Мат. IV мiжнар. наук.-практ. конф. Сучасна iнформацiйна Україна: iнформатика, економiка, фiлософiя 2010, Донецьк, – т.1 – С. 139–143.
4. Грунский И.С., Татаринов Е.А. Алгоритм распознавания графов // Тр. 4 междунар. Конф. Параллельные вычисления и задачи управления PACO’2008, Москва, Ин-т Проблем Управления им. В.А. Трапезникова РАН, 2008 – С. 1483–1498.
5. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПБ.: БХВ – Петербург, 2003. – 1104 с.
6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.
7. Кристофидес Н. Теория графов: алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978. – 430 с.
8. Оре О. Теорія графів / Оре О. – М. : Наука, 1980. – 340 с.
9. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ. Коллективы автоматов в лабиринтах // Дискретная математика. – 2003. – Т. 15, вып. 3. – С. 3–40.
10. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. – М.: Наука, 1985. – 320 с.
11. Капитонова Ю.В. Математическая теория проектирования вычислительных систем / Ю.В. Капитонова, А.А. Летичевский. – М.: Наука, 1988. – 296 с.
12. Грунский И.С. Распознавание конечного графа блуждающим по нему агентом / И.С. Грунский, Е.А. Татаринов // Вестник Донецкого университета. Сер. А. Естественные науки. – 2009. – № 1. – С. 492–497.
13. Сапунов С.В. Неотличимость вершин помеченных графов / С.В. Сапунов // Труды ИПММ. – 2008. 189 с.
14. Грунский И.С., Сапунов С.В. Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации. – 2012. C. 422–427
15. Материал из свободной электронной библиотеки Википедия: словарь теории графов. Электронный ресурс. Режим доступа: http://ru.wikipedia.org/wiki/Глоссарий_теории_графов