# US 12,181,305 B2 · Methods and systems for generating lane line and road edge data using empirical path distributions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,181,305 B2 - Document ID: US12181305B2 - Status: Granted - Kind: B2 - Application number: 17/819,881 - Filed: 2022-08-15 - Published: 2024-02-15 - Granted: 2024-12-31 - Earliest claimed: 2022-08-15 - Assignees: GM Global Technology Operations LLC - Applicants: GM Global Technology Operations LLC - Inventors: Samuel Walker Beck; Benjamin Isaacoff; Matthew Kelly Titsworth; Jasmine Kuo - Web page: https://patentgrep.com/patent/US12181305B2 ## CPC - G01C 21/3819: {Road shape data, e.g. outline of a route} - G01C 21/3822: {Road feature data, e.g. slope data} - B60W 60/001: {Planning or execution of driving tasks} - B60W 2420/403: Image sensing, e.g. optical camera - B60W 2520/00: Input parameters relating to overall vehicle dynamics - B60W 2552/53: Road markings, e.g. lane marker or crosswalk - B60W 2556/40: High definition maps - 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) - B60W: CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT ## Abstract Systems and method are provided for defining map data used in controlling a vehicle. In one embodiment, a method includes: receiving, by a processor, telemetry data; determining, by the processor, distribution data of a path based on the telemetry data; determining, by the processor, a plurality of sample data based on a trained machine learning model and the distribution data; generating, by the processor, at least one of lane line data and road edge data based on the sample data and a second machine learning model; and storing, by the processor, the map data including the lane line data and road edge data for use in controlling the vehicle. ## Claims ### Claim 1 A method of generating map data for use in controlling a vehicle, the method comprising: receiving, by a processor, telemetry data; determining, by the processor, distribution data of a path based on the telemetry data, including by: determining information for a transition graph by counting a number of paths visit each pair of nodes in sequence, and including an edge for each pair of nodes that occurs more than a threshold number of times relative to a total number of path; and initializing, for each node, a conditional distribution to describe a log likelihood of each successor node, and initializing, for each edge between a source node and a target node, a conditional distribution to describe a log likelihood of a position, a speed, a heading, and a time difference at the target node according to a position, a speed, and a heading at the source node; determining, by the processor, sample data based on a first machine learning model and the distribution data; generating, by the processor, both lane line data and road edge data based on the sample data and a second machine learning model; assembling, the via the processor, the telemetry data into a path of points that the vehicle has travelled along a road segment and the path is associated with a plurality of lines that are normal to the road segment, wherein the normal lines are equally spaced according to defined increments along the road segment; defining, via the processor, each intersection of a path with a normal line as a node of the transition graph; generating, via the processor, the transition graph by evaluating multiple paths generated for the road segment from a plurality of vehicles; generating, via the processor, the map data using the transition graph; and storing, by the processor, the map data including the lane line data and road edge data and controlling the vehicle based on the map data. ### Claim 2 (depends on 1) The method of claim 1, wherein the telemetry data includes a position, a speed, a heading, and a time difference observed from an area in an environment. ### Claim 3 (depends on 1) The method of claim 1, wherein the second machine learning model includes a convolutional neural network, and wherein the first machine learning model includes an expectation maximization model. ### Claim 4 (depends on 1) The method of claim 1, wherein the method further comprises using an expectation maximization model to train the distribution data according to the telemetry data. ### Claim 5 (depends on 1) The method of claim 1, wherein the method further comprises controlling the vehicle based on the map data. ### Claim 6 (depends on 1) The method of claim 1, wherein the determining the plurality of sample data comprises sampling the distribution data by repeatedly choosing a successor node from a plurality of nodes according to a log likelihood at a current node, and selecting parameters according to the distribution data on an edge corresponding to the successor node. ### Claim 7 (depends on 6) The method of claim 6, wherein the determining the plurality of sample data comprises repeating the choosing and selecting a plurality of times to produce density image data comprising a density image. ### Claim 8 (depends on 7) The method of claim 7, further comprising: processing, via the processor, the density image data, including the density image, with a trained convolutional neural network (CNN) model to produce predictions of positions of the lane lines and road edges, and incorporating the predictions in the map data for use in controlling the vehicle. ### Claim 9 A vehicle, comprising: an autonomous driving system configured to control the vehicle based on map data; and a map definition module configured to, by a processor: receive telemetry data; determine distribution data of a path based on the telemetry data, including by: determining information for a transition graph by counting a number of paths visit each pair of nodes in sequence, and including an edge for each pair of nodes that occurs more than a threshold number of times relative to a total number of path; and initializing, for each node, a conditional distribution to describe a log likelihood of each successor node, and initializing, for each edge between a source node and a target node, a conditional distribution to describe a log likelihood of a position, a speed, a heading, and a time difference at the target node according to a position, a speed, and a heading at the source node; determine a plurality of sample data based on a first machine learning model and the distribution data; generate both line data and road edge data based on the sample data and a second machine learning model; assemble the telemetry data into a path of points that the vehicle has travelled along a road segment and the path is associated with a plurality of lines that are normal to the road segment, wherein the normal lines are equally spaced according to defined increments along the road segment; define each intersection of a path with a normal line as a node of the transition graph; generate the transition graph by evaluating multiple paths generated for the road segment from a plurality of vehicles; generate the map data using the transition graph; and store the map data including the lane line data and road edge data and control the vehicle using the map data. ### Claim 10 (depends on 9) The vehicle of claim 9, wherein the processor is further configured to process the density image data, including the density image, with a trained convolutional neural network (CNN) model to produce predictions of positions of the lane lines and road edges, and incorporating the predictions in the map data for use in controlling the vehicle. ### Claim 11 A computer implemented system for generating map data used in controlling a vehicle, the system comprising: a non-transitory computer readable medium configured to store instructions; and a processor configured to perform the instructions in order to carry out a method, the method comprising: receiving, by a processor, telemetry data; determining, by the processor, distribution data of a path based on the telemetry data, including by: determining information for a transition graph by counting a number of paths visit each pair of nodes in sequence, and including an edge for each pair of nodes that occurs more than a threshold number of times relative to a total number of path; and initializing, for each node, a conditional distribution to describe a log likelihood of each successor node, and initializing, for each edge between a source node and a target node, a conditional distribution to describe a log likelihood of a position, a speed, a heading, and a time difference at the target node according to a position, a speed, and a heading at the source node; determining, by the processor, a plurality of sample data based on a first machine learning model and the distribution data; generating, by the processor, both lane line data and road edge data based on the sample data and a second machine learning model; assembling, the via the processor, the telemetry data into a path of points that the vehicle has travelled along a road segment and the path is associated with a plurality of lines that are normal to the road segment, wherein the normal lines are equally spaced according to defined increments along the road segment; defining, via the processor, each intersection of a path with a normal line as a node of the transition graph; generating, via the processor, the transition graph by evaluating multiple paths generated for the road segment from a plurality of vehicles; generating, via the processor, the map data using the transition graph; and storing, by the processor, the map data including the lane line data and road edge data and controlling the vehicle based on the map data. ### Claim 12 (depends on 11) The system of claim 11, wherein the telemetry data includes a position, a speed, a heading, and a time difference observed from an area in an environment. ### Claim 13 (depends on 11) The system of claim 11, wherein the second machine learning model is a convolutional neural network. ### Claim 14 (depends on 11) The system of claim 11, wherein the threshold number of times is relative to a total number of paths. ### Claim 15 (depends on 11) The system of claim 11, wherein the processor is further configured to process the density image data, including the density image, with a trained convolutional neural network (CNN) model to produce predictions of positions of the lane lines and road edges, and incorporating the predictions in the map data for use in controlling the vehicle. ### Claim 16 (depends on 11) The system of claim 11, wherein the method further comprises using expectation maximization to train the distribution data according to the telemetry data. ### Claim 17 (depends on 11) The system of claim 11, wherein the determining the plurality of sample data comprises sampling the distribution data by repeatedly choosing a successor node from a plurality of nodes according to a log likelihood at a current node, and selecting parameters according to the distribution data on an edge corresponding to the successor node. ### Claim 18 (depends on 17) The system of claim 17, wherein the determining the plurality of sample data comprises repeating the choosing and the selecting a plurality of times to produce density image data comprising a density image.