# US 12,600,367 B1 · Determining point locations based on road segment approximations > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,600,367 B1 - Document ID: US12600367B1 - Status: Granted - Kind: B1 - Application number: 18/112,231 - Filed: 2023-02-21 - Granted: 2026-04-14 - Earliest claimed: 2023-02-21 - Assignees: Zoox, Inc. - Applicants: Zoox, Inc. - Inventors: Lakshay Garg; Joona Markus Petteri Kiiski - Web page: https://patentgrep.com/patent/US12600367B1 ## CPC - B60W 50/06: Improving the dynamic response of the control system, e.g. improving the speed of regulation or avoiding hunting or overshoot - G01C 21/30: Map- or contour-matching - B60W 30/09: Taking automatic action to avoid collision, e.g. braking and steering - B60W 60/001: {Planning or execution of driving tasks} - G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) - G01C 21/32: Structuring or formatting of map data - G01C 21/3461: {Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries} - G01C 21/3602: {Input other than that of destination using image analysis, e.g. detection of road signs, lanes, buildings, real preceding vehicles using a camera} - G01C 21/3819: {Road shape data, e.g. outline of a route} - B60W 2050/065: {by reducing the computational load on the digital processor of the control computer} - B60W 2554/802: Longitudinal distance - B60W 2556/40: High definition maps - 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 - 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) ## Abstract Techniques for transforming an object location from a first frame of reference to a route-relative frame of reference. A road management component may receive sensor data captured from sensor devices of a vehicle. The road management component may analyze the sensor data to determine a location of an object within the environment. The road management component may utilize a discretized map to determine a cell associated with the object location. Upon identifying the cell within which the object is located, the road management component may receive the list of road segments which may be proximate to the object. In such instances, the road management component may determine to which of the segments from the list of road segments the object is proximate. The road management component may determine how far along the reference line the object is positioned and/or how far away from the reference line the object is positioned. ## Claims ### Claim 1 A system comprising: one or more processors; and one or more non-transitory computer-readable media storing computer-executable instructions that, when executed, cause the one or more processors to perform operations comprising: receiving, from a sensor device associated with a vehicle, sensor data associated with an environment; detecting, based at least in part on the sensor data, an object in the environment; determining a location of the object within the environment, the location being defined in a first coordinate system; determining, based at least in part on the location, that the object is located within a cell of discretized map data; receiving a candidate road associated with the cell, wherein the candidate road includes a segment; determining that the object is associated with the segment; receiving, from the cell and based at least in part on determining that the object is associated with the segment, an approximation of the segment, wherein the approximation is determined at a previous time; determining, as a set of coordinates in a second coordinate system, a first distance relative to the object from a first point along the approximation and a second distance of the object relative to a second point along the approximation; and controlling the vehicle based at least in part on the first distance and the second distance. ### Claim 2 (depends on 1) The system of claim 1, wherein the first distance indicates a measurement of the object along the candidate road, the candidate road being represented as a reference line, wherein determining the first distance comprises: identifying a start point of the reference line; identifying a second segment of the reference line between the start point and the segment, wherein the second segment is associated with a second approximation; and determining, based at least in part on a sum of a first length the second approximation and at least a portion of a second length of the approximation, the first distance. ### Claim 3 (depends on 1) The system of claim 1, wherein the second coordinate system is a relative reference frame. ### Claim 4 (depends on 1) The system of claim 1, the operations further comprising: receiving a second candidate road associated with the cell, wherein the second candidate road includes a second segment and a second approximation; determining that the object is associated with the second segment; determining a third distance relative to the object from a third point along the second approximation and a fourth distance of the object relative to a fourth point along the second approximation; and controlling the vehicle based at least in part on the first distance, the second distance, the third distance, and the fourth distance. ### Claim 5 (depends on 1) The system of claim 1, wherein the discretized map data is determined based at least in part on generating a plurality of cells associated with map data, the cell being associated with the plurality of cells, wherein the cell includes a cell identifier associated with a candidate road identifier of the candidate road. ### Claim 6 One or more non transitory computer readable media storing instructions executable by one or more processors, wherein the instructions, when executed, cause the one or more processors to perform operations comprising: receiving sensor data associated with an environment; detecting, based at least in part on the sensor data, an object in the environment; determining a location of the object within the environment; determining, based at least in part on the location, that the object is located within a cell of discretized map data; receiving a candidate road associated with the cell, wherein the candidate road includes a segment; determining that the object is associated with the segment; receiving, from the cell and based at least in part on the object being associated with the segment, an approximation of the segment, wherein the approximation is determined at a previous time; determining a first distance relative to the object from a first point along the approximation and a second distance of the object relative to a second point along the approximation; and controlling a vehicle based at least in part on the first distance and the second distance. ### Claim 7 (depends on 1) The system of claim 1, wherein the approximation is determined by a remote system and stored in the cell. ### Claim 8 (depends on 6) The one or more non transitory computer readable media of claim 6, wherein the first distance indicates a measurement of the object along the candidate road, the candidate road being represented as a reference line, wherein determining the first distance comprises: identifying a start point of the reference line; identifying a second segment of the reference line between the start point and the segment, wherein the second segment is associated with a second approximation; and determining, based at least in part on a sum of a first length of the second approximation and at least a portion of a second length of the approximation, the first distance. ### Claim 9 (depends on 6) The one or more non transitory computer readable media of claim 6, wherein the first distance and the second distance are in a relative coordinate system and the location is in a Cartesian coordinate system. ### Claim 10 (depends on 6) The one or more non transitory computer readable media of claim 6, the operations further comprising: receiving a second candidate road associated with the cell, wherein the second candidate road includes a second segment and a second approximation; determining that the object is associated with the second segment; determining a third distance relative to the object from a third point along the second approximation and a fourth distance of the object relative to a fourth point along the second approximation; and controlling the vehicle based at least in part on the first distance, the second distance, the third distance, and the fourth distance. ### Claim 11 (depends on 6) The one or more non transitory computer readable media of claim 6, wherein the discretized map data is determined based at least in part on generating a plurality of cells associated with map data, the cell being associated with the plurality of cells, wherein the cell includes a cell identifier associated with a candidate road identifier of the candidate road. ### Claim 12 (depends on 6) The one or more non transitory computer readable media of claim 6, wherein the approximation is determined based at least in part on: receiving a reference line associated with the candidate road; determining a value associated with a difference between the approximation and the segment; and determining that the value is less than or equal to a threshold value. ### Claim 13 (depends on 12) The one or more non transitory computer readable media of claim 12, wherein determining the approximation further comprises: determining the value is greater than the threshold value; dividing the segment into a plurality of subsegments; determining a second approximation for a subsegment of the plurality of subsegments; determining, based at least in part on the second approximation, a second value; and determining that the second value is less than or equal to the threshold value. ### Claim 14 A method comprising: receiving sensor data associated with an environment; detecting, based at least in part on the sensor data, an object in the environment; determining a location of the object within the environment; determining, based at least in part on the location, that the object is located within a cell of discretized map data; receiving a candidate road associated with the cell, wherein the candidate road includes a segment; determining that the object is associated with the segment; receiving, from the cell and based at least in part on the object being associated with the segment, an approximation of the segment, wherein the approximation is determined at a previous time; determining a first distance relative to the object from a first point along the approximation and a second distance of the object relative to a second point the approximation; and controlling a vehicle based at least in part on the first distance and the second distance. ### Claim 15 (depends on 14) The method of claim 14, wherein the first distance indicates a measurement of the object along the candidate road, the candidate road being represented as a reference line, wherein determining the first distance comprises: identifying a start point of the reference line; identifying a second segment of the reference line between the start point and the segment, wherein the second segment is associated with a second approximation; and determining, based at least in part on a sum of a first length of the second approximation and at least a portion of a second length of the approximation, the first distance. ### Claim 16 (depends on 14) The method of claim 14, wherein the first distance and the second distance are in a relative coordinate system and the location is in a Cartesian coordinate system. ### Claim 17 (depends on 14) The method of claim 14, further comprising: receiving a second candidate road associated with the cell, wherein the second candidate road includes a second segment and a second approximation; determining that the object is associated with the second segment; determining a third distance relative to the object from a third point along the second approximation and a fourth distance of the object relative to a fourth point along the second approximation; and controlling the vehicle based at least in part on the first distance, the second distance, the third distance, and the fourth distance. ### Claim 18 (depends on 14) The method of claim 14, wherein the discretized map data is determined based at least in part on generating a plurality of cells associated with map data, the cell being associated with the plurality of cells, wherein the cell includes a cell identifier associated with a candidate road identifier of the candidate road. ### Claim 19 (depends on 14) The method of claim 14, wherein the approximation is determined based at least in part on: receiving a reference line associated with the candidate road; determining a value associated with a difference between the approximation and the segment; and determining that the value is less than or equal to a threshold value. ### Claim 20 (depends on 19) The method of claim 19, wherein determining the approximation further comprises: determining the value is greater than the threshold value; dividing the segment into a plurality of subsegments; determining a second approximation for a subsegment of the plurality of subsegments; determining, based at least in part on the second approximation, a second value; and determining that the second value is less than or equal to the threshold value.