FSMI: Fast computation of Shannon mutual information for information-theoretic mapping
FSMI: Fast computation of Shannon mutual information for information-theoretic mapping
复制标题
DOI：
10.1109/icra.2019.8793541
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Zhengdong Zhang;Theia Henderson;S. Karaman;V. Sze
中科院分区：
文献类型：
--
作者：
Zhengdong Zhang;Theia Henderson;S. Karaman;V. Sze
探索任务嵌入在许多机器人应用中，例如搜索和救援以及太空探索。基于信息的探索算法旨在通过最大化信息理论度量（例如地图和潜在的未来测量之间的互信息）来找到信息量最大的轨迹。不幸的是，大多数现有的基于信息的探索算法的计算困难的香农互信息度量的评估所困扰。在这篇文章中，我们考虑的基本问题，评估香农互信息之间的地图和距离测量。首先，我们考虑2D环境。我们提出了一种新的算法，称为快速香农互信息（FSMI）。该算法背后的关键见解是，某个积分可以解析计算，从而节省大量的计算。其次，我们考虑3D环境，由有效的数据结构表示，例如，一个可压缩映射，使得测量值被行程编码（RLE）压缩。我们提出了一种新的算法，称为FSMI-RLE，有效地评估香农互信息的测量时，使用RLE压缩。对于FSMI和FSMI-RLE，我们还提出了对传感器噪声分布进行不同假设的变体，以进一步节省计算。我们在广泛的实验中评估所提出的算法。特别是，我们表明，所提出的算法优于现有的算法，计算香农互信息以及其他算法，计算柯西-施瓦茨二次互信息（CSQMI）。此外，我们证明了计算香农互信息的3D地图上的第一次。
Exploration tasks are embedded in many robotics applications, such as search and rescue and space exploration. Information-based exploration algorithms aim to find the most informative trajectories by maximizing an information-theoretic metric, such as the mutual information between the map and potential future measurements. Unfortunately, most existing information-based exploration algorithms are plagued by the computational difficulty of evaluating the Shannon mutual information metric. In this article, we consider the fundamental problem of evaluating Shannon mutual information between the map and a range measurement. First, we consider 2D environments. We propose a novel algorithm, called the fast Shannon mutual information (FSMI). The key insight behind the algorithm is that a certain integral can be computed analytically, leading to substantial computational savings. Second, we consider 3D environments, represented by efficient data structures, e.g., an OctoMap, such that the measurements are compressed by run-length encoding (RLE). We propose a novel algorithm, called FSMI-RLE, that efficiently evaluates the Shannon mutual information when the measurements are compressed using RLE. For both the FSMI and the FSMI-RLE, we also propose variants that make different assumptions on the sensor noise distribution for the purpose of further computational savings. We evaluate the proposed algorithms in extensive experiments. In particular, we show that the proposed algorithms outperform existing algorithms that compute Shannon mutual information as well as other algorithms that compute the Cauchy–Schwarz quadratic mutual information (CSQMI). In addition, we demonstrate the computation of Shannon mutual information on a 3D map for the first time.