Abstract
The paper presents Perimeter-Based Polar Scan Matching (PB-PSM), a new 2D scan matching algorithm. The algorithm favors matches with a larger perimeter overlap between the two input scans, while using a robust cost minimization process (using an adaptive direct search method, made possible due to a linear complexity data association technique). PB-PSM is benchmarked against the previously published PSM and PSM-C algorithms, and numerous realizations of the ICP algorithm. Results for convergence, accuracy, and computational speed are discussed. PB-PSM is employed on several laser scan datasets, both existing and in-house. Quantitative comparison of resulting maps is done using a new metric for evaluating occupancy grid maps accuracy, by calculating the average cell distance from the walls of the true map. The relative importance of each novel contribution is quantified using the new metric. Additional qualitative analysis is provided for previously published and relatively large datasets.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Abbreviations
- n :
-
Total number of points
- n c :
-
Number of cost-contributing points.
- r :
-
Range [mm].
- R min , R max :
-
Minimum/maximum laser range, respectively [mm].
- T E :
-
Threshold for eliminating matching anomalies.
- T M :
-
Threshold for consideration of matching success.
- T F :
-
Threshold for final cost function accepted value.
- x, y :
-
Cartesian laser point coordinates [mm].
- α :
-
Threshold for shallow angle definition.
- 𝜃 :
-
Beam angle.
- ψ :
-
azimuth angle [rad].
- ε :
-
error with respect to ground truth.
- Δ():
-
Property shift.
- ()′:
-
Quantity after roto-translation
- ()″:
-
Interpolated radii value
- () C :
-
Current scan related property.
- () R :
-
Reference scan related property.
- EKF:
-
Extended Kalman Filter.
- FOV:
-
Field of View.
- GPS:
-
Global Positioning System.
- ICP:
-
Iterative Closest Point.
- IDC:
-
Iterative Dual Correspondence.
- IMRP:
-
Iterative Matching Range Point.
- OG:
-
Occupancy Grid.
- PB-PSM:
-
Perimeter-Based Polar Scan Matching.
- PM:
-
Perimeter Matching.
- PSM:
-
Polar Scan Matching.
- PSM-C:
-
Polar Scan Matching - Cartesian.
- SLAM:
-
Simultaneous Localization And Mapping.
References
Achtelik, M., Bachrach, A., He, R., Prentice, S., Roy, N.: Autonomous navigation and exploration of a quadrotor helicopter in GPS-denied indoor environments. In IARC First Symposium on Indoor Flight Issues, July 21st. University of Puerto Rico, Mayagüez, Puerto Rico (2009)
Bailey, T., Nebot, E.: Localisation in large-scale environments. Robot. Auton. Syst. 37, 261–281 (2001)
Bailey, T., Nieto, J., Guivant, J., Stevens, M., Nebot, E.: Consistency of the EKF- SLAM algorithm. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3562–3568. Beijing (2006)
Bailey, T., Nieto, J., Nebot, E.: Consistency of the FastSLAM algorithm. In: IEEE International Conference on Intelligent Robotics and Automation, pp. 424–427. Beijing (2006)
Bergström, P.: ICP implementation for Matlab. http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=12627&objectType=FILE (2007)
Besl, P.J., McKay, N.D.: A method for registration of 3-d shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 239–256 (1992)
Brenneke, C., Wagner, B.: A scan based navigation system for autonomous operation of mobile robots in man-made environments. In: International Conference of systems engineering (ICSE). Coventry (2003)
Censi, A.: An ICP variant using a point-to-line metric. In: Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on Robotics and Automation (ICRA), pp. 19–25. Pasadena (2008)
Cox, I.J.: Blanche-an experiment in guidance and navigation of an autonomous robot vehicle. IEEE Trans. Robot. Autom. 7(2), 193–204 (1991)
Diosi, A., Kleeman, L.: Fast laser scan matching using polar coordinates. Int. J. Robot. Res. 26(10), 1125–1153 (2007)
Dissanayake, M., Newman, P., Clark, S., Durrant-Whyte, H., Csorba, M.: A solution to the simultaneous localization and map building (SLAM) problem. IEEE Trans. Robot. Autom. 17(3), 229–241 (2001)
Durrant-Whyte, H., Bailey, T.: Simultaneous localisation and mapping (SLAM): Part I the essential algorithms. IEEE Robot. Autom. Mag. 13(2), 99–110 (2006)
Elfes, A.: Using occupancy grids for mobile robot perception and navigation. Computer 22(6), 46–57 (1989)
Friedman, C.: Accurate slam with application for aerial path planning, Ph.D. thesis, Clark School of Engineering (2013)
Friedman, C., Chopra, I., Potyagaylo, S., Rand, O., Kanza, Y.: Towards model-free SLAM using a single laser range scanner for helicopter MAV. In: AIAA Guidance Navigation and Controls Conference. Portland (2011)
Friedman, C., Chopra, I., Potyagaylo, S., Rand, O., Kanza, Y.: Towards obstacle avoidance and autonomous uav operation. In: AHS Specialists’ Meeting on Unmanned Rotorcraft and Network Centric Operations. Tempe, AZ (2011)
Friedman, C., Chopra, I., Rand, O.: Highly accurate simultaneous localization and mapping for rotary wing UAVs. In: American Helicopter Society 68th Annual Forum. Fort Worth (2012)
Gutmann, J.S.: Robuste navigation autonomer mobiler systeme. Ph.D. thesis, Albert-Ludwigs-Universität Freiburg (2000)
Gutmann, J.S., Schlegel, C.: Amos: Comparison of scan matching approaches for self-localization in indoor environments. In: Proceedings of the 1st Euromicro Workshop on Advanced Mobile Robots, pp. 61–67. Kaiserslautern (1996)
Hähnel, D., Burgard, W., Fox, D., Thrun, S.: An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements. In: IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas (2003)
Hokuyo: UTM-30LX. Tech. rep. http://www.hokuyo-aut.jp/02sensor/07scanner/utm_30lx.html (2009)
Howard, A.: Laser scans dataset collected at fort Ap hill, as part of the DARPA/IPTO sdr project. Tech. rep. http://cres.usc.edu/radishrepository/view-one.php?name=ap_hill_07b (2004)
Howard, A., Parker, L.E., Sukhatme, G.S.: Experiments with a large heterogeneous mobile robot team: Exploration, mapping, deployment and detection. Int. J. Robot. Res. 25(5–6), 431–447 (2006)
Lu, F., Milios, E.: Robot pose estimation in unknown environments by matching 2D range scans. J. Intell. Robot. Syst. 18(3), 249–275 (1997)
Nguyen, V., Harati, A., Siegwart, R.: A lightweight SLAM algorithm using orthogonal planes for indoor mobile robotics. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2007, 29 October - 2 November. San Diego (2007)
Núñez, P., Vázquez-Martin, R., Bandera, A., Sandoval, F.: Fast laser scan matching approach based on adaptive curvature estimation for mobile robots. Robotica 27, 469–479 (2009)
Nüchter, A., Surmann, H., Lingemann, K., Hertzberg, J., Thrun, S.: 6D SLAM with an application in autonomous mine mapping. Robot. Autom. 2, 1998–2003 (2004)
Okubo, Y., Ye, C., Borenstein, J.: Characterization of the hokuyo URG-04LX laser rangefinder for mobile robot obstacle negotiation. SPIE Defense, Security + Sensing, Unmanned Systems Technology XI (2010)
Olson, E.B.: Real-time correlative scan matching. In: IEEE International Conference on Robotics and Automation, 2009. ICRA ’09 (2009)
Park, S., Park, S.K.: Spectral scan matching and its application to global localization for mobile robots. In: IEEE International Conference on Robotics and Automation Anchorage Convention District. Anchorage (2010)
Röfer, T.: Using histogram correlation to create consistent laser scan maps. In: Proceedings of the IEEE International Conference on Robotics Systems (IROS-2002), pp. 625–630. EPFL, Luasanne, Switzerland (2002)
Saarinen, J., Mazl, R., Kulich, M., Suomela, J., Preucil, L., Halme, A.: Methods for personal localisation and mapping. In: 5th IFAC/EURON Symposium on Intelligent Autonomous Vehicles Instituto Superior Tecnico. Lisboa (2004)
Schiele, B., Crowley, J.L.: A comparison of position estimation techniques using occupancy grids. Robot. Auton. Syst. 12(3–4), 163–161 (1994)
Segal, A., Hähnel, D., Thrun, S.: Generalized-ICP. In: Proceedings of Robotics: Science and Systems (RSS) (2009)
Shen, S., Michael, N., Kumar, V.: Autonomous multi-floor indoor navigation with a computationally constrained MAV. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 20–25 (2011)
Stachniss, C., Grisetti, G., Hähnel, D., Burgard, W.: Improved rao-blackwellized mapping by adaptive sampling and active loop-closure. In: Proceedings of the Workshop on Self-Organization of AdaptiVE behavior (SOAVE) (2004)
Tang, P., Huber, D., Akinci, B.: A comparative analysis of depth-discontinuity and mixed-pixel detection algorithms. In: Proceedings of the International Conference on 3-D Digital Imaging and Modeling (3DIM), pp. 29–38 (2007)
Thrun, S.M., Hähnel, D.: Scan alignment and 3-D surface modeling with a helicopter platform. In: The 4th International Conference on Field and Service Robotics (2003)
Thrun, S.: Learning occupancy grid maps with forward sensor models. Auton. Robots 15(2), 111–127 (2003)
Thrun, S., Burgard, W., Fox, D.: Probabilistic Robotics. 1. The MIT Press (2005)
Tomono, M.: A scan matching method using euclidean invariant signature for global localization and map building. In: ICRA, pp. 886–871. Piscataway (2004)
Yuan, X., Zhao, C.X., Tang, Z.M.: Lidar scan-matching for mobile robot localization. Inf. Technol. J. 9(1), 27–33 (2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Friedman, C., Chopra, I. & Rand, O. Perimeter-Based Polar Scan Matching (PB-PSM) for 2D Laser Odometry. J Intell Robot Syst 80, 231–254 (2015). https://doi.org/10.1007/s10846-014-0158-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-014-0158-y