Algorithms for Maps Construction and
Localization in a Mobile Robot

Daniel ROJAS¹, Ginno MILLÁN², Fernando PASSOLD³, Román OSORIO⁴, Claudio CUBILLOS¹, Gastón LEFRANC¹

¹Pontificia Universidad Católica de Valparaíso,
Av. Brasil 2950, Valparaíso, Chile
glefranc@ucv.cl
²Universidad Catolica del Norte,
Larrondo 1281, Coquimbo, Chile
gmillan@ucn.cl

³Universidade de Passo Fundo, BR 285,
Bairro Passo Fundo, Sao José, Brazil
fpassold@upf.br
⁴IIMAS, Universidad Autónoma de México
Av. Universidad 3000, México
roman@unam.mx

Abstract: In this paper it is presented an integration of algorithms that permits maps construction and navigation of mobile robots. Simultaneous Localization and Mapping (SLAM) algorithm is used based on FastSLAM method. Navigation system is based on Vector Field Histogram algorithm to avoid obstacle and a spiral way trajectory method. Up to three different complex simulation maps have been used to evaluate the system.

Keywords: Mobile Robot, Vector Field Histogram (VHF) algorithm, Simultaneous Localization and Mapping (SLAM), FastSLAM.

>>Full text
CITE THIS PAPER AS:
Daniel ROJAS, Ginno MILLÁN, Fernando PASSOLD, Román OSORIO, Claudio CUBILLOS, Gastón LEFRANC, Algorithms for Maps Construction and Localization in a Mobile Robot, Studies in Informatics and Control, ISSN 1220-1766, vol. 23(2), pp. 189-196, 2014. https://doi.org/10.24846/v23i2y201407

Introduction

The main problem in an autonomous mobile robot is the complexity and difficulty to move in an unknown environment. To solve this problem, the robot must construct a map of the environment and, at the same time, determine their local localization on the map. If only a map is provided, it is called global localization. When only a priori state is given, both states the map and pose are estimated simultaneously, it is called simultaneous localization and mapping. This is the reason SLAM and global localization is considered disjointed problems. But, neither in practice are nor disjointed because of the map is imperfect, having small errors and a lack or an excess of landmark [1], [2].

Objects or obstacles that exist in an environment are called landmarks. In real applications, unknown environment exploration has a set of landmarks, allowing to measure relative distance from the robot to each landmark.

In this paper, both SLAM and global localization are used for mapping and a mobile robot simultaneous localization (SLAM). This permits a mobile robot moving in an unknown environment and its implementation in closed environments (e.g. rooms, offices, warehouses, etc.) with autonomous exploration [1], [2].

SLAM solutions have generally been based on Extended Kalman Filter (EKF) SLAM [3]-[5]; and type Rao-Blackwellized particle filter, called FastSLAM. [8].

EKF filter allows to integrate the measures carried out by the robot and control actions to create the probably environment map. Figure 1 shows a set of landmarks in the environment, the robot’s position and observations on the landmarks. [9], [10].

This SLAM EKF algorithm grows quadratic form with the number of landmarks on the map, making complicated to generate maps. It is also sensitive to erroneous data associated to observations with landmarks.

It has been proposed a compressed algorithm to improve performance and reduce complexity. Map is subdivided into several sub maps [4].

Online SLAM, recovers the present position Xt of the robot, instead of the entire route. These algorithms tend to be incremental and can process a data item at a time. This type of algorithms is usually called filters.

To solve any SLAM problem, the robot must have two models: a mathematical model that relates measurements of odometry ut to Xt-1 and Xt robot positions and a model that relates measurements Zt to the environment map and Xt robot location.

There are several methods for mobile robot navigation from one point to another one; it uses the VHF algorithm for navigation. This algorithm utilizes a two-dimensional Cartesian histogram to represent obstacles.

Each cell has a value representing the certainty that there is an obstacle in that position. The Cartesian histogram reduces to a one-dimensional polar histogram. In this ways, the probability of finding an obstacle is obtained. Then, all available routes to the destination are look for, and select which have less cost function G. [11]-[14].

