# US 10,845,820 B2 · Route generation using high definition maps 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 10,845,820 B2 - Document ID: US10845820B2 - Status: Granted - Kind: B2 - Application number: 15/853,614 - Filed: 2017-12-22 - Published: 2018-07-05 - Granted: 2020-11-24 - Earliest claimed: 2016-12-30 - Assignees: Deepmap Inc. - Applicants: DeepMap Inc. - Inventors: Mark Damon Wheeler - Web page: https://patentgrep.com/patent/US10845820B2 ## CPC - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - G01C 21/30: Map- or contour-matching - G01C 21/3658: {Lane guidance} - G01C 21/3815: {Road data} - G01C 21/3819: {Road shape data, e.g. outline of a route} - G01C 21/3826: {Terrain data} - G01C 21/3867: {Geometry of map features, e.g. shape points, polygons or for simplified maps} - G05D 1/0276: {using signals provided by a source external to the vehicle (involving a plurality of vehicles G05D1/0287; automatically controlling vehicle speed responsive to externally generated signals B60K31/0058)} - G06F 16/29: Geographical information databases - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 16/9537: Spatial or temporal dependent retrieval, e.g. spatiotemporal queries - G08G 1/0112: {from the vehicle, e.g. floating car data [FCD]} - G08G 1/0129: {for creating historical data or processing based on historical data} - G08G 1/0141: {for traffic information dissemination} - G08G 1/04: using optical or ultrasonic detectors - G08G 1/096822: {where the segments of the route are transmitted to the vehicle at different locations and times} - G08G 1/09685: {where the complete route is computed only once and not updated} - G08G 1/0969: having a display in the form of a map - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - 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) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) ## Abstract A system generates a high definition map for an autonomous vehicle to travel from a source location to a destination location. The system determines a low resolution route and receives high definition map data for a set of geographical regions overlaying the low resolution route. The system uses lane elements within the geographical regions to form a set of potential partial routes. The system calculates the error between the potential partial route and the low resolution route and removes potential partial routes with errors above the threshold. Once completed, the system selects a final route and sends signals to the controls of the autonomous vehicle to follow the final route. The system determines whether surface areas adjacent to a lane that are not part of the road are safe for the vehicle to drive in case of emergency. The system stores information describing navigable surface areas with representations of lanes. ## Claims ### Claim 1 A non-transitory computer readable storage medium having instructions for determining a route using a high definition map encoded thereon that, when executed by a processor, cause the processor to perform operations comprising: receiving, by an autonomous vehicle, a low resolution route from a source address to a destination address, the low resolution route identifying a set of streets for traveling from the source address to the destination address, wherein each street comprises one or more lanes; receiving a representation of a lane element graph of high definition map data, the lane element graph comprising nodes representing lane elements of the one or more lanes and edges representing connections between lane elements; determining a high resolution route between the source address and the destination address based on a set of potential partial routes to an intermediate point of the low resolution route between the source address and the destination address, each partial route being generated based on connecting the lane elements of the lane element graph and represented as a sequence of connected lane elements of the lane element graph, the determining comprising repeatedly performing steps of: selecting a potential partial route from the set of potential partial routes; identifying from the lane element graph, an additional lane element connected to a lane element of the selected potential partial route; determining a measure of error that represents a locational difference between the low resolution route and a modified partial route obtained by adding the additional lane element to the selected potential partial route; and responsive to the measure of error being below a threshold value, replacing the selected partial route with the modified partial route and updating the threshold value to the measure of error for the modified partial route; determining a potential completed route based on a particular potential partial route from the set of potential partial routes connecting the source address to the destination address; and selecting the potential completed route as the high resolution route, responsive to the potential completed route having a measure of error less than any other potential completed route or potential partial route. ### Claim 2 (depends on 1) The non-transitory computer readable medium of claim 1, wherein the low resolution map is represented as a navigation map generated by a third party map provider, the navigation map comprising geocoded instructions for a route from the source address to the destination address. ### Claim 3 (depends on 2) The non-transitory computer readable medium of claim 2, wherein the received navigation map is based on latitude-longitude coordinates. ### Claim 4 (depends on 1) The non-transitory computer readable medium of claim 1, wherein the edge between a first lane element and a second lane element indicates a physical proximity between the lane elements, over which a vehicle may travel directly from a portion of a street corresponding to the first lane element to a portion of a street corresponding to the second lane element. ### Claim 5 (depends on 1) The non-transitory computer readable medium of claim 1, wherein a lane element comprises one or more of: geometric lane boundaries; a direction of traffic within the lane compared to the high resolution route; static traffic flow restrictions; or non-traffic road features. ### Claim 6 (depends on 1) The non-transitory computer readable medium of claim 1, further comprising: retrieving representations of one or more geographical regions overlapping the low resolution route from an online server, each representation of a geographical region comprising a plurality lane elements and relations between lane elements. ### Claim 7 (depends on 1) The non-transitory computer readable medium of claim 1, further comprising: sending information describing geocoded instructions of the low resolution route to an online server; and receiving one or more geographical regions through which the low resolution route passes. ### Claim 8 (depends on 1) The non-transitory computer readable medium of claim 1, further comprising: responsive to the measure of error being above the threshold value, rejecting the additional lane element, wherein the threshold value is not updated; and identifying, from the lane element graph, an alternate additional lane element connected to a lane element of the partial route. ### Claim 9 (depends on 1) The non-transitory computer readable medium of claim 1, further comprising: responsive to determining that no other additional lane element connected to the potential partial route results in a modified partial route has an error below the threshold value, removing the selected potential partial route from the set of potential partial routes; and selecting a second potential partial route from the set of potential partial routes. ### Claim 10 (depends on 1) The non-transitory computer readable medium of claim 1, wherein the measure of error represents the perpendicular distance between lane elements along the length of the potential partial route and the low resolution route. ### Claim 11 (depends on 1) The non-transitory computer readable medium of claim 1, wherein determining the measure of error further comprises: establishing the threshold value, the threshold value representing the maximum allowable perpendicular distance between a potential partial route and the low resolution route; identifying additional lane elements that may be added to the partial route; and computing the measure of error for each possible additional lane element. ### Claim 12 (depends on 11) The non-transitory computer readable medium of claim 11, wherein the measure of error is determined for each modified partial route and the threshold value is updated to represent a lowest measure of error for a potential completed route. ### Claim 13 (depends on 1) The non-transitory computer readable medium of claim 1, wherein responsive to identifying a plurality of additional lane elements for adding to a potential partial route: determining a plurality of modified partial routes, each modified partial route obtained by adding an additional lane to the potential partial route; and adding the modified partial routes to the plurality of potential partial routes responsive to determining that the modified partial route has a measure of error below a current updated threshold value. ### Claim 14 A method for determining a route using a high definition map comprising: receiving, by an autonomous vehicle, a low resolution route from a source address to a destination address, the low resolution route identifying a set of streets for traveling from the source address to the destination address, wherein each street comprises one or more lanes; receiving a representation of a lane element graph of high definition map data, the lane element graph comprising nodes representing lane elements of the one or more lanes and edges representing connections between lane elements; determining a high resolution route between the source address and the destination address based on a set of potential partial routes to an intermediate point of the low resolution route between the source address and the destination address, each partial route being generated based on connecting the lane elements of the lane element graph and represented as a sequence of connected lane elements of the lane element graph, the determining comprising repeatedly performing steps of: selecting a potential partial route from the set of potential partial routes; identifying from the lane element graph, an additional lane element connected to a lane element of the selected potential partial route; determining a measure of error that represents a locational difference between the low resolution route and a modified partial route obtained by adding the additional lane element to the selected potential partial route; and responsive to the measure of error being below a threshold value, replacing the selected partial route with the modified partial route and updating the threshold value to the measure of error for the modified partial route; determining a potential completed route based on a particular potential partial route from the set of potential partial routes connecting the source address to the destination address; and selecting the potential completed route as the high resolution route, responsive to the potential completed route having a measure of error less than any other potential completed route or potential partial route. ### Claim 15 (depends on 14) The method of claim 14, wherein the low resolution map is represented as a navigation map generated by a third party map provider, the navigation map comprising geocoded instructions based on latitude and longitude coordinates for a route from the source address to the destination address. ### Claim 16 (depends on 14) The method of claim 14, wherein the edge between a first lane element and a second lane element indicates a physical proximity between the lane elements, over which a vehicle may travel directly from a portion of a street corresponding to the first lane element to a portion of a street corresponding to the second lane element. ### Claim 17 (depends on 14) The method of claim 14, further comprising, retrieving representations of one or more geographical regions overlapping the low resolution route from an online server, each representation of a geographical region comprising a plurality lane elements and relations between lane elements. ### Claim 18 (depends on 14) The method of claim 14, further comprising: responsive to the measure of error being above the threshold value, rejecting the additional lane element, wherein the measure of error represents the perpendicular distance between lane elements along the length of the potential partial route and the low resolution route, and wherein the threshold value is not updated; and identifying, from the lane element graph, an alternate additional lane element connected to a lane element of the potential partial route. ### Claim 19 (depends on 14) The method of claim 14, wherein responsive to identifying a plurality of additional lane elements for adding to a potential partial route: determining a plurality of modified partial routes, each modified partial route obtained by adding an additional lane to the potential partial route; and adding the modified partial routes to the plurality of potential partial routes responsive to determining that the modified partial route has a measure of error below a threshold value. ### Claim 20 A method for determining a route using a high definition map, the method comprising: storing a lane element graph of high definition map data, the lane element graph comprising lane elements of one or more lanes of streets and edges/nodes; storing a plurality of geographical regions, each geographical region describing a section of a world map; receiving a request from an autonomous vehicle, the request describing instructions in the form of a low resolution route from a source location to a destination; identifying geographical regions through which the low resolution route passes; determining a subset of a lane element graph for a low resolution route based on the identified geographical regions, wherein the subset of the lane element graph represents lane elements of; and sending a representation of the subset of lane element graph to the autonomous vehicle, wherein the autonomous vehicle uses the lane element graph to construct a high definition route for driving from the source location to the destination, the high definition route being constructed by connecting lane elements of the subset of the lane element graph.