Back to results
US 12,576,887 B2Granted
Route lane matching based on graph search
AssigneeZoox, Inc.
InventorsXiaosi Zeng, Lakshay Garg, Cheng Peng, Andres Guillermo Morales Morales
Life of this patent
Estimating the term…
Abstract
Techniques for identifying road segments associated with an object trajectory are discussed herein. A computing device can implement a model that extracts points from an object trajectory and identifies road segments along a path between the extracted points. The model can determine a set of road segments for the path based on searching a graph. The graph can comprise nodes to represent different road segments, and a graph search algorithm can output road segments representing a shortest path between the nodes associated with the extracted points. The road segments can be used by a vehicle computing device for predicting vehicle actions to control a vehicle.
Claims20
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 a trajectory associated with an object in an environment;
- determining a first point and a second point associated with the trajectory;
- searching a graph comprising a first node corresponding to the first point and a second node corresponding to the second point;
- determining, based at least in part on searching the graph, a set of road segments in the environment representing a path between the first point and the second point;
- defining a first set of nodes corresponding to a first set of road segments and a second set of nodes corresponding to a second set of road segments;
- searching the graph comprises selecting one of:
- the first set of road segments or the second set of road segments as the set of road segments representing the path;
- assigning a first score to a first output of searching the first set of nodes and a second score to a second output of searching the second set of nodes, the first score or the second score indicating a level of similarity between the trajectory and one of:
- the first set of road segments associated with the first output or the second set of road segments associated with the second output;
- determining one of:
- the first set of road segments associated with the first output or the second set of road segments associated with the second output as the set of road segments based at least in part on the higher of the first score or the second score;
- sending the set of road segments to a vehicle computing device associated with a vehicle;
- and
- controlling the vehicle in the environment based at least in part on the set of road segments.
11 more elements
A method comprising:
- receiving a trajectory associated with an object in an environment;
- determining a first point and a second point associated with the trajectory;
- searching a graph comprising a first node corresponding to the first point and a second node corresponding to the second point;
- determining, based at least in part on searching the graph, a set of road segments in the environment representing a path between the first point and the second point;
- defining a first set of nodes corresponding to a first set of road segments and a second set of nodes corresponding to a second set of road segments;
- searching the graph comprises selecting one of:
- the first set of road segments or the second set of road segments as the set of road segments representing the path;
- assigning a first score to a first output of searching the first set of nodes and a second score to a second output of searching the second set of nodes, the first score or the second score indicating a level of similarity between the trajectory and one of:
- the first set of road segments associated with the first output or the second set of road segments associated with the second output;
- determining one of:
- the first set of road segments associated with the first output or the second set of road segments associated with the second output as the set of road segments based at least in part on the higher of the first score or the second score;
- sending the set of road segments to a vehicle computing device associated with a vehicle;
- and
- controlling the vehicle in the environment based at least in part on the set of road segments.
11 more elements
A system comprising:
- one or more processors;
- and
- one or more non-transitory computer-readable media storing instructions executable by the one or more processors, wherein the instructions, when executed, cause the system to perform operations comprising:
- receiving a trajectory associated with an object in an environment;
- determining a first point and a second point associated with the trajectory;
- searching a graph comprising a first node corresponding to the first point and a second node corresponding to the second point;
- determining, based at least in part on searching the graph, a set of road segments in the environment representing a path between the first point and the second point;
- defining a first set of nodes corresponding to a first set of road segments and a second set of nodes corresponding to a second set of road segments;
- searching the graph comprises selecting one of:
- the first set of road segments or the second set of road segments as the set of road segments representing the path;
- assigning a first score to a first output of searching the first set of nodes and a second score to a second output of searching the second set of nodes, the first score or the second score indicating a level of similarity between the trajectory and one of:
- the first set of road segments associated with the first output or the second set of road segments associated with the second output;
- determining one of:
- the first set of road segments associated with the first output or the second set of road segments associated with the second output as the set of road segments based at least in part on the higher of the first score or the second score;
- sending the set of road segments to a vehicle computing device associated with a vehicle;
- and
- controlling the vehicle in the environment based at least in part on the set of road segments.
14 more elements
Dependencies are inferred from the claim text.