Real-time correlative scan matching

Scan matching, the problem of registering two laser scans in order to determine the relative positions from which the scans were obtained, is one of the most heavily relied-upon tools for mobile robots. Current algorithms, in a trade-off for computational performance, employ heuristics in order to quickly compute an answer. Of course, these heuristics are imperfect: existing methods can produce poor results, particularly when the prior is weak. The computational power available to modern robots warrants a re-examination of these quality vs. complexity trade-offs. In this paper, we advocate a probabilistically-motivated scan-matching algorithm that produces higher quality and more robust results at the cost of additional computation time. We describe several novel implementations of this approach that achieve real-time performance on modern hardware, including a multi-resolution approach for conventional CPUs, and a parallel approach for graphics processing units (GPUs). We also provide an empirical evaluation of our methods and several contemporary methods, illustrating the benefits of our approach. The robustness of the methods make them especially useful for global loop-closing.

Authors

• Edwin Olson

Keywords

• Robustness
• Laser radar
• Iterative closest point algorithm
• Mobile robots
• Cost function
• Graphics
• Navigation
• Wheels
• Motion estimation
• Central Processing Unit
• Scan Matching
• Correlative Scan Matching
• Graphics Processing Unit
• Log-likelihood
• Use Of Algorithms
• Lookup Table
• Line Segment
• Pair Of Points
• Covariance Estimation
• Part Of Environment
• Map Points
• Rotated Component
• Odometry
• Simultaneous Localization And Mapping
• Iterative Closest Point
• Rigid Body Transformation
• Hill-climbing
• LiDAR Scans
• Reference Scan
• Query Point
• Correlation-based Methods
• Solution Error
• Runtime Complexity
• Search Window
• Algorithm In Order
• Regeneration Buffer
• Low-resolution Map
• Occlusion Effect
• Local Context
• Step Size