DonNTU   Masters' portal

Abstract

Content

Introduction

The most common problem of all mobile devices, moving temselves without without human help, remains Navigation. In connection with tryes to create standalone a means of rolling or agent arises a number of problems titled as "navygation problems" [1].Navigation is the science (or art) of directing the course of a mobile robot as it traverses the environment. Inherent in any navigation scheme is the desire to reach a destination without getting lost or crashing into any objects.

Traditionally, the task of navigating includes two sub-problems, which can be separated in time: the localization in space and route planning. Localization is to assess the current position of work on some well-known strongholds of protection specified in absolute coordinates.

The algorithms involve the global planning information about all the space to determine the areas in which motion is possible, and then select the optimal path. For a planning problem are the exact algorithmic solutions. However, the exact algorithms have a large computational complexity and moreover, require accurate algebraic models of interference. Heuristic methods do not guarantee the completeness of the search and global optimality even in the planning, when all the information available about the environment. However, the heuristic global planning methods reduce the complexity of the problem and the sensitivity to errors in the data in different ways.

Using genetic algorithms can find the best route taking into account the minimum travel time to various scenarios of real traffic conditions and different speeds of the vehicle.

1. Theme urgency

Mobile robotic systems are used today in many different industries. Corporate customers are interested in multi-functional industrial robots, the mass becomes an active buyer of intellectual vacuum cleaners and robotic dogs, security and rescue rely on stand-alone devices that can tirelessly perform tasks of tracking and searching [2-3]. Moreover, all such devices should ideally be confidently navigate in unfamiliar and unpredictable environment of the real world.

The urgency of the autonomous mobile agents development persists and grows, it is enough to recall the necessity of using such devices in emergency situations, in terms of environmental disasters, with deep studies in the works in various urban and industrial communications. A new upsurge of interest in the structure of autonomous agents, called plans for a European Space Agency and NASA (with Russia), the study of planets in the solar system stand-alone devices.

2. Goal and tasks of the research

The goal and tasks of the research is to implement a navigation system using genetic algorithms to solve the navigatoin problem of path plainning in a mobile robot enviroment.

Research object: genetic algorithms application for autonomous robot path planning solving task.

Research subject: evolutionary algorithm for autonomous robot path planning navigator implementation.

Main tasks of the research:

  1. It is necessary to investigate the following objectives for the genetic navigator development :
    • how to plan mobile robot paths;
    • algorithms for obstacle avoidance;
    • ways of the environment representing .
  2. To solve the key problems of the algorithm evolution navigator, as the selection of anchor points.
  3. To optimize the genetic algorithm must be selected:
    • operators to modify it;
    • to compare the performance of genetic algorithms;
    • to select an efficient variant of the genetic algorithm.

3. The general problem of mobile robot path planning

An integral part of any navigation system is the desire to reach their destination and does not get lost or run into any of the objects [4]. There may be other restrictions on a particular route, for example, the speed limit or zone of uncertainty, where theoretically, of course, you can get directions, but it is not desirable.

Often the way in which the robot must move forward, we plan independently,based on previous input and without obstacles in real time [5-6]. It can be effectively, but only if the environment is completely known and unchanged, and the robot can pass on the good path. But in the real world conditions it becomes more complicated.

However, the limitations of off-Iine planning led researchers to study planning in real time (the on-line planning).This method relies on the knowledge gained from probing the local environment for the processing of unknown obstacles, according to how the robot goes your way in a real environment.

3.1. Evolution algorithms usingin for navigation tasks.

Evolutionary Navigator (thereafter EN) should be a system of genetic algorithm that combines both offline and online planning with a simple map of high accuracy and efficient scheduling algorithm. The first part of the algorithm (off-line planner) searches an optimal global path from the starting point to destination, while the second part (on-line planner) is responsible for handling potential conflicts or circumvention of previously unknown objects, replacing part of the planned globally optimal path in the auxiliary path[7]. I'd like to admit that both parts of the ES share the same evolutionary algorithm, but with different values ??of various parameters.

