Location utility-based map reduction
Maps used for navigation often include a database of location descriptions for place recognition (loop closing), which permits bounded-error performance. A standard pose-graph SLAM system adds a new entry for every new pose into the location database, which grows linearly and unbounded in time and t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2017
|
| Online Access: | http://hdl.handle.net/1721.1/107401 https://orcid.org/0000-0002-8863-6550 |
| _version_ | 1826188757892595712 |
|---|---|
| author | Steiner, Ted J Huang, Guoquan Leonard, John J |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Steiner, Ted J Huang, Guoquan Leonard, John J |
| author_sort | Steiner, Ted J |
| collection | MIT |
| description | Maps used for navigation often include a database of location descriptions for place recognition (loop closing), which permits bounded-error performance. A standard pose-graph 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 NP-hard, 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. |
| first_indexed | 2024-09-23T08:04:35Z |
| format | Article |
| id | mit-1721.1/107401 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:04:35Z |
| publishDate | 2017 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/1074012022-09-23T10:44:50Z Location utility-based map reduction Steiner, Ted J Huang, Guoquan Leonard, John J Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Mechanical Engineering Steiner, Ted J Huang, Guoquan Leonard, John J Maps used for navigation often include a database of location descriptions for place recognition (loop closing), which permits bounded-error performance. A standard pose-graph 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 NP-hard, 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. Charles Stark Draper Laboratory (Fellowship) 2017-03-13T16:27:54Z 2017-03-13T16:27:54Z 2015-07 2015-05 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-6923-4 978-1-4799-6924-1 978-1-4799-6922-7 INSPEC Accession Number: 15286382 http://hdl.handle.net/1721.1/107401 Steiner, Ted J., Guoquan Huang, and John J. Leonard. “Location Utility-Based Map Reduction.” 2015 IEEE International Conference on Robotics and Automation (ICRA) (May 2015). https://orcid.org/0000-0002-8863-6550 en_US http://dx.doi.org/10.1109/ICRA.2015.7139223 Proceeding of the 2015 IEEE International Conference on Robotics and Automation (ICRA) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers MIT Web Domain |
| spellingShingle | Steiner, Ted J Huang, Guoquan Leonard, John J Location utility-based map reduction |
| title | Location utility-based map reduction |
| title_full | Location utility-based map reduction |
| title_fullStr | Location utility-based map reduction |
| title_full_unstemmed | Location utility-based map reduction |
| title_short | Location utility-based map reduction |
| title_sort | location utility based map reduction |
| url | http://hdl.handle.net/1721.1/107401 https://orcid.org/0000-0002-8863-6550 |
| work_keys_str_mv | AT steinertedj locationutilitybasedmapreduction AT huangguoquan locationutilitybasedmapreduction AT leonardjohnj locationutilitybasedmapreduction |