Location Utility-based Map Reduction

TitleLocation Utility-based Map Reduction
Publication TypeConference Proceedings
Year of Conference2015
AuthorsSteiner T, Huang G, Leonard JJ
Conference NameInternational Conference on Robotics and Automation (ICRA)
Date Published05/2015
Abstract

Maps used for navigation often include a database of location descriptions for place recognition (loop closing), which permits bounded-error performance. A standard posegraph SLAM system adds a new entry for every new pose into the location database, which grows linearly and unbounded in time and thus becomes unsustainable. To address this issue, in this paper we propose 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 as well as the vehicle motion. In particular, we introduce 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 loop-closure events to occur at that location. While finding the optimal reduced location database is NPhard, we develop an efficient greedy algorithm to sort all the locations in a map based on their relative utility without access to sensor measurements or the vehicle trajectory. This enables pre-determination of a generic, limited-size place-recognition database containing the N best locations in the environment. To validate the proposed approach, we develop an open-source street-map simulator using real city-map data and show that an accurate map (pose-graph) can be attained even when using a place-recognition database with only 1% of the entries of the corresponding full database.

PDF: