  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 paper,
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.
