# US 11,068,516 B2 · High definition map and route storage management system for autonomous vehicles > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,068,516 B2 - Document ID: US11068516B2 - Status: Granted - Kind: B2 - Application number: 16/786,835 - Filed: 2020-02-10 - Published: 2020-09-10 - Granted: 2021-07-20 - Earliest claimed: 2016-12-30 - Assignees: Deepmap Inc. - Applicants: DeepMap Inc. - Inventors: Mark Damon Wheeler - Web page: https://patentgrep.com/patent/US11068516B2 ## CPC - G06F 16/29: Geographical information databases - G01C 21/3881: {Tile-based structures} - G01C 21/3889: {Transmission of selected map data, e.g. depending on route} - G05D 1/00: Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots (drive control systems specially adapted for autonomous road vehicles B60W60/00) - G05D 1/0212: {with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287)} - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - G06F 9/54: Interprogram communication - G06F 12/0811: with multilevel cache hierarchies - G06F 12/0875: with dedicated cache, e.g. instruction or stack - G06F 2212/1016: Performance improvement - G06F 2212/1024: Latency reduction - G06F 2212/283: Plural cache memories - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES ## Abstract High definition maps for autonomous vehicles are very high resolution and detailed, and hence require storage of a great deal of data. A vehicle computing system provides multi-layered caching makes this data usable in a system that requires very low latency on every operation. The system determines which routes are most likely to be driven in the near future by the car, and ensures that the route is cached on the vehicle before beginning the route. The system provides efficient formats for moving map data from server to car and for managing the on-car disk. The system further provides real-time accessibility of nearby map data as the car moves, while providing data access at optimal speeds. ## Claims ### Claim 1 A method of caching high-definition (HD) map data by a vehicle comprising: storing, by a vehicle, a plurality of map tiles, each map tile representing a portion of the HD map data; determining a location of the vehicle based on sensor data; predicting movement of the vehicle within a threshold time interval from the location; determining a subset of map tiles based on the location and the predicted movement, each map tile of the subset of map tiles corresponding to a portion of a route that the vehicle is likely to drive through within the threshold time interval; loading the subset of map tiles in the RAM; and providing access to the subset of map tiles loaded in the RAM during navigation of the vehicle along the route. ### Claim 2 (depends on 1) The method of claim 1, further comprising loading the subset of map tiles from a first cache of decompressed map tiles. ### Claim 3 (depends on 2) The method of claim 2, further comprising: obtaining a compressed subset of map tiles from a second cache of compressed map tiles; decompressing the compressed subset of map tiles to obtain the subset of map tiles; and storing the decompressed subset of map tiles in the first cache. ### Claim 4 (depends on 1) The method of claim 1, wherein predicting the movement of the vehicle is based on localization data of the vehicle obtained at a plurality of time intervals. ### Claim 5 (depends on 4) The method of claim 4, further comprising determining the localization data based on the sensor data and the HD map data. ### Claim 6 (depends on 1) The method of claim 1, wherein the sensor data is obtained from one or more sensors selected from a group of sensors comprising: a detection and ranging sensor; a Global Positioning System (GPS) receiver, a camera, and an inertial measurement unit (IMU). ### Claim 7 (depends on 1) The method of claim 1, wherein determining the subset of map tiles based on the location and the predicted movement further comprises: identifying, based on the location, a first map tile in which the vehicle is currently located; and determining a second map tile adjacent to the first map tile that is located with respect to the first map tile according to the predicted movement, wherein the first map tile and the second map tile are included in the subset of map tiles. ### Claim 8 One or more non-transitory computer-readable storage media having instructions stored thereon that, in response to being executed by one or more processors, cause a system to perform operations comprising: storing, by a vehicle, a plurality of map tiles, each map tile representing a portion of Hight Definition (HD) map data; determining a location of the vehicle based on sensor data; predicting movement of the vehicle within a threshold time interval from the location; determining a subset of map tiles based on the location and the predicted movement, each map tile of the subset of map tiles corresponding to a portion of a route that the vehicle is likely to drive through within the threshold time interval; loading the subset of map tiles in the RAM; and providing access to the subset of map tiles loaded in the RAM during navigation of the vehicle along the route. ### Claim 9 (depends on 8) The one or more non-transitory computer-readable storage media of claim 8, the operations further comprising loading the subset of map tiles from a first cache of decompressed map tiles. ### Claim 10 (depends on 9) The one or more non-transitory computer-readable storage media of claim 9, the operations further comprising: obtaining a compressed subset of map tiles from a second cache of compressed map tiles; decompressing the compressed subset of map tiles to obtain the subset of map tiles; and storing the decompressed subset of map tiles in the first cache. ### Claim 11 (depends on 8) The one or more non-transitory computer-readable storage media of claim 8, wherein predicting the movement of the vehicle is based on localization data of the vehicle obtained at a plurality of time intervals. ### Claim 12 (depends on 11) The one or more non-transitory computer-readable storage media of claim 11, the operations further comprising determining the localization data based on the sensor data and the HD map data. ### Claim 13 (depends on 8) The one or more non-transitory computer-readable storage media of claim 8, wherein the sensor data is obtained from one or more sensors selected from a group of sensors comprising: a detection and ranging sensor; a Global Positioning System (GPS) receiver, a camera, and an inertial measurement unit (IMU). ### Claim 14 (depends on 8) The one or more non-transitory computer-readable storage media of claim 8, wherein determining the subset of map tiles based on the location and the predicted movement further comprises: identifying, based on the location, a first map tile in which the vehicle is currently located; and determining a second map tile adjacent to the first map tile that is located with respect to the first map tile according to the predicted movement, wherein the first map tile and the second map tile are included in the subset of map tiles. ### Claim 15 A system comprising: one or more processors; and one or more non-transitory computer-readable storage media having instructions stored thereon that, in response to being executed by the one or more processors, cause the system to perform operations comprising: storing, by a vehicle, a plurality of map tiles, each map tile representing a portion of High Definition (HD) map data; determining a location of the vehicle based on sensor data; predicting movement of the vehicle within a threshold time interval from the location; determining a subset of map tiles based on the location and the predicted movement, each map tile of the subset of map tiles corresponding to a portion of a route that the vehicle is likely to drive through within the threshold time interval; loading the subset of map tiles in the RAM; and providing access to the subset of map tiles loaded in the RAM during navigation of the vehicle along the route. ### Claim 16 (depends on 15) The system of claim 15, the operations further comprising loading the subset of map tiles from a first cache of decompressed map tiles. ### Claim 17 (depends on 16) The system of claim 16, the operations further comprising: obtaining a compressed subset of map tiles from a second cache of compressed map tiles; decompressing the compressed subset of map tiles to obtain the subset of map tiles; and storing the decompressed subset of map tiles in the first cache. ### Claim 18 (depends on 15) The system of claim 15, wherein predicting the movement of the vehicle is based on localization data of the vehicle obtained at a plurality of time intervals. ### Claim 19 (depends on 18) The system of claim 18, the operations further comprising determining the localization data based on the sensor data and the HD map data. ### Claim 20 (depends on 15) The system of claim 15, wherein the sensor data is obtained from one or more sensors selected from a group of sensors comprising: a detection and ranging sensor; a Global Positioning System (GPS) receiver, a camera, and an inertial measurement unit (IMU). ### Claim 21 (depends on 15) The system of claim 15, wherein determining the subset of map tiles based on the location and the predicted movement further comprises: identifying, based on the location, a first map tile in which the vehicle is currently located; and determining a second map tile adjacent to the first map tile that is located with respect to the first map tile according to the predicted movement, wherein the first map tile and the second map tile are included in the subset of map tiles.