Improved Global Localization and Resampling Techniques for Monte Carlo Localization Algorithm

Abstract

Global indoor localization algorithms enable the robot to estimate its pose in pre-mapped environments using sensor measurements when its initial pose is unknown. The conventional Adaptive Monte Carlo Localization (AMCL) is a highly efficient localization algorithm that can successfully cope with global uncertainty. Since the global localization problem is paramount in mobile robots, we propose a novel approach that can significantly reduce the amount of time it takes for the algorithm to converge to true pose. Given the map and initial scan data, the proposed algorithm detects regions with high likelihood based on the observation model. As a result, the suggested sample distribution will expedite the process of localization. In this study, we also present an effective resampling strategy to deal with the kidnapped robot problem that enables the robot to recover quickly when the sample weights drop-down due to unmapped dynamic obstacles within the sensor’s field of view. The proposed approach distributes the random samples within a circular region centered around the robot’s pose by taking into account the prior knowledge about the most recent successful pose estimation. Since the samples are distributed over the region with high probabilities, it will take less time for the samples to converge to the actual pose. The percentage of improvement for the small sample set (500 samples) exceeded 90% over the large maps and played a big role in reducing computational resources. In general, the results demonstrate the localization efficacy of the proposed scheme, even with small sample sets. Consequently, the proposed scheme significantly increases the real-time performance of the algorithm by 85.12% on average in terms of decreasing the computational cost.

Keywords

• AMCL
• Global localization
• Likelihood
• Probability
• Resampling
• Sample distribution

References

1. A. Milstein, J. N. Sánchez, and E. T. Williamson, “Robust global localization using clustered particle filtering,” in Proceedings of the National Conference on Artificial Intelligence, 2002, pp. 581–586.
2. J. J. Leonard and H. F. Durrant-Whyte, “Mobile Robot Localization by Tracking Geometric Beacons,” IEEE Trans. Robot. Autom., vol. 7, no. 3, pp. 376–382, 1991, DOI: 10.1109/70.88147.
3. S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics, 3rd ed. United States: MIT Press, 2005.
4. S. P. Engelson, “Passive Navigation and Visual Place Recognition,” in Doctoral dissertation, Yale University, 1994.
5. W. Burgard, D. Fox, D. Hennig, and T. Schmidt, “Estimating the absolute position of a mobile robot using position probability grids,” in Proceedings of the National Conference on Artificial Intelligence, 1996, vol. 2, pp. 896–901.
6. P. Jensfelt and S. Kristensen, “Active global localization for a mobile robot using multiple hypothesis tracking,” IEEE Trans. Robot. Autom., vol. 17, no. 5, pp. 748–760, Oct. 2001, DOI: 10.1109/70.964673.
7. F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “Monte Carlo localization for mobile robots,” in Proceedings - IEEE International Conference on Robotics and Automation, 1999, vol. 2, pp. 1322--1328, DOI: 10.1016/S0004-3702(01)00069-8.
8. N. J. Gordon, D. J. Salmond, and A. F. M. Smith, “Novel approach to nonlinear/non-gaussian Bayesian state estimation,” in IEE Proceedings, Part F: Radar and Signal Processing, 1993, vol. 140, no. 2, pp. 107–113, DOI: 10.1049/ip-f-2.1993.0015.

9. G. Grisetti, C. Stachniss, and W. Burgard, “Improved techniques for grid mapping with Rao-Blackwellized particle filters,” IEEE Trans. Robot., vol. 23, no. 1, pp. 34–46, 2007, DOI: 10.1109/TRO.2006.889486.
10. T. Röfer and M. Jüngel, “Vision-based fast and reactive Monte-Carlo localization,” in Proceedings - IEEE International Conference on Robotics and Automation, 2003, 3rd ed., vol. 1, pp. 856–861, DOI: 10.1109/robot.2003.1241700.
11. Y. Liu and H. Zhang, “Visual loop closure detection with a compact image descriptor,” in IEEE International Conference on Intelligent Robots and Systems, 2012, pp. 1051–1056, DOI: 10.1109/IROS.2012.6386145.
12. M. Labbé and F. Michaud, “Online global loop closure detection for large-scale multi-session graph-based SLAM,” in IEEE International Conference on Intelligent Robots and Systems, 2014, pp. 2661–2666, DOI: 10.1109/IROS.2014.6942926.
13. M. Cummins and P. Newman, “FAB-MAP: Probabilistic localization and mapping in the space of appearance,” Int. J. Rob. Res., vol. 27, no. 6, pp. 647–665, Jun. 2008, DOI: 10.1177/0278364908090961.
14. K. L. Ho and P. Newman, “Detecting loop closure with scene sequences,” Int. J. Comput. Vis., vol. 74, no. 3, pp. 261–286, Sep. 2007, DOI: 10.1007/s11263-006-0020-1.
15. S. Lang, G. Murrow, S. Lang, and G. Murrow, “The Distance Formula,” in Geometry, Springer New York, 1988, pp. 110–122.