US 10,671,076 B1Granted

Trajectory prediction of third-party objects using temporal logic and tree search

AssigneeZoox, Inc.

InventorsMarin Kobilarov, Timothy Caldwell, Vasumathi Raman, Christopher Paxton

Life of this patent

Estimating the term…

Loading patent…

Abstract

Techniques for generating trajectories for autonomous vehicles and for predicting trajectories for third-party objects using temporal logic and tree search are described herein. Perception data about an environment can be captured to determine static objects and dynamic objects. For a particular dynamic object, which can represent a third-party vehicle, predictive trajectories can be generated to represent possible trajectories based on available options and rules of the road. Operations can include determining probabilities that a third-party vehicle will execute a predictive trajectory and updating the probabilities over time as motion data is captured. Predictive trajectories can be provided to the autonomous vehicle and commands for the autonomous vehicle can be based on the predictive trajectories. Further, determining a trajectory can include utilizing a Monte Carlo Tree Search (MCTS) to search for possible trajectories, while using Linear Temporal Logic (LTL) formulas to validate or reject the possible trajectories.

Claims20

Dependent claims

A system of an autonomous vehicle, the system comprising:

one or more processors;
and
one or more computer readable storage media communicatively coupled to the one or more processors and storing instructions that are executable by the one or more processors to:
receive sensor data from one or more of a LIDAR sensor, a RADAR sensor, or a camera sensor;
determine, based at least in part on the sensor data, one or more dynamic symbols, a dynamic symbol of the one or more dynamic symbols representing a third-party object that is not under control of the autonomous vehicle;
determine, based at least in part on the sensor data, motion data associated with the one or more dynamic symbols, the motion data including at least a position, an orientation, and a velocity associated with a dynamic symbol of the one or more dynamic symbols;
determine, based at least in part on the one or more dynamic symbols and one or more static symbols, one or more predictive trajectories navigable by the third-party object, wherein the one or more dynamic symbols and the one or more static symbols represent temporal logic features;
determine, based at least in part on the motion data, an outcome probability associated with a predictive trajectory of the one or more predictive trajectories;
select, as a selected predictive trajectory, the predictive trajectory based at least in part on the outcome probability;
and
provide the selected predictive trajectory to a decision planner of the autonomous vehicle.

8 more elements

A method comprising:

selecting a dynamic symbol as a subject symbol for prediction, wherein the dynamic symbol represents a temporal logic feature;
determining one or more symbols associated with the subject symbol;
determining one or more predictive trajectories associated with predictive motion of the subject symbol based at least in part on the one or more symbols and the subject symbol;
determining an outcome probability associated with a predictive trajectory of the one or more predictive trajectories;
providing the predictive trajectory to a decision planner of an autonomous vehicle, the predictive trajectory provided based at least in part on the outcome probability associated with the predictive trajectory;
determining a command trajectory of the autonomous vehicle based at least in part on the predictive trajectory provided to the decision planner;
and
commanding the autonomous vehicle based at least in part on the command traj ectory.

5 more elements

A non-transitory computer-readable medium storing instructions that, when executed, cause one or more processors to perform operations comprising:

receiving sensor data from one or more sensors of an autonomous vehicle, the sensor data including at least one of LIDAR sensor data, RADAR sensor data, acoustic sensor data, or image sensor data;
determining, based at least in part on the sensor data, one or more dynamic symbols proximate to the autonomous vehicle, wherein the one or more dynamic symbols represent temporal logic features;
selecting a dynamic symbol of the one or more dynamic symbols as a subject symbol for prediction;
determining one or more symbols associated with the subject symbol;
determining one or more predictive trajectories associated with predictive motion of the subject symbol based at least in part on the one or more symbols and the subject symbol;
determining an outcome probability associated with a predictive trajectory of the one or more predictive trajectories;
and
providing the predictive trajectory to a decision planner of the autonomous vehicle, the predictive trajectory provided based at least in part on the outcome probability associated with the predictive trajectory;
and
controlling the autonomous vehicle based at least in part on the predictive trajectory.

7 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/833,715Filed 6 Dec 2017 · us provisional application
Priority: 1 Mar 2017
Granted: 2 Jun 2020
Term ends: Not estimatedThe source records don’t support an estimate.

Classification17 codes

G05D 1/0214
With means for defining a desired trajectory: in accordance with safety or protection criteria, e.g. avoiding hazardous areas
G08G 1/09623
Having an indicator mounted inside the vehicle, e.g. giving voice messages: systems involving the acquisition of information from passive traffic…
B60W 60/00274
Using trajectory prediction for other traffic participants: considering possible movement changes
B60W 60/00276
Using trajectory prediction for other traffic participants: for two or more other traffic participants