High definition map and route storage management system for autonomous vehicles

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-care disk. The system further provides real-time accessibility of nearby map data as the car moves, while providing data access at optimal speeds.

What is claimed is: 
     
       1. A method of caching high-definition map data by an autonomous vehicle comprising:
 sending, by the autonomous vehicle to an online system, information describing a route to be traveled by the autonomous vehicle; 
 receiving a plurality of compressed map tiles from the online system by the autonomous vehicle, wherein each compressed map tile of the plurality of compressed map tiles comprises a section of the three-dimensional map corresponding to a portion of the route; 
 decompressing the plurality of compressed map tiles into a plurality of accessible map tiles; 
 determining localization data describing a position of the autonomous vehicle, wherein the position of the autonomous vehicle corresponds to a first portion of the route; 
 identifying a first accessible map tile corresponding to a current section of the three-dimensional map based in part on the localization data; 
 loading the first accessible map tile in a random-access memory (RAM), wherein the RAM stores accessible map tiles for utilization in driving the autonomous vehicle along the route; 
 determining a first subset of accessible map tiles based in part on the localization data, each accessible map tile of the first subset of accessible map tiles corresponding to a second portion of the route that the autonomous vehicle is likely to drive through within a threshold time interval, wherein the localization data further comprises a velocity of the autonomous vehicle and wherein determining the first subset of accessible map tiles comprises:
 determining a predicted route based on the localization data, wherein the predicted route is predicted movement of the autonomous vehicle calculated from the autonomous vehicle driving with the velocity after a time interval from the position of the autonomous vehicle; and 
 identifying accessible map tiles based on the predicted route; 
 
 loading the first subset of accessible map tiles in the RAM; and 
 providing control signals to vehicle controls of the autonomous vehicle to navigate the autonomous vehicle along the route, the control signals determined by accessing data of the first subset of accessible map tiles from the RAM. 
 
     
     
       2. The method of  claim 1 , wherein each section of the three-dimensional map corresponding to a portion of the route overlaps with one or more other sections of the three-dimensional map which are adjacent to that section. 
     
     
       3. The method of  claim 1 , wherein receiving a plurality of compressed map tiles from the online system by the autonomous vehicle comprises storing the plurality of compressed map tiles in a first cache memory. 
     
     
       4. The method of  claim 3 , wherein decompressing the plurality of compressed map tiles into a plurality of accessible map tiles comprises storing the plurality of accessible map tiles in a second cache memory, wherein the accessible map tiles are loaded from the second cache memory into the RAM, wherein the second cache memory has a faster access time than the first cache memory. 
     
     
       5. The method of  claim 1 , wherein decompressing the plurality of compressed map tiles into a plurality of accessible map tiles comprises partitioning each accessible map tile into a plurality of sub-sections. 
     
     
       6. The method of  claim 5 , wherein all sub-sections of accessible map tiles are partitioned in a grid with each sub-section indexed with coordinates of the grid. 
     
     
       7. The method of  claim 5 , accessing the first accessible map tile from the RAM for use in driving the autonomous vehicle along the route comprises accessing a sub-section of the first accessible map tile based at least in part on the localization data. 
     
     
       8. The method of  claim 1 , wherein determining localization data describing a position of the autonomous vehicle, wherein the position of the autonomous vehicle corresponds to a first portion of the route comprises receiving a set of coordinates of the autonomous vehicle by a detection and ranging sensor mounted on the autonomous vehicle. 
     
     
       9. The method of  claim 1 , wherein determining a first subset of accessible map tiles based in part on the localization data comprises identifying accessible map tiles each having a proximity to the position of the autonomous vehicle under a threshold distance. 
     
     
       10. The method of  claim 1 , wherein determining a first subset of accessible map tiles based in part on the localization data further comprises:
 identifying a lane within the first accessible map tile in which the autonomous vehicle is based on the position of the autonomous vehicle in the first accessible map tile, wherein the lane is associated with one or more accessible map tiles which are potential routes from the lane; and 
 determining the first subset of accessible map tiles based in part on the lane. 
 
     
     
       11. A non-transitory computer-readable storage medium with encoded instructions to cache high-definition map data by an autonomous vehicle that, when executed by a processor, cause the processor to:
 send, by the autonomous vehicle to an online system, information describing a route to be traveled by an autonomous vehicle associated with the autonomous vehicle; 
 receive a plurality of compressed map tiles from the online system by the autonomous vehicle, wherein each compressed map tile of the plurality of compressed map tiles comprises a section of the three-dimensional map corresponding to a portion of the route; 
 decompress the plurality of compressed map tiles into a plurality of accessible map tiles; 
 determine localization data describing a position of the autonomous vehicle, wherein the position of the autonomous vehicle corresponds to a first portion of the route; 
 identify a first accessible map tile corresponding to a current section of the three-dimensional map based in part on the localization data; 
 load the first accessible map tile in a random-access memory (RAM), wherein the RAM stores accessible map tiles for utilization in driving the autonomous vehicle along the route; 
 determine a first subset of accessible map tiles based in part on the localization data, each accessible map tile of the first subset of accessible map tiles corresponding to a second portion of the route that the autonomous vehicle is likely to drive through within a threshold time interval, wherein the localization data further comprises a velocity of the autonomous vehicle and wherein the instructions to determine the first subset of accessible map tiles cause the processor to:
 determine a predicted route based on the localization data, wherein the predicted route is predicted movement of the autonomous vehicle calculated from the autonomous vehicle driving with the velocity after a time interval from the position of the autonomous vehicle; and 
 identify accessible map tiles based on the predicted route; 
 
 load the first subset of accessible map tiles in the RAM; and 
 provide control signals to vehicle controls of the autonomous vehicle to navigate the autonomous vehicle along the route, the control signals determined by accessing the first subset of accessible map tiles from the RAM. 
 
     
     
       12. The non-transitory computer-readable storage medium of  claim 11 , wherein each section of the three-dimensional map corresponding to a portion of the route overlaps with one or more other sections of the three-dimensional map which are adjacent to that section. 
     
     
       13. The non-transitory computer-readable storage medium of  claim 11 , wherein to receive a plurality of compressed map tiles from the online system by the autonomous vehicle comprises further instructions that, when executed by the processor, cause the processor to store the plurality of compressed map tiles in a first cache memory. 
     
     
       14. The non-transitory computer-readable storage medium of  claim 13 , wherein to decompress the plurality of compressed map tiles into a plurality of accessible map tiles comprises further instructions that, when executed by the processor, cause the processor to store the plurality of accessible map tiles in a second cache memory, wherein the accessible map tiles are loaded from the second cache memory into the RAM, wherein the second cache memory has a faster access time than the first cache memory. 
     
     
       15. The non-transitory computer-readable storage medium of  claim 11 , wherein to decompress the plurality of compressed map tiles into a plurality of accessible map tiles comprises further instructions that, when executed by the processor, cause the processor to partition each accessible map tile into a plurality of sub-sections. 
     
     
       16. The non-transitory computer-readable storage medium of  claim 15 , wherein all sub-sections of accessible map tiles are partitioned in a grid with each sub-section indexed with coordinates of the grid. 
     
     
       17. The non-transitory computer-readable storage medium of  claim 15 , wherein to access the first accessible map tile from the RAM for use in driving the autonomous vehicle along the route comprises further instructions that, when executed by the processor, cause the processor to access a sub-section of the first accessible map tile based at least in part on the localization data. 
     
     
       18. The non-transitory computer-readable storage medium of  claim 11 , wherein to determine a first subset of accessible map tiles based in part on the localization data comprises further instructions that, when executed by the processor, cause the processor to identify accessible map tiles each having a proximity to the position of the autonomous vehicle under a threshold distance. 
     
     
       19. The non-transitory computer-readable storage medium of  claim 11 , wherein to determine localization data describing a position of the autonomous vehicle, wherein the position of the autonomous vehicle corresponds to a first portion of the route comprises further instructions that, when executed by the processor, cause the processor to receive a set of coordinates of the autonomous vehicle by a detection and ranging sensor mounted on the autonomous vehicle. 
     
     
       20. The non-transitory computer-readable storage medium of  claim 11 , wherein to determine a first subset of accessible map tiles based in part on the localization data comprises further instructions that, when executed by the processor, cause the processor to:
 identify a lane within the first accessible map tile in which the autonomous vehicle is based on the position of the autonomous vehicle in the first accessible map tile, wherein the lane is associated with one or more accessible map tiles which are potential routes from the lane; and 
 determine the first subset of accessible map tiles based in part on the lane. 
 
     
     
       21. A computer system comprising:
 an electronic processor; and 
 a non-transitory computer-readable storage medium with encoded instructions to cache high-definition map data by an autonomous vehicle that, when executed by a processor, cause the processor to:
 send, by the autonomous vehicle to an online system, information describing a route to be traveled by an autonomous vehicle associated with the autonomous vehicle; 
 receive a plurality of compressed map tiles from the online system by the autonomous vehicle, wherein each compressed map tile of the plurality of compressed map tiles comprises a section of the three-dimensional map corresponding to a portion of the route; 
 decompress the plurality of compressed map tiles into a plurality of accessible map tiles; 
 determine localization data describing a position of the autonomous vehicle, wherein the position of the autonomous vehicle corresponds to a first portion of the route; 
 identify a first accessible map tile corresponding to a current section of the three-dimensional map based in part on the localization data; 
 load the first accessible map tile in a random-access memory (RAM), wherein the RAM stores accessible map tiles for utilization in driving the autonomous vehicle along the route; 
 determine a first subset of accessible map tiles based in part on the localization data, each accessible map tile of the first subset of accessible map tiles corresponding to a second portion of the route that the autonomous vehicle is likely to drive through within a threshold time interval, wherein the localization data further comprises a velocity of the autonomous vehicle, wherein the instructions to determine the first subset of accessible map tiles cause the processor to:
 determine a predicted route based on the localization data, wherein the predicted route is predicted movement of the autonomous vehicle calculated from the autonomous vehicle driving with the velocity after a time interval from the position of the autonomous vehicle; and 
 identify accessible map tiles based on the predicted route; 
 
 load the first subset of accessible map tiles in the RAM; and 
 provide control signals to vehicle controls of the autonomous vehicle to navigate the autonomous vehicle along the route, the control signals determined by accessing the first subset of accessible map tiles from the RAM. 
 
 
     
     
       22. The computer system of  claim 21 , wherein each section of the three-dimensional map corresponding to a portion of the route overlaps with one or more other sections of the three-dimensional map which are adjacent to that section. 
     
     
       23. The computer system of  claim 21 , wherein to receive a plurality of compressed map tiles from the online system by the autonomous vehicle comprises further instructions that, when executed by the processor, cause the processor to store the plurality of compressed map tiles in a first cache memory. 
     
     
       24. The computer system of  claim 23 , wherein to decompress the plurality of compressed map tiles into a plurality of accessible map tiles comprises further instructions that, when executed by the processor, cause the processor to store the plurality of accessible map tiles in a second cache memory, wherein the accessible map tiles are loaded from the second cache memory into the RAM, wherein the second cache memory has a faster access time than the first cache memory. 
     
     
       25. The computer system of  claim 21 , wherein to decompress the plurality of compressed map tiles into a plurality of accessible map tiles comprises further instructions that, when executed by the processor, cause the processor to partition each accessible map tile into a plurality of sub-sections. 
     
     
       26. The computer system of  claim 25 , wherein all sub-sections of accessible map tiles are partitioned in a grid with each sub-section indexed with coordinates of the grid. 
     
     
       27. The computer system of  claim 25 , wherein to access the first accessible map tile from the RAM for use in driving the autonomous vehicle along the route comprises further instructions that, when executed by the processor, cause the processor to access a sub-section of the first accessible map tile based at least in part on the localization data. 
     
     
       28. The computer system of  claim 21 , wherein to determine a first subset of accessible map tiles based in part on the localization data comprises further instructions that, when executed by the processor, cause the processor to identify accessible map tiles each having a proximity to the position of the autonomous vehicle under a threshold distance. 
     
     
       29. The computer system of  claim 21 , wherein to determine localization data describing a position of the autonomous vehicle, wherein the position of the autonomous vehicle corresponds to a first portion of the route comprises further instructions that, when executed by the processor, cause the processor to receive a set of coordinates of the autonomous vehicle by a detection and ranging sensor mounted on the autonomous vehicle. 
     
     
       30. The computer system of  claim 21 , wherein to determine a first subset of accessible map tiles based in part on the localization data comprises further instructions that, when executed by the processor, cause the processor to:
 identify a lane within the first accessible map tile in which the autonomous vehicle is based on the position of the autonomous vehicle in the first accessible map tile, wherein the lane is associated with one or more accessible map tiles which are potential routes from the lane; and 
 determine the first subset of accessible map tiles based in part on the lane.