Unified scene graphs

Patent metadata

Field	Value
Publication number	US-11436504-B1
Application number	US-201916432796-A
Country	US
Kind code	B1
Filing date	Jun 5, 2019
Priority date	Jun 11, 2018
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

Abstract

Indications of static objects (e.g., lane segments, signs etc.) and dynamic objects (e.g., moving vehicles, pedestrians and the like) in the operation environment of a vehicle are obtained. A graph comprising a plurality of nodes and edges is generated. Individual ones of the nodes represent respective static and dynamic objects, and an edge between a first pair of nodes represents a relationship between the objects represented by the pair. The graph includes an indication of an uncertainty metric associated with the relationship. To generate the graph, a geometric analysis is performed, as a result of which an edge between a different pair of nodes is excluded from the graph. Using the graph, one or more operations of a task pertaining to vehicle movements is performed.

First claim

What is claimed is:

1. A method, comprising:
performing, at one or more computing devices:
obtaining respective indications of (a) one or more static objects in an operation environment of a first vehicle and (b) one or more dynamic objects in the operation environment;
generating a graph comprising a plurality of nodes and a plurality of edges, wherein a first node of the graph represents the first vehicle, wherein a second node of the graph represents a static object of the one or more static objects, wherein a third node of the graph represents a dynamic object of the one or more dynamic objects, wherein a first edge between a first pair of nodes of the graph represents a first relationship between a pair of objects represented by the first pair of nodes, wherein at least one object of the pair of objects represented by the first pair of nodes is the first vehicle or the dynamic object, wherein the graph includes an indication of a first uncertainty metric associated with the first relationship, and wherein generating the graph comprises determining, based on a geometric analysis, that an edge between a second pair of nodes is not to be included in the graph;
preparing, using at least the generated graph, a first trajectory of the first vehicle; and
transmitting, to a motion control subsystem of the vehicle, one or more directives to move the first vehicle according to the first trajectory.

2. The method as recited in claim 1 , wherein preparing the first trajectory comprises obtaining geometric information for at least a portion of a motion planning-related reasoning algorithm from the graph, without performing a geometric computation that accesses a first data structure representing the static objects and a second data structure representing dynamic objects.

3. The method as recited in claim 1 , wherein the geometric analysis comprises utilizing a bounding volume hierarchy (BVH) algorithm.

4. The method as recited in claim 1 , wherein the geometric analysis comprises determining one or more of: (a) a current proximity of a pair of objects represented by respective nodes or (b) a future proximity of a pair of objects represented by respective nodes.

5. The method as recited in claim 1 , further comprising performing, by the one or more computing devices:
accessing a map to obtain an indication of an expected location of at least one static object of the one or more static objects, wherein the map is obtained at the first vehicle from a map source via a communication protocol.

6. The method as recited in claim 1 , wherein a respective indication of at least one object of the first pair of objects is based at least in part on output produced by one or more sensors of the first vehicle, wherein a first sensor of the one or more sensors comprises one or more of: (a) a still camera, (b) a video camera, (c) a radar device, (d) a LIDAR device, (e) an infra-red device, or (f) an ultrasonic device.

7. The method as recited in claim 1 , further comprising performing, by the one or more computing devices:
determining the uncertainty metric based at least in part on one or more of: (a) error bounds indicated by a sensor device used to determine the relationship, (b) an estimate of an accuracy of a type of a sensor device whose output is used to determine the relationship, or (c) an estimate of a distance, from the first vehicle, of at least one of the objects of the pair of objects.

8. The method as recited in claim 1 , wherein the graph includes a second uncertainty metric assigned to a particular node, wherein the second uncertainty metric is based at least in part on an estimated probability of an incorrect identification of the object represented by the particular node.

9. The method as recited in claim 1 , further comprising performing, by the one or more computing devices:
including, in the graph, a fourth node, based at least in part on input obtained from a first data source;
including, in the graph, a fifth node, based at least in part on input obtained from a second data source; and
replacing, in the graph, the fourth and fifth nodes by a reconciled node corresponding to the fourth and fifth nodes, wherein the replacing is based at least in part on one or more algorithms, wherein a particular algorithm of the one or more algorithms comprises one or more of: (a) analyzing temporal data pertaining to at least one node of the fourth and fifth nodes, or (b) determining a probability that the fourth and fifth nodes refer to the same object.

10. The method as recited in claim 1 , wherein the plurality of nodes comprises at least one node representing a virtual entity.

11. A system, comprising:
one or more processors; and
a memory;
wherein the memory stores program instructions that when executed on or across the one or more processors cause the one or more processors to:
obtain respective indications of (a) one or more static objects in an operation environment of at least a first vehicle and (b) one or more dynamic objects in the operation environment;
generate a graph comprising a plurality of nodes and a plurality of edges, wherein a first node of the graph represents the first vehicle, wherein a second node of the graph represents a static object of the one or more static objects, wherein a third node of the graph represents a dynamic object of the one or more dynamic objects, wherein a first edge between a first pair of nodes of the graph represents a first relationship between a pair of objects represented by the first pair of nodes, wherein at least one object of the pair of objects represented by the first pair of nodes is the first vehicle or the dynamic object, wherein the graph includes an indication of a first uncertainty metric associated with the first relationship, and wherein generating the graph comprises determining, based at least in part on a geometric analysis, that an edge between a second pair of nodes is not to be included in the graph; and
cause, using the generated graph, one or more operations of a task pertaining to vehicle movements to be performed.

12. The system as recited in claim 11 , wherein a first static object of the one or more static objects comprises at least a portion of one or more of: (a) a lane segment, (b) a traffic light, (c) a curb, (d) a sign, (e) a building, (f) an overpass, (g), a bridge, (g) a parking lot, (h) a landmark, (i) a cross-walk, (j) an element of vegetation, or (k) a gate.

13. The system as recited in claim 11 , wherein a first dynamic object of the one or more dynamic objects comprises at least a portion of one or more of: (a) a second vehicle, (b) a pedestrian, or (c) an animal.

14. The system as recited in claim 11 , wherein the memory stores further program instructions that when executed on or across the one or more processors further cause the one or more processors to:
obtain, based at least in part on an analysis of a plurality of paths between at least a particular pair of nodes of the graph, a joint estimate of an attribute value of one or more of: (a) a node of the particular pair or (b) an edge incident on a node of the particular pair.

15. The system as recited in claim 11 , wherein the memory stores further program instructions that when executed on or across the one or more processors further cause the one or more processors to:
include, in the graph, a fourth node, wherein the fourth node comprises a first set of temporal data about a particular object;
include, in the graph, a fifth node, wherein the fifth node comprises a second set of temporal data about the particular object; and
replace, in the graph, the fourth and fifth n

Assignees

• Apple Inc

Inventors

• Lukarski Dimitar Hristov
• Johnson Luke Burke
• Rao Arun
• Swaminathan Siddharth

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title

• G06N20/00

  Machine learning · CPC title

• G06N5/04 Primary

  Inference or reasoning models · CPC title

• G05D2201/0213

  Physics · mapped topic