A.M. Shirvanyan - Post-graduate Student, Junior Research Scientist, Laboratory № 3 "Logical control systems", V.A. Trapeznikov Institute of Control Sciences of RAS, Russian Academy of Sciences (Moscow). E-mail: artshirvanyan@mail.ru D.A. Tumchenok - Post-graduate Student, Junior Research Scientist, Laboratory № 3 "Logical control systems", V.A. Trapeznikov Institute of Control Sciences of RAS, Russian Academy of Sciences (Moscow). E-mail: dmitriy_tumchenok@mail.ru

When you control the robot there is a set of subtasks (localization, mapping, path construction and other). One of the subtasks of the mobile robot motion control is creating and updating obstacles map. Obstacles map is denoted as a set of points in the plane, limiting the area of space inaccessible to traffic. Quite a full robot mapping methods review was presented in [1]. Group mapping methods are traditionally divided into two categories - metric and topological. Metric mapping [2, 3] displays the environment by using the geometrical features are present in it. A topological mapping [5,6] includes information both about the location and on how to get from one point to another. Also worth noting there is another kind of display - a hybrid mapping [7, 8]. This mapping type uses the mapping metric for navigational accuracy at a local site and the topological mapping between points in space to move. The method presented in this paper relates to the first group of methods. There are different ways of mapping the obstacles. The main of them is the formation by a set of points from the board sensor, formation of vacant and occupied cells and formation by lines. The variant with a set of points has a number of drawbacks, including: occupation of most amount of memory, the work with large amounts of data, nontrivial interpretation of route planning in the already well-known map. Also it may occur a random point of the disturbance that has to be filtered. The advantage of this map type is the accuracy of data. In the case of formation a grid map the map is constructed with a specific grid cell size. Often, if you do not require solving the problem of travel in narrow places, the cell\'s size is compared with the half-width of the mobile robot. In some cases, an amount safe range can increase the cell size. A cell is considered to be impassable if it contains at least one rangefinder measurement. If the cells are large enough, the obstacles coordinates error is significant. Another way to map represents obstacles as lines. An advantage of this method is that you need to store in memory only the ends of the lines. When routing the feasibility of the route identified with the non-intersection the lines of the obstacles. It is impossible to do in the case of a map of obstacles consisting of points. This article raises several problems for the formation of a universal map of a mobile robot: filtering points (the filtering noise problem); \"compression\" of set of points to lines (the saving memory task). As a basis for modeling the \"mobile robot control\" course [12] was chosen. We are created a test map with obstacles for the experiments. It is depicted in the figure below. In the center of the figure is a robot, it is his starting position. The cross in the top right corner is the goal of the movement. It is believed that the robot does not know anything about the location of obstacles before the movement. The robot gets an information from infrared rangefinders in real time. The Kalman filter has been implemented to obtain more data that are reliable and smooths the boundaries. Where we have done a series of experiments with different parameters of the algorithm. We calculated the total accu-mulated error. The following results were obtained after a series of experiments (the total number of points obtained from the sensors is equal to 642): before the filtration: the total accumulated error was 3957 mm. Thus, the deviation of the points from the boundaries of obstacles averaged 6 mm (2% of the range of the sensor); after the filtration: the total accumulated error decreased to 2758 mm. Thus, the average deviation was reduced to 4 mm (1.5% range of the sensor); after the algorithm: the total accumulated error in the best case is 1278 mm. Thus, the average error is decreased and amounted to 2 mm (1% of the sensor range); after repeat the algorithm: the total accumulated error in the best case was 1923 mm. Thus, the average error is in-creased. It follows that the error deviation obtained from actual boundaries decreases after application of the method. Another advantage of the algorithm is reducing the number of stored points. So initially, the boundaries of obstacles are obtained at 642 points (before and after filtration) in this experiment. After we applied the algorithm, and boundaries of obstacles are based on 156 lines (158 points). It takes 4 times less memory. The number of lines became 57 (59 points) after repeat the algorithm that has 3 times less. But in this case, the accuracy is lost. Therefore, whether to apply the algorithm again or not, everyone has to decide for itself. In this article, we proposed algorithm for creating maps of obstacles in the line form in real time. A series of experiments on the test maps in the environment Matlab Simulink were performed. The experiments have shown that the parameters of the algorithm differ depending on the sensor accuracy, the number of points and form of obstacles. Usually, the accuracy of determining the boundaries of the obstacles is improved by 2-3 times, and the number of points that are stored in the memory is reduced in 4-7 times after the application of the proposed algorithm. A big advantage of the method is that the amount of stored points always known - it is the number of line pieces multiplied by two. Robot to be used in enclosed spaces in which the boundaries of most of the obstacles are straight lines.

 