In this paper, an algorithm integration that allows map construction and simultaneous localization (SLAM), with autonomous indoor navigation through a mobile robot is presented. A construction maps and location algorithm is based on the FastSLAM method. For autonomous exploration, it uses the method of Vector Field Histogram (VHF) based navigation algorithm for navigation to avoid obstacles and a spiral shape path, to explore the environment. This algorithm integration is is evaluated using simulation in three different types of maps, with varying degrees of complexity. Then, developed algorithm is implemented in a real mobile robot.

REFERENCES

HYUKDOO, C., W.-Y. KWANG, K. EUNTAI, Simultaneous Global Localization and Mapping, IEEE/ASME Transactions on Mechatronics, vol. 19(4), 2014, pp. 1160-1170.
HASHIKAWA, F., K. MORIOKA, Mobile Robot Navigation based on Interactive SLAM with an Intelligent Space. 8th International Conference on Ubiquitous Robots and Ambient Intelligence, 2011, pp. 788-789.
GARULLI, A., A. GIANNITRAPANI, A. ROSSI, A. VICINO, Mobile Robots SLAM for Line-based Environment Representation, Decision and Control Conference and European Control Conference, 2005.
LEE, Y., T. KWON, J. SONG, SLAM of a Mobile Robot Using Thinning-based Topological Information, International Journal of Control, Automation and Systems, vol. 5(5), 2007, pp. 577-583.
RESTREPO, C., A. ALZATE, C. TORRES, J. MOLINAS, Localización y Construcción de un Mapa en Forma Simultánea Utilizando el Filtro Extendido de Kalman, Revista de Ingeniería UC, Colombia, vol. 16(1), 2009, pp. 11-18.
OSORIO, R., S. GARCÍA, M. PENA, I. LOPEZ-JUAREZ, G. LEFRANC, Movement and Color Detection of a Dynamic Object: An application to a Mobile Robot, Studies in Informatics and Control, vol. 21, no. 1, 2012, pp. 33-40.
HADDA, I., J. KNANI, Global Mapping and Localization for Mobile Robots Using Stereo Vision, 10th International Multi-Conference on Systems, Signals & Devices, 2013, pp. 1-6.
MONTEMERLO, M., S. THRUN, Simultaneous Localization and Mapping with Unknow Data Association Using FastSLAM, Proceedings of the IEEE International Conference on Robotics Automation, USA, 2003, pp. 1985-1991.
MOUTTARLIER, P., R. CHATILA, An Experimental System or Incremental Environment Modeling by an Autonomous Mobile Robot, 1st International Symposium on Experimental Robotics, Canada, 2009.
HERNANDEZ-MARTINEZ, E. G., E. ARANDA-BRICAIRE, Decentralized Formation Control of Multi-agent Robot Systems based on Formation Graphs, Studies in Informatics and Control, vol. 21, no. 1, 2012, pp. 7-16.
FOX, D., Adapting the Sample Size in Particle Filters Through KLD-Sampling, International Journal of Robotics Research, vol. 22, no. 12, 2003, pp. 985-1003.
LATOMBE, J.-C., Robot Motion Planning, Kluwer Academic Publisher, 1991.
ULRICH, I., BORENSTEIN, J., VHF+: Reliable Obstacle Avoidance for Fast Mobile Robots, Proceedings of the IEEE International Conference on Robotics Automation, vol. 2, 1998, pp. 1572-1577.
MONTEMERLO, M., S. THRUN, D. KOLLER, B. WEGBREIT, FastSLAM 2.0: An Improved Particle Filtering Algorithm for Simultaneous Localization and Mapping that Probably Converges, Proceedings of the Sixteenth International Conference on Artificial Intelligence, Mexico, 2003.
ROJAS, D., F. PASSOLD, C. CUBILLOS, G. LEFRANC, Integration of Algorithms for Maps Construction and Simultaneous Localization in a Mobile Robot, the 6th International Conference on Management and Control of Production and Logistics, Brazil, 2013.
FREES, D., C. CUBILLOS, G. LEFRANC, Mobile Robot with Multi Agent Architecture. IEEE International Conference on Engineering and Systems Applications, Santiago de Chile, 2012.