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.
白菜888
- 粉丝: 7
- 资源: 75
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0