1. Thrun S. Robotic mapping: A survey // Exploring Artificial Intelligence in the New Millenium. Morgan Kaufmann.2002.
2. Chatila R., Laumond J.P. Position referencing and consistent world modeling for mobile robots // IEEE International Conference on Robotics and Automation. 1985.
3. Arras K.O. Feature-based robot navigation in known and unknown environments: Ph.D. Thesis, Swiss Federal Institute of Technology Lausanne (EPFL). Thesis number 2765.2003.
4. Martinelli A., Svensson A., Tomatis N., Siegwart R. SLAM based on quantities invariant of the robot-s configuration // In: IFAC Symposium on Intelligent Autonomous Vehicles. 2004.
5. Choset H., Nagatani K. Topological simultaneous localization and mapping (SLAM): Toward exact localization without explicit localization // IEEE Transactions on Robotics and Automation. 2001. № 17.R. 125-137.
6. Tapus A. Topological SLAM - Simultaneous localization and mapping with fingerprints of places: Ph.D. Thesis. Swiss Federal Institute of Technology Lausanne (EPFL).2005.Thesis Number 3357.
7. Thrun S. Learning metric-topological maps for indoor mobile robot navigation // Artificial Intelligence 99. 1998.№ 1.R. 21-71.
8. Tomatis N., Nourbakhsh I., Siegwart R. Hybrid simultaneous localization and map building: A natural integration of topological and metric // Robotics and Autonomous Systems. 2003. № 44. R.3-14.
9. Ogandzhanjan S.B., Rozhnov A.V., Burmistrov P.A., Lobanov I.A., Tjurin S.A. Tvorcheskie materialy «kruglogo stola». CH. I. Retrospektiva i realnaja konkordancija issledovanijj v sfere intellekta // Nejjrokompjutery: razrabotka, primenenie. 2016. № 1. S. 17-29.
10. Rozhnov A.V. Tvorcheskie materialy «kruglogo stola». CH. II. Sistemnaja integracija i modelirovanie novykh ehffektov v sfere intellekta // Nejjrokompjutery: razrabotka, primenenie. 2016. № 3. S. 3-12.
11. Baryshev P.F., Rozhnov A.V., Gubin A.N., Lobanov I.A. Obosnovanie informacionno-analiticheskojj sistemy v razvitii metodov i modelejj soglasovanija ierarkhicheskikh reshenijj // Dinamika slozhnykh sistem - XXIvek. 2014. № 3. S. 43-52.
12. Rozhnov A.V. Nekotorye problemnye voprosy sistemnojj integracii napravlenijj nauchnojj dejatelnosti v zadachakh nejjrokompjutinga // Nejjrokompjutery: razrabotka, primenenie. 2014. № 1. S. 3-9.
13. Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics // IEEE Transactions on. 1968. № 4 (2). R.100-107.
14. Likhachev M., Stentz A. R* Search. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. Menlo Park.Calif.2008
15. Turner A., Doxa M., O\'sullivan D., Penn A. From isovists to visibility graphs: a methodology for the analysis of architectural space. Environ Plann B.Pion Ltd.2001. V. 28.
16. Ott G. Metody podavlenija shumov i pomekh v ehlektronnykh sistemakh. M.: Mir. 1979. 318 s.
17. Control of mobile robots. Availible at: https://ru.coursera.org/course/conrob.html (dataobrashhenija: 02.11.2015).
18. Ambarcumjan A.A., Potekhin A.I. Gruppovoe upravlenie v diskretno-sobytijjnykh sistemakh // Problemy upravlenija. 2012. № 5. S. 46-53.
19. Ambarcumjan A.A.Supervizornoe upravlenie strukturirovannymi dinamicheskimi diskretno-sobytijjnymi sistemami // Avtomatika i telemekhanika. 2009. № 8. S. 156-176.
20. Potekhin A.I., Branishtov S.A., Kuznetsov S.K. Discrete-Event Models of a Railway Network // Automation and Remote Control. 2015. V. 72.№8. S. 345-356.