【泡泡一分钟】CDDT：可用于加速定位的快速2D光线投射近似法

会员服务 ·

【泡泡一分钟】CDDT：可用于加速定位的快速2D光线投射近似法

2019 年 9 月 12 日 泡泡机器人SLAM

每天一分钟，带你读遍机器人顶级会议文章

标题：CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization

作者：Corey H. Walsh and Sertac Karaman

来源：IEEE International Conference on Robotics and Automation (ICRA)，2018

编译：林旭滨

审核：颜青松，陈世浪

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

摘要

定位对于自主移动机器人而言是必不可少的功能。目前成熟的定位方案结合了光线投射（ray casting）和粒子滤波器，这使得算法的计算量很大，难以在计算资源受限的移动机器人上运行。我们提出了一种新的数据结构称为压缩方向距离变换（Compressed Directional Distance Transform）以加速二维栅格占据地图中的光线投射过程。相比于其它方法在恶劣的状况下的性能表现，我们的方法不仅允许地图在线更新，并且在地图尺寸固定的情况下，能用接近常量时间实现光线投射。我们的实验结果表明所提算法性能接近基于查表法的三维光线投射，但是在内存使用量和预算量上却少了两个数量级。这使得我们能在一个移动机器人所搭载的单个CPU线程板上，运行粒子滤波器算法，用40Hz的速度同时维护2500个粒子，其中每个粒子具有61根投射线。

表1 各种方法内存使用量和初始化时间对比（CDDT和PCDDT是本文所提方法）。

表2 在两个不同地图上的定位速度，Speedup一栏指的是各种方法相对于Bresenham's Line的速度提升对比。

Abstract

Localization is an essential component for autonomous robots. A well-established localization approach combines ray casting with a particle filter, leading to a computationally expensive algorithm that is difficult to run on resource-constrained mobile robots. We present a novel data structure called the Compressed Directional Distance Transform for accelerating ray casting in two dimensional occupancy grid maps. Our approach allows online map updates, and near constant time ray casting performance for a fixed size map, in contrast with other methods exhibit poor worst case performance. Our experimental results show that the proposed algorithm approximates the performance characteristics of reading from a three dimensional lookup table of ray cast solutions while requiring two orders of magnitude less memory and precomputation. This results in a particle filter algorithm which can maintain 2500 particles with 61 ray casts per particle at 40Hz, using a single CPU thread onboard a mobile robot.

如果你对本文感兴趣，请点击点击阅读原文下载完整文章，如想查看更多文章请关注【泡泡机器人SLAM】公众号（paopaorobot_slam）。

百度网盘提取码：fvwz

欢迎来到泡泡论坛，这里有大牛为你解答关于SLAM的任何疑惑。

有想问的问题，或者想刷帖回答问题，泡泡论坛欢迎你！

泡泡网站：www.paopaorobot.org

泡泡论坛：http://paopaorobot.org/bbs/