Utility-based map reduction for ground and flight vehicle navigation

Maps used for navigation often include a database of location descriptions for place-recognition (to enable localization or loop-closing), which permits bounded-error navigation performance. A standard localization system must describe the entire operational environment in its place-recognition database. A standard pose-graph-based simultaneous localization and mapping (SLAM) system adds a new place-recognition database entry for every new vehicle pose, which grows linearly and unbounded in time and thus becomes unsustainable. To address these issues, this thesis proposes a new map-reduction approach that pre-constructs a fixed-size place-recognition database amenable to the limited storage and processing resources of the vehicle by exploiting the high-level structure of the environment and vehicle motion. In particular, the thesis introduces the concept of location utility - which encapsulates the visitation probability of a location and its spatial distribution relative to nearby locations in the database - as a measure of the value of potential localization or loop-closure events to occur at that location. While finding the optimal reduced location database is NP-hard, an efficient greedy algorithm is developed to sort all the locations in a map based on their relative utility without access to sensor measurements or the vehicle trajectory. This enables predetermination of a generic, limited-size place-recognition database containing the N best locations in the environment. A street-map simulator using city-map data and a terrain relative navigation simulator using terrestrial rocket flight data are used to validate the approach and show that an accurate map and trajectory reconstruction (pose-graph) can be attained even when using a place-recognition database with only 1% of the entries of the corresponding full database.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Steiner, Theodore J., III (Theodore Joseph)

Advisor dc:contributor.advisor

• Jeffrey A. Hoffman and John J. Leonard.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

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

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/98802

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/98802