Real-Time Correlative Scan Matching
Edwin B. Olson
University of Michigan
Department of Electrical Engineering and Computer Science
Ann Arbor, MI 48109
Email: ebolson@umich.edu
http://april.eecs.umich.edu
Abstract— 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.
I. INTRODUCTION
Consider a robot sensing an environment from two poses
x
0
and x
1
; at each position, it obtains a two-dimensional lidar
scan (z
0
and z
1
). These lidar scans capture a horizontal cross-
section of the environment typically sampled at one degree
intervals. Provided that some parts of the environment are
visible from both x
0
and x
1
, it is generally possible to find
a rigid-body transformation T that will project the points z
1
so that they align with z
0
. This process of matching the scans
z
0
and z
1
is known as scan matching. The solution to a scan
matching problem is the rigid-body transformation T , which is
parameterized by three values: two translational components
(∆x and ∆y) and a rotational component (θ). Aside from
being an interesting perceptual problem, scan matching is at
the center of most navigation, mapping, and localization sys-
tems. This is because the rigid body transformation T exactly
corresponds to the motion of the robot as it travelled from
x
0
to x
1
. Since lidar-derived data is typically of far-higher
quality than odometry (which is prone to unpredictable wheel
slippage), scan matching plays a central role in estimating the
motion of the robot.
The primary challenge in designing a scan matcher is to
minimize the runtime complexity while maximizing the qual-
ity (and robustness) of the solutions. Most existing methods are
designed around computationally-efficient local searches that
produce answers quickly, but are not robust to initialization
Fig. 1. Correlation (3D) Cost Function. Given two laser scans (bottom),
we compute a rigid-body transform that aligns them by computing the cost
function in three dimensions (translation in ˆx and ˆy) and θ). Each tile
represents a slice of the cost volume for a fixed θ. The numerical maximum
is then identified (white cross hairs).
error. The problem is that scan matching, when viewed as an
optimization problem, is rarely convex: the cost surface can be
very complicated, having many local minima (see Fig. 1). The
vehicle’s dead-reckoning error can cause the initial estimate to
be far from the global maximum; as a result, many approaches
fail to identify the global maximum.
This paper describes a family of scan matching algorithms
based upon cross-correlation of two lidar scans. Our approach
casts the problem in a probabilistic framework: it finds the
rigid-body transformation that maximizes the probability of
having observed the data. Rather than trusting a local search
algorithm to find the global maximum (an approach that does
not work well in the presence of initialization noise, as we
will illustrate), we perform a search over the entire space of
plausible rigid-body transformations. This plausible region is
derived from a prior which, in turn, can be derived from the
commanded motion or wheel/visual odometry.
评论0