A continuous approach to information-theoretic exploration with range sensors

In this thesis we derive an algorithm that addresses the computational bottleneck of robotic exploration: computing the expected information gain -- i.e. mutual information -- between an occupancy map and a range sensor measurement. The algorithm we derive has a lower complexity and in practice runs 200 to 1500 times faster than the state of the art CSQMI and FSMI algorithms. The speedup is due to the realization that the mutual information at one cell of an occupancy map can be defined in terms of the mutual information at adjacent cells. This makes computing the mutual information at all cells in the map much faster than computing the mutual information of each cell independently. The derivation is unique in that it models the occupancy map and range measurements as continuous random fields despite the fact that actual computation requires quantization. This framework is critical to the recursive definitions that provide performance gain. It also reveals flaws, previously obscured by discretization, in several well established concepts: the practice of initializing occupancy probabilities in an occupancy grid to 1/2 is arbitrary and in application often an overestimate; and the formula for mutual information defined by Julian et al. fails to take into account a radial volume element, which changes mutual information values dramatically. Both of these claims are supported empirically. Finally, we investigate two heuristics that use mutual information computation to perform actual exploration tasks and provide an analysis of each heuristic's use case. These claims are validated by synthetic exploration experiments.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Henderson, Trevor(Trevor F.)

Advisor dc:contributor.advisor

• Sertac Karaman and Vivienne Sze.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/124248

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/124248