Abstract
Table of contents
- Introduction
- 1. Basic tasks of research
- 2. Method of the environment and the map comparison by a mobile agent
- Conclusion
- References
Introduction
The basic problem of theoretical cybernetics is the cooperation of the sensor-based and the guided systems (control automat and his operating environment). The interaction of an automaton and its environments is usually represented as movement of automaton on a labeled graph or labyrinth. Automaton reads labels of the current vertex and its neighborhood and can move along the edges of the graph from vertex to vertex, change label of the vertex or add new labels [1–4].
The central problem in research of the automata and graphs interaction is the problem of graph properties analysis with different a priori information and different interaction processes of graph and automaton. This problem arises in the navigation of mobile robots using topological maps of the environment. Robot environment is modeled by a finite undirected graph with labeled vertices. The agent is assumed to have neither compass nor other instruments for measuring orientation or distance. The exploration algorithm allows the robot to form a model of its world by exploring the world systematically with the use of one or more distinct markers (flags) that can be dropped and picked up at will. These markers can be recognized if they are found on the path of the robot. The exploration algorithm works by incrementally expanding a known sub graph of the world by exploring unknown edges incident with it. Several methods for this problem have been proposed in the literature, but there no optimal method (or tend to optimal) for the mobile robot self location problem on topological environment [5–7].
The purpose
The purpose of the master's degree work is to develop an optimal method for the problem of verifying that a given input map is a correct description of the world by an active agent.
1. Basic tasks of research
1. To study a map as an environment of agent.
2. To consider examples of the existent topological maps.
3. To study basic definitions and denotations of the graph theory.
4. To consider the known algorithms for robot self location and map validation problems.
5. To develop a new method for comparison of a map and an environment.
Research object: map and environment validation by an agent.
Subject of investigation: unknown environment validation with labeling traversed vertices and edges on the map by an agent.
2. Method of the environment and the map comparison by a mobile agent
Input: undirected connected graphs G1 and G2 with unlabeled vertices and edges (labeled with white color).
Output: graphs are isomorphic or not.
Method: simultaneous motion in G1 and G2 on white or green edges over white or red vertices while there are non-black vertices in the graph.
1. An agent begins the analysis of a vertex v;
2. If a few edges is incident to the vertex v, an agent puts in the v red flag and moves to the new adjacent vertex, painting the edge between vertices with green color;
3. An agent on the map G2 marks vertices and edges by the same colors and flags, as on environment G2;
4. An agent compares the past vertices and edges in the map G2 with the passed vertices and edges in the environment G1;
5. If the explored area of map G2 coincides with the explored area of environment G1 and there are non-passed vertices and edges on the map, go to step 1;
6. If the explored area of map G2 coincides with the explored area of environment G1 and there are no non-passed vertices and edges then G2 is isomorphic to G1, go to step 10;
7. Otherwise G1 is not isomorphic to G2, go to step 10;
8. If the number of edges of q incident to the vertex v is equal to 1 than agent puts the black flag and moves to an adjacent vertex, painting the edge with green color:
8.1 If an adjacent vertex has the black flag, go to step 3, and then go to step 5;
8.2 Otherwise go to step 3, and then go to step 5;
9. If number of edges q, incident to the vertex v is equal to 2 than
9.1 If in the vertex v of the environment G1 there is an incident green edge and a black flag on one of the adjacent vertices, an agent puts on the vertex v the black flag and passes to the adjacent vertex (marked a white paint, or red flag);
9.2 Go to step 3-4;
9.3 If in the vertex v of the environment G1 all incident edges are green and there are black flags on both adjacent vertices then in the vertex v agent puts a black flag;
9.4 Go to step 3, and then go to step 6;
9.5 If in the vertex v of the environment G1 all incident edges are white then adjacent vertex with red flag is selected;
9.6 Otherwise, white vertex is selected, go to step 1;
9.7 If the adjacent vertex is with the black flag, go to step 6;
10. End of algorithm.
Work of algorithm is presented on a picture 6.1
Figure 6.1 – Algorithm of comparison of the environment and set map a mobile agent
(animation: 6 frames, 3 cycles of repeating, 99 kilobytes)
(1 – environment of study of agent, 2 – map of agent)
Conclusion
In the present work a map as an environment of agent is studied; examples of the existent topological maps are considered; several known algorithms for map validation are examined; the new method of the map and the environment comparison is developed.
References
- Сапунов С. В. Диссертация на соискание научной степени кандидата физико-математических наук: Анализ графов с помеченными вершинами / Сапунов С. В. – Донецк, 2007. – 180 с.
- Кудрявцев В. Б. Введение в теорию автоматов / Кудрявцев В. Б. – М. : Наука, 1985. – 320 с.
- Глушков В. М. Теория дискретных преобразователей / Глушков В. М. – Новосибирск: Наука, 1973. – 100 с.
- Макконелл Д. Анализ алгоритмов. Вводный курс / Макконелл Д. – М. : Техносфера, 2002. – 304 с.
- Олейник Р.И. О контроле автоматных лабиринтов конечным автоматом // Труды ИМПММ НАНУ. – 2000. – Т. 5. – С. 107–114.
- Dudek G. Map validation and Robot Self-Location in a Graph-Like World / Dudek G // Robotics and Autonomous Systems. – 1997. – Vol. 22, №2. – P. 159–178.
- Dudek G., Jenkin M. Computational Principles of Mobile Robotics. / Dudek G., Jenkin M. // Robotics and Autonomous Systems. – 2000. – Cambridg. – P. 159–178.