Improving Monte Carlo Localization Performance Using Strategic Navigation Policies
Resumo
An important problem in robotics is to determine and maintain the position of a robot that moves through a previously known environment with indistinguishable reference points. This problem is made difficult due to the inherent noise in robot movement and identification of reference points and due to multiple identical reference points. Monte Carlo Localization (MCL) is a frequently used technique to solve this problem and its performance intuitively depends on how the robot explores the map. In this paper, we evaluate the performance of MCL under different navigation policies. In particular, we propose a novel navigation policy that aims in reducing the uncertainty in the robot's location by making a greedy movement at every step. We show that this navigation policy can significantly outperform random movements, particularly when the map has few reference points. Moreover, differently from random movements, the performance of the proposed navigation policy is not monotonic with the number of reference points on the map.
Referências
Baudry, G., Macharis, C., and Vallée, T. (2018). Range-based multi-actor multi-criteria analysis: A combined method of multi-actor multi-criteria analysis and monte carlo simulation to support participatory decision making under uncertainty. European Journal of Operational Research, 264(1):257 – 269.
dos S. Ferreira Júnior, H. J. and Figueiredo, D. R. (2018). Influence of location and nuber of landmarks on the monte carlo localization problem. In XV Encontro Nacional de Inteligência Artificial e Computacional (ENIAC).
Elfes, A. (1987). Sonar-based real-world mapping and navigation. IEEE Journal on Robotics and Automation, 3(3):249–265.
Fox, D., Burgard, W., Dellaert, F., and Thrun, S. (1999). Monte carlo localization: Efficient position estimation for mobile robots. In Nat. Conf. on Artificial Intelligence (AAAI), pages 343–349.
Fox, D., Burgard, W., and Thrun, S. (1998). Active markov localization for mobile robots. Robotics and Autonomous Systems, 25(3-4):195–207.
Gottipati, S. K., Seo, K., Bhatt, D., Mai, V., Murthy, K., and Paull, L. (2019). Deep active localization. IEEE Robotics and Automation Letters, 4(4):4394–4401.
Hou, X. and Arslan, T. (2017). Monte carlo localization algorithm for indoor positioning using bluetooth low energy devices. In Int. Conf. on Localization and GNSS (ICLGNSS), pages 1–6.
Jensfelt, P. and Kristensen, S. (2001). Active global localization for a mobile robot using multiple hypothesis tracking. IEEE Transactions on Robotics and Automation, 17(5):748–760.
Li, T., Sun, S., and Duan, J. (2010). Monte carlo localization for mobile robot using adaptive particle merging and splitting technique. In IEEE Int. Conf. on Information and Automation, pages 1913–1918.
Milstein, A. (2008). Occupancy grid maps for localization and mapping. In Motion Planning. InTech.
Rekleitis, I., Meger, D., and Dudek, G. (2006). Simultaneous planning, localization, and mapping in a camera sensor network. Robotics and Autonomous Systems.
Thruna, S., Foxb, D., Burgard, W., and Dellaert, F. (2001). Robust monte carlo localization for mobile robots. Artificial Intelligence, 128:99–141.
Tovar, B., Muñoz-Gómez, L., Murrieta-Cid, R., Alencastre-Miranda, M., Monroy, R., and Hutchinson, S. (2006). Planning exploration strategies for simultaneous localization and mapping. Robotics and Autonomous Systems, 54(4):314–331.
NA Another interesting result is the relatively poor performance when the number of landmarks ranges from 3 to 7. In this regime, the movement noise and symmetry of landmarks undermine the proposed method. The investigation of navigation policies that can also be effective in this regime is left as future work.
Baudry, G., Macharis, C., and Vallée, T. (2018). Range-based multi-actor multi-criteria analysis: A combined method of multi-actor multi-criteria analysis and monte carlo simulation to support participatory decision making under uncertainty. European Journal of Operational Research, 264(1):257 – 269.
dos S. Ferreira Júnior, H. J. and Figueiredo, D. R. (2018). Influence of location and nuber of landmarks on the monte carlo localization problem. In XV Encontro Nacional de Inteligência Artificial e Computacional (ENIAC).
Elfes, A. (1987). Sonar-based real-world mapping and navigation. IEEE Journal on Robotics and Automation, 3(3):249–265.
Fox, D., Burgard, W., Dellaert, F., and Thrun, S. (1999). Monte carlo localization: Efficient position estimation for mobile robots. In Nat. Conf. on Artificial Intelligence (AAAI), pages 343–349.
Fox, D., Burgard, W., and Thrun, S. (1998). Active markov localization for mobile robots. Robotics and Autonomous Systems, 25(3-4):195–207.
Gottipati, S. K., Seo, K., Bhatt, D., Mai, V., Murthy, K., and Paull, L. (2019). Deep active localization. IEEE Robotics and Automation Letters, 4(4):4394–4401.
Hou, X. and Arslan, T. (2017). Monte carlo localization algorithm for indoor positioning using bluetooth low energy devices. In Int. Conf. on Localization and GNSS (ICLGNSS), pages 1–6.
Jensfelt, P. and Kristensen, S. (2001). Active global localization for a mobile robot using multiple hypothesis tracking. IEEE Transactions on Robotics and Automation, 17(5):748–760.
Li, T., Sun, S., and Duan, J. (2010). Monte carlo localization for mobile robot using adaptive particle merging and splitting technique. In IEEE Int. Conf. on Information and Automation, pages 1913–1918.
Milstein, A. (2008). Occupancy grid maps for localization and mapping. In Motion Planning. InTech.
Rekleitis, I., Meger, D., and Dudek, G. (2006). Simultaneous planning, localization, and mapping in a camera sensor network. Robotics and Autonomous Systems.
Thruna, S., Foxb, D., Burgard, W., and Dellaert, F. (2001). Robust monte carlo localization for mobile robots. Artificial Intelligence, 128:99–141.
Tovar, B., Muñoz-Gómez, L., Murrieta-Cid, R., Alencastre-Miranda, M., Monroy, R., and Hutchinson, S. (2006). Planning exploration strategies for simultaneous localization and mapping. Robotics and Autonomous Systems, 54(4):314–331.
dos S. Ferreira Júnior, H. J. and Figueiredo, D. R. (2018). Influence of location and nuber of landmarks on the monte carlo localization problem. In XV Encontro Nacional de Inteligência Artificial e Computacional (ENIAC).
Elfes, A. (1987). Sonar-based real-world mapping and navigation. IEEE Journal on Robotics and Automation, 3(3):249–265.
Fox, D., Burgard, W., Dellaert, F., and Thrun, S. (1999). Monte carlo localization: Efficient position estimation for mobile robots. In Nat. Conf. on Artificial Intelligence (AAAI), pages 343–349.
Fox, D., Burgard, W., and Thrun, S. (1998). Active markov localization for mobile robots. Robotics and Autonomous Systems, 25(3-4):195–207.
Gottipati, S. K., Seo, K., Bhatt, D., Mai, V., Murthy, K., and Paull, L. (2019). Deep active localization. IEEE Robotics and Automation Letters, 4(4):4394–4401.
Hou, X. and Arslan, T. (2017). Monte carlo localization algorithm for indoor positioning using bluetooth low energy devices. In Int. Conf. on Localization and GNSS (ICLGNSS), pages 1–6.
Jensfelt, P. and Kristensen, S. (2001). Active global localization for a mobile robot using multiple hypothesis tracking. IEEE Transactions on Robotics and Automation, 17(5):748–760.
Li, T., Sun, S., and Duan, J. (2010). Monte carlo localization for mobile robot using adaptive particle merging and splitting technique. In IEEE Int. Conf. on Information and Automation, pages 1913–1918.
Milstein, A. (2008). Occupancy grid maps for localization and mapping. In Motion Planning. InTech.
Rekleitis, I., Meger, D., and Dudek, G. (2006). Simultaneous planning, localization, and mapping in a camera sensor network. Robotics and Autonomous Systems.
Thruna, S., Foxb, D., Burgard, W., and Dellaert, F. (2001). Robust monte carlo localization for mobile robots. Artificial Intelligence, 128:99–141.
Tovar, B., Muñoz-Gómez, L., Murrieta-Cid, R., Alencastre-Miranda, M., Monroy, R., and Hutchinson, S. (2006). Planning exploration strategies for simultaneous localization and mapping. Robotics and Autonomous Systems, 54(4):314–331.
NA Another interesting result is the relatively poor performance when the number of landmarks ranges from 3 to 7. In this regime, the movement noise and symmetry of landmarks undermine the proposed method. The investigation of navigation policies that can also be effective in this regime is left as future work.
Baudry, G., Macharis, C., and Vallée, T. (2018). Range-based multi-actor multi-criteria analysis: A combined method of multi-actor multi-criteria analysis and monte carlo simulation to support participatory decision making under uncertainty. European Journal of Operational Research, 264(1):257 – 269.
dos S. Ferreira Júnior, H. J. and Figueiredo, D. R. (2018). Influence of location and nuber of landmarks on the monte carlo localization problem. In XV Encontro Nacional de Inteligência Artificial e Computacional (ENIAC).
Elfes, A. (1987). Sonar-based real-world mapping and navigation. IEEE Journal on Robotics and Automation, 3(3):249–265.
Fox, D., Burgard, W., Dellaert, F., and Thrun, S. (1999). Monte carlo localization: Efficient position estimation for mobile robots. In Nat. Conf. on Artificial Intelligence (AAAI), pages 343–349.
Fox, D., Burgard, W., and Thrun, S. (1998). Active markov localization for mobile robots. Robotics and Autonomous Systems, 25(3-4):195–207.
Gottipati, S. K., Seo, K., Bhatt, D., Mai, V., Murthy, K., and Paull, L. (2019). Deep active localization. IEEE Robotics and Automation Letters, 4(4):4394–4401.
Hou, X. and Arslan, T. (2017). Monte carlo localization algorithm for indoor positioning using bluetooth low energy devices. In Int. Conf. on Localization and GNSS (ICLGNSS), pages 1–6.
Jensfelt, P. and Kristensen, S. (2001). Active global localization for a mobile robot using multiple hypothesis tracking. IEEE Transactions on Robotics and Automation, 17(5):748–760.
Li, T., Sun, S., and Duan, J. (2010). Monte carlo localization for mobile robot using adaptive particle merging and splitting technique. In IEEE Int. Conf. on Information and Automation, pages 1913–1918.
Milstein, A. (2008). Occupancy grid maps for localization and mapping. In Motion Planning. InTech.
Rekleitis, I., Meger, D., and Dudek, G. (2006). Simultaneous planning, localization, and mapping in a camera sensor network. Robotics and Autonomous Systems.
Thruna, S., Foxb, D., Burgard, W., and Dellaert, F. (2001). Robust monte carlo localization for mobile robots. Artificial Intelligence, 128:99–141.
Tovar, B., Muñoz-Gómez, L., Murrieta-Cid, R., Alencastre-Miranda, M., Monroy, R., and Hutchinson, S. (2006). Planning exploration strategies for simultaneous localization and mapping. Robotics and Autonomous Systems, 54(4):314–331.
Publicado
15/10/2019
Como Citar
FERREIRA JÚNIOR, Henrique; FIGUEIREDO, Daniel.
Improving Monte Carlo Localization Performance Using Strategic Navigation Policies. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 16. , 2019, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 515-526.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2019.9311.