Nowdays, different researchers have experimented with different methods of evolutionary computation for path planning problem [8]. For example, Davidor uses dynamic structure of chromosomes and the crossover operator to optimize certain processes in the real world (including developing ways of planning applications) [9]. Others describes a genetic algorithm for the problem of route planning, and presented a genetic algorithm to develop a real-time multi-heuristic search strategies [10-11]. Both approaches involve the use of certain cards, sostotyaschey of the key points. Other researchers have used a classifier system or genetic programming paradigm approached the problem of route planning [12-13].

3.2.Genetic algorithms selectoin for future evolution navigstor realisation.

I choose the evolutionary algorithm proposed in the article Zbignieva Mikhalevich «Path planning in a mobile robot environment» described below for the basis of the evolutionary navigator creation [14]. This method is unique in the sense that the evolutionary navigator runs on all the free space and does not make any a priori assumptions about acceptable ways of nodes, and it combines with offline and online scheduling.

To begin with I'd like to consider the map structure. In оrdеr to support path search in the entire, сопtiпuоus free space vertex graphs are used to represent objects in the environment. we limit the environment to get the two-dimensional representation of the area of ??objects. Thus, the robot can be represented by a point, while the objects in the environment can "grow" the scale, respectively. We assume that the mobile robot is equipped with sensors to scan the environment [15]. Notable items are ordered list (clockwise) of its vertices. Online there are unknown obstacles and modeled pieces of "wall", where each piece of the "wall", and is a straightforward list of its vertices with two endpoints. This view is consistent with the known objects in real time the robot completes the information about the map of the environment, but only partial information about unknown obstacles can be obtained by probing at a specific location. Finally, all media is defined as a rectangular area (map).

Now it is important to identify ways generated by EN. The path consists of one or more line segments, from the starting position, goals, and perhaps the intersection of two adjacent segments – the node. Feasible path has only possible nodes, the infeasiblthe path is the one that contains at least one impossible node.

Let's suppose there exists a path p = (m1, m2, ..., mn) (n> = 2), where m1 and mn denote the start and end nodes, respectively. Node (i = 1, ..., n-1) is invalid if it is infeasiblthe or can not be combined with a subsequent node mi over obstacles, or it is inside (or very close to) the obstacle. We assume that the initial and final nodes are outside the barriers, and are not too close to them [16].

However, it should be noted that the original site does not necessarily have to be possible (if it is not possible to pass to the next node), whereas the target node (point) is always possible. Also note that different paths can have different number of nodes.

3.3.The description of evolution navigstor algorithm.

The evolutionary algorithm, which will be described here is an evolutionary navigator that combines offline and online mode with a simple planning high accuracy map and efficient scheduling algorithm [17].

The first part of the algorithm (offline planner) searches a globall optimal path from start to destination, and the second part (on-line planner) is responsible for handling potential conflicts or previously unknown objects, replacing part of the original path to the global optimum subput. It is important to note that both parts of the ES share the same evolutionary algorithm, but with different values ??of various parameters.

The EN reads the map and receives the initial and target location. Then the off-line genetic algorithm (FEG) produces near-optimal global path is partially straight path consisting of admissible nodal points or nodes. Figure 1 shows the evolutionary algorithm.

Навигатор

Figure 1 - Evolutionary navigator show

(animation: 12 frames, 10 circuses of repetition, 30 kb)

If the robot moves too close to the object surrounding the object, on-line genetic algorithm (NEG) makes virtually "grow" the representation of the object on the map and alienates the local path of the object that is as straightforward as was previously planned to construct the path algorithm FEG. The robot then moves along a successful path to the current node should be designed.

Conclusion

In connection with attempts to create autonomous moving vehicle or mobile agents, a number of issues united by a common name - "navigational problems". It is, primarily, on the motion of the earth's surface, although the obtained results in this area have been successfully used during the motion of underwater vehicles and missile guidance, and have been successful in developing computer games.

The global planning algorithms involve the information about all the space to determine the areas in which motion is possible, and then select the optimal path. While scheduling heuristics reduce the complexity of the problem and the data errors sensitivity in different ways. Therefore,evolutionary navigator algorithm has been selected to develop a universal navigation system for autonomous robot.

.

The choice of this algorithm makes it possible to consider a set of behaviors and aspects of the robot's environment at the planning stage of the way. However, the key problem remains the definition of the algorithm selected nodal points. The solution to this problem is the basis for further research

This master's work is not completed yet. Final completion: December 2011. The full text of the work and materials on the topic can be obtained from the author or his head after this date.

References

  1. Лысенко О. Использование лазерных сканеров SICK AG для навигации мобильных роботов /Олег Лысенко / материалы из журнала «Компоненты и технологии» № 1 '2008 [Электронный ресурс]. – Режим доступа:http://www.kit-e.ru/articles/sensor/2008_01_56.php
  2. Черноножкин В.А. Система локальной навигации для наземных мобильных роботов/ Черноножкин В.А., Половко С.А./ Центральный научно-исследовательский и опытно-конструкторский институт робототехники и технической кибернетики – Режим доступа к материалам: http://144.206.159.178/ft/9344/538978/11790042.pdf
  3. Бобровский С.Навигация мобильных роботов/Сергей Бобровский/ PC Week/RE («Компьютерная неделя») / [Электронный ресурс]. – Режим доступа: http://www.pcweek.ru/themes/detail.php?ID=66917
  4. Стоут Б.. Алгоритмы поиска пути/ Браян Стоут[Электронный ресурс].– Режим доступа: http://pmg.org.ru/ai/index.html
  5. Sharon Laubach. Sensor-based Autonomous Navigation for Mars Rover/ Sharon Laubach, Joel Burdick. Larry Matthies[Электронный ресурс]. – Режим доступа: http://robotics.caltech.edu/~jwb/ERC/rover/rover_detailed.html
  6. Latombe J. C. Robot Motion Planning/J-C Latombe.– Kluwer Academic Publishers: 1991.
  7. Jean-Yves Bouguet. Visual Navigation using a single camera. – [Електронний ресурс]/ Jean-Yves Bouguet, Pietro Perona. – Режим доступа:http://www.vision.caltech.edu/bouguetj/
  8. Lozano-Perz T. An Algorithm of Planning Colisions Free Paths among Polyhedral Abstracts/ T. Lozano-Perz. – ACM,1984. p 560-570.
  9. Davidor Y. Genetic Algoritms and Robotics./ Y. Davidor. – World Scientific, 1991
  10. Sibata T. Robot Motion Planning by Genetic Algoritms with Fuzzy Logics/ T. Sibata, T. Fukuda. – ISIC, 1993.
  11. Shing M.T. Genetic Algoritms for the Development of Real-Time Multi-Historic Search Strategies/ M.T Shing, G.B. Parker. – 1993. 570 p.
  12. Zhou H.H. Learning by Analogy in Genetic Classifier Systems/Zhou H.H. – CA, 1994. 550 p.
  13. Handly S. The Genetic Planner/ S. Handly. – ISIC,1993.
  14. Zbigniev Michailevich. Genetic Algoritms plus Data Structures equal Evolution Programs/ Zbigniev Michailevich.– Springer, 1999. – 387 c.
  15. Курейчик В. М. Поисковая адаптация: теория и практика/ Курейчик В. М., Лебедев Б. К., Лебедев О. К. – М: Физматлит, 2006. – 272 c.
  16. Samejima K. Adaptive internal state space construction method for reinforcement learning of a real-world agent/ K.Samejima, T. Omori. – Neural Networks, 1999
  17. Курейчик В.М. Генетические алгоритмы и их применение/В.М.Курейчик .– Таганрог: ТРТУ, 2002
  18. Плотников В.А. Анализ эффективности существующих методов уклонения от столкновения для мобильного робота / Плотников В.А. – Донецк: Штучний інтелект – 2010.
  19. Ольшевский А.И. Решение задачи Штейна при помощи генетического алгоритма /Ольшевский А.И., Починский М.Ю. : Бионика интеллекта –2008.
  20. Емельянов В.В. Теория и практика эволюционного моделирования/ В. В.Емельянов, В. В. Курейчик В. В., В. М. Курейчик. – М: Физматлит, 2003. – 432 c.