Systems and Means of Informatics
2018, Volume 28, Issue 4, pp 10-21
ENCLOSED ROOM EXPLORATION ALGORITHM FOR AN AUTONOMOUS MOBILE ROBOT
- O. Arkhipov
- A. Gasilov
- Yu. Maniakov
- O. Yakovlev
Abstract
An enclosed room exploration algorithm for an autonomous mobile robot equipped with sensors is introduced. This paper includes the definition of the task of enclosed room exploration. The algorithm utilizes the data model of a floorplan, based on a concave polygon with holes, which is refined and enhanced by merging different views of the room in the iterative manner during exploration. This representation allows formulating the termination criterion that can be checked in constant time and constructing a graph for pathfinding and obstacle avoidance purposes. In addition, analysis of algorithm's computational complexity and results of a test based on synthetic datasets are provided. Furthermore, an approach to exploration path building and an algorithm of floorplan's polygons union are considered.
[+] References (6)
- Siegwart, R., and I.R. Nourbakhsh. 2004. Introduction to autonomous mobile robots. Cambridge, MA: MIT Press. 321 p.
- Davydov, O.I., andA.K. Platonov. 2015. Set' Passfreymov - kombinirovannaya model' operatsionnoy sredy mobil'nogo robota [Passframe Network - combined operating environment model for a mobile robot]. Preprinty IPM im. M. V. Keldysha [Keldysh Institute preprints]. 28 p. Available at: http://library.keldysh.ru/preprint.asp?id=2015- 15 (accessed July 31, 2018).
- Yakovlev, O. A. 2018. Metody initsializatsii voksel'nogo ob'ema v zadache trekhmernoy rekonstruktsii [Initial bounding box estimation methods for volumetric three-dimensional reconstruction]. Sistemy i Sredstva Informatiki - Systems and Means of Informatics 28(1):53-64.
- Chentsov, O. V., and A. V. Skvortsov. 2003. Obzor algoritmov postroeniya overleev mnogougol'nikov [A review of the algorithms of polygon overlays design]. Tomsk State University J. 280:338-345.
- Skvortsov, A. V. 2002. Postroenie ob"edineniya, peresecheniya i raznosti proizvol'nykh mnogougol'nikov v srednem za lineynoe vremya s pomoshch'yu triangulyatsii [An algorithm for constructing the union, intersection, and difference of arbitrary polygons on the basis of triangulation with linear-time complexity on average] Numerical Methods and Programming 3(1):116-123.
- Hart, P.E., N.J. Nilsson, and B. Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE T. Syst. Sci. Cyb. 4(2): 100-107.
[+] About this article
Title
ENCLOSED ROOM EXPLORATION ALGORITHM FOR AN AUTONOMOUS MOBILE ROBOT
Journal
Systems and Means of Informatics
Volume 28, Issue 4, pp 10-21
Cover Date
2018-11-30
DOI
10.14357/08696527180402
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
computer vision; autonomous exploration mobile robot; floorplan; navigation; pathfinding
Authors
O. Arkhipov  , A. Gasilov , Yu. Maniakov , and O. Yakovlev
Author Affiliations
Orel Brach of the Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences; 137 Moskovskoe Shosse, Orel 302025, Russian Federation
|