Influence of Location and Number of Landmarks on the Monte Carlo Localization Problem

  • Henrique José dos S. Ferreira Júnior UFRJ
  • Daniel Ratton Figueiredo UFRJ


An important problem in robotics is to determine and maintain the position of a robot that moves through a previously known environment with reference points that are indistinguishable, which is made difficult due to the inherent noise in robot movement and identification of reference pints. Monte Carlo Localization (MCL) is a frequently used technique to solve this problem and its performance intuitively depends on reference points. In this paper we evaluate the performance of MCL as a function of the number of reference points and their positioning in the environment. In particular, we show that performance is not monotonic in the number of reference points and that a random positioning of the reference points is close to optimal.


Elinas, P. and Little, J. J. (2005). mcl: Monte-carlo localization for mobile robots with stereo vision. In Proc. of Robotics: Science and Systems (RSS), volume 53.

Fox, D., Burgard, W., Dellaert, F., and Thrun, S. (1999). Monte carlo localization: Efficient position estimation for mobile robots. In Proc. of the National Conference on Artificial Intelligence (AAAI), pages 343–349.

Howard, A. (2006). Multi-robot simultaneous localization and mapping using particle filters. The International Journal of Robotics Research, 25(12):1243–1256.

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.

Metropolis, N., Rosenbluth, A.W., Rosenbluth, M. N., Teller, A. H., and Teller, E. (1953). Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6):1087–1092.

Milstein, A. (2008). Occupancy grid maps for localization and mapping. In Motion Planning. InTech.

Muzio, A., Aguiar, L., Máximo, M. R., and Pinto, S. C. (2016). Monte carlo localization with field lines observations for simulated humanoid robotic soccer. In XIII Latin American Robotics Symposium and IV Brazilian Robotics Symposium (LARS/SBR), pages 334–339.

Payá, L., Fernández, L., Gil, A., and Reinoso, O. (2010). Map building and monte carlo localization using global appearance of omnidirectional images. Sensors, 10(12):11468–11497.

Thruna, S., Foxb, D., Burgard, W., and Dellaert, F. (2001). Robust monte carlo localization for mobile robots. Artificial Intelligence, 128:99–141.

Torma, P., Gy¨orgy, A., and Szepesvári, C. (2010). A markov-chain monte carlo approach to simultaneous localization and mapping. In Proc. 13th International Conference on Artificial Intelligence and Statistics, pages 852–859.

FERREIRA JÚNIOR, Henrique José dos S.; FIGUEIREDO, Daniel Ratton. Influence of Location and Number of Landmarks on the Monte Carlo Localization Problem. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 15. , 2018, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . p. 413-424. ISSN 2763-9061. DOI: