Efficient Computation of Map-scale Continuous Mutual Information on Chip in Real Time

Exploration tasks are essential to many emerging robotics applications, ranging from search and rescue to space exploration. The planning problem for exploration requires determining the best locations for future measurements that will enhance the fidelity of the map, for example, by reducing its total entropy. A widely-studied technique involves computing the Mutual Information (MI) between the current map and future measurements, and utilizing this MI metric to decide the locations for future measurements. However, computing MI for reasonably-sized maps is computationally and energywise expensive, often prohibitive for smaller robots and drones, which has been the bottleneck towards fast and efficient robotic exploration. As a workaround, MI is often only computed for a sparse set of points or computed at a rate slower than the update of the map, techniques which fail to provide theoretical guarantees on the efficiency of exploration. In this thesis, we introduce a new hardware accelerator architecture for MI computation that features a high-efficiency MI compute core and an optimized memory subsystem that provides sufficient bandwidth to keep the cores fully utilized. The core employs interleaving to counter the recursive algorithm, and workload balancing and numerical approximations to reduce latency and energy consumption. We demonstrate this optimized architecture on a Field-Programmable Gate Array (FPGA) implementation, which can compute MI for all cells in an entire 201-by-201 grid (e.g., representing a 20.1m-by-20.1m map at 0.1m resolution) in 1.55 ms while consuming 1.7 mJ of energy, thus finally rendering MI computation for the whole map real time and at a fraction of the energy cost of traditional compute platforms. For comparison, this particular FPGA implementation running on the Xilinx Zynq-7000 platform is two orders of magnitude faster and consumes three orders of magnitude times less energy per MI map compute, when compared to a baseline GPU implementation running on an NVIDIA GeForce GTX 980 platform. The improvements are more pronounced when compared to CPU implementations of equivalent algorithms.M.Eng