Trajectory generation using temporal logic and tree search

Patent metadata

Field	Value
Publication number	US-11360477-B2
Application number	US-202016908389-A
Country	US
Kind code	B2
Filing date	Jun 22, 2020
Priority date	Mar 1, 2017
Publication date	Jun 14, 2022
Grant date	Jun 14, 2022

Abstract

Techniques for determining a trajectory for an autonomous vehicle are described herein. In general, determining a route can include utilizing a search algorithm such as Monte Carlo Tree Search (MCTS) to search for possible trajectories, while using temporal logic formulas, such as Linear Temporal Logic (LTL), to validate or reject the possible trajectories. Trajectories can be selected based on various costs and constraints optimized for performance. Determining a trajectory can include determining a current state of the autonomous vehicle, which can include determining static and dynamic symbols in an environment. A context of an environment can be populated with the symbols, features, predicates, and LTL formula. Rabin automata can be based on the LTL formula, and the automata can be used to evaluate various candidate trajectories. Nodes of the MCTS can be generated and actions can be explored based on machine learning implemented as, for example, a deep neural network.

First claim

What is claimed is:

1. A method comprising:
receiving, from a machine learned model, an output;
determining, based at least in part on the output and a progressive widening algorithm, a node to a tree for use in a tree search;
determining, based at least in part on the tree search, a candidate trajectory associated with traversing an environment;
determining a cost associated with the candidate trajectory, the cost comprising one or more of a steering cost, an acceleration cost, a travel time cost, a comfort cost, or a lane position cost; and
controlling, based at least in part on the cost and the candidate trajectory, an autonomous vehicle to traverse the environment.

2. The method of claim 1 , further comprising:
receiving state data associated with the autonomous vehicle, the state data associated with a first time; and
determining, based at least in part on the tree search, simulated state data associated with a second time after the first time;
wherein the candidate trajectory is based at least in part on the state data and the simulated state data.

3. The method of claim 2 , wherein the state data comprises at least one of:
velocity data;
steering angle data; or
acceleration data.

4. The method of claim 1 , wherein the tree search comprises a Monte Carlo Tree Search.

5. The method of claim 1 , further comprising:
evaluating the candidate trajectory based at least in part on a temporal logic formula.

6. The method of claim 1 , wherein:
the candidate trajectory is a first candidate trajectory;
a first branch associated with the tree search represents the first candidate trajectory; and
a second branch associated with the tree search represents a second candidate trajectory.

7. The method of claim 1 , wherein a node associated with the tree search comprises one or more of:
a symbol;
a feature;
a predicate;
a temporal logic symbol; or
an automaton.

8. The method of claim 1 , further comprising:
adding the node further based at least in part on the progressive widening algorithm.

9. The method of claim 1 , further comprising:
determining that a termination condition associated with a first branch of the tree search is satisfied; and
adding the node to a second branch based at least in part on the termination condition being satisfied.

10. The method of claim 1 , further comprising:
adding the node further based at least in part on a driving policy.

11. One or more non-transitory computer-readable media storing instructions that, when executed, cause one or more processors to perform operations comprising:
receiving, from a machine learned model, an output;
determining, based at least in part on the output and a progressive widening algorithm, a node to a tree for use in a tree search;
determining, based at least in part on the tree search, a candidate trajectory associated with traversing an environment;
determining a cost associated with the candidate trajectory, the cost comprising one or more of a steering cost, an acceleration cost, a travel time cost, a comfort cost, or a lane position cost; and
controlling, based at least in part on the cost and the candidate trajectory, an autonomous vehicle to traverse the environment.

12. The one or more non-transitory computer-readable media of claim 11 , the operations further comprising:
receiving state data associated with the autonomous vehicle, the state data associated with a first time; and
determining, based at least in part on the tree search, simulated state data associated with a second time after the first time;
wherein the candidate trajectory is based at least in part on the state data and the simulated state data.

13. The one or more non-transitory computer-readable media of claim 12 , wherein the state data comprises at least one of:
velocity data;
steering angle data; or
acceleration data.

14. The one or more non-transitory computer-readable media of claim 11 , wherein:
the candidate trajectory is a first candidate trajectory;
a first branch associated with the tree search represents the first candidate trajectory; and
a second branch associated with the tree search represents a second candidate trajectory.

15. 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 machine learned model, an output;
determining, based at least in part on the output and a progressive widening algorithm, whether to add a node to a tree used in a tree search;
determining, based at least in part on the tree search, a candidate trajectory associated with traversing an environment;
determining a cost associated with the candidate trajectory, the cost comprising one or more of a steering cost, an acceleration cost, a travel time cost, a comfort cost, or a lane position cost; and
controlling, based at least in part on the cost and the candidate trajectory, an autonomous vehicle to traverse the environment.

16. The system of claim 15 , the operations further comprising:
receiving state data associated with the autonomous vehicle, the state data associated with a first time; and
determining, based at least in part on the tree search, simulated state data associated with a second time after the first time;
wherein the candidate trajectory is based at least in part on the state data and the simulated state data.

17. The system of claim 16 , wherein the state data comprises at least one of:
velocity data;
steering angle data; or
acceleration data.

18. The system of claim 15 , wherein the tree search comprises a Monte Carlo Tree Search.

19. The system of claim 15 , the operations further comprising:
evaluating the candidate trajectory based at least in part on a temporal logic formula.

20. The system of claim 15 , wherein:
the candidate trajectory is a first candidate trajectory;
a first branch associated with the tree search represents the first candidate trajectory; and
a second branch associated with the tree search represents a second candidate trajectory.

Assignees

• Zoox Inc

Inventors

• Kobilarov Marin
• Caldwell Timothy
• Raman Vasumathi
• Paxton Christopher
• Kiiski Joona Markus Petteri
• Askeland Jacob Lee
• Somers Robert Edward

Classifications

• G06N3/092

  Reinforcement learning · CPC title

• G06N3/0464

  Convolutional networks [CNN, ConvNet] · CPC title

• G05D1/246

  using environment maps, e.g. simultaneous localisation and mapping [SLAM] · CPC title

• G05D1/646

  Following a predefined trajectory, e.g. a line marked on the floor or a flight path · CPC title

• G05D1/617

  Safety or protection, e.g. defining protection zones around obstacles or avoiding hazards (arrangements for controlling the position or course of two or more vehicles for avoiding collisions therebetween G05D1/693; arrangements for reacting to or preventing system or operator failure G05D1/80) · CPC title