Trajectory generation using temporal logic and tree search

Patent metadata

Field	Value
Publication number	US-10691127-B2
Application number	US-201816193801-A
Country	US
Kind code	B2
Filing date	Nov 16, 2018
Priority date	Mar 1, 2017
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

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 system comprising:
one or more processors; and
a computer-readable medium storing computer-executable instructions that, when executed, cause the system to perform operations comprising:
generating a plurality of candidate trajectories for an autonomous vehicle;
selecting, based at least in part on an environment proximate to the autonomous vehicle, a temporal logic formula;
evaluating a candidate trajectory of the plurality of candidate trajectories based at least in part on an automaton determined by the temporal logic formula;
selecting, as a selected trajectory, the candidate trajectory based at least part on a result of the evaluating and on a cost associated with the candidate trajectory; and
controlling the autonomous vehicle based at least in part on the selected trajectory.

2. The system of claim 1 , wherein the temporal logic formula is further based at least in part on a symbol representing a portion of the environment proximate to the autonomous vehicle.

3. The system of claim 2 , the operations further comprising one or more of:
receiving the symbol from map data representing the environment; or
determining the symbol based at least in part on sensor data captured by the autonomous vehicle.

4. The system of claim 1 , the operations further comprising:
determining, based at least in part on the symbol, a feature; and
determining, based at least in part on the symbol or the feature, a predicate;
wherein the temporal logic formula is further based at least in part on at least one of the feature or the predicate.

5. The system of claim 1 , the operations further comprising:
generating the automaton based at least in part on the temporal logic formula; and
evaluating the candidate trajectory using the automaton, wherein the automaton comprises at least one of a Rabin automaton, a Büchi automaton, a Streett automaton, a Parity automaton, or a Muller automaton;
wherein selecting the candidate trajectory as the selected trajectory is further based at least in part on evaluating the candidate trajectory using the automaton.

6. The system of claim 1 , the operations further comprising:
populating a tree search with a first snapshot of the environment at a first time, the first snapshot based at least in part on the candidate trajectory;
selecting an action based at least in part on the first snapshot and at least one machine learning algorithm;
evolving the first snapshot over a time step by applying the action to the first snapshot to generate a second snapshot; and
add a node to the tree search based at least in part on a termination condition associated with the action, the node representing a speculative snapshot associated with the environment associated with a second time after the first time.

7. The system of claim 1 , the operations further comprising:
populating a tree search with a plurality of candidate trajectories, the plurality of trajectories comprising at least the candidate trajectory; and
adding at least one node to the tree search based at least in part on a machine learning algorithm comprising a neural network.

8. A method comprising:
generating a plurality of candidate trajectories for an autonomous vehicle;
populating a tree search with a candidate trajectory of the plurality of candidate trajectories;
selecting, based at least in part an environment proximate to the autonomous vehicle a temporal logic formula;
evaluating a candidate trajectory of the plurality of candidate trajectories based at least in part on an automaton determined by the temporal logic formula;
selecting, as a selected trajectory, the candidate trajectory based at least part on a result of the evaluating and on a cost associated with the candidate trajectory; and
controlling the autonomous vehicle based at least in part on the selected trajectory.

9. The method of claim 8 , wherein the temporal logic formula is further based at least in part on symbol representing a portion of the environment proximate to the autonomous vehicle.

10. The method of claim 9 , further comprising one or more of:
receiving the symbol from map data representing the environment; or
determining the symbol based at least in part on sensor data captured by the autonomous vehicle.

11. The method of claim 8 , further comprising:
determining, based at least in part on the symbol, a feature; and
determining, based at least in part on the symbol or the feature, a predicate;
wherein the temporal logic formula is further based at least in part on at least one of the feature or the predicate.

12. The method of claim 8 , wherein the temporal logic formula comprises at least one of a linear temporal logic formula or a signal temporal logic formula.

13. The method of claim 8 , further comprising:
generating the automaton based at least in part on the temporal logic formula; and
evaluating the candidate trajectory using the automaton, wherein the automaton comprises at least one of a Rabin automaton, a Büchi automaton, a Streett automaton, a Parity automaton, or a Muller automaton;
wherein selecting the candidate trajectory as the selected trajectory is further based at least in part on evaluating the candidate trajectory using the automaton.

14. The method of claim 8 , further comprising:
adding at least one node to the tree search based at least in part on a machine learning algorithm comprising a neural network.

15. One or more non-transitory computer-readable media storing instructions that, when executed, cause one or more processors to perform operations comprising:
generating, based at least in part on a tree search, a plurality of candidate trajectories for an autonomous vehicle;
selecting, based at least in part an environment proximate to the autonomous vehicle, a temporal logic formula;
evaluating a candidate trajectory of the plurality of candidate trajectories based at least in part on an automaton determined by the temporal logic formula;
selecting, as a selected trajectory, the candidate trajectory based at least part on a result of the evaluating and on a cost associated with the candidate trajectory; and
controlling the autonomous vehicle based at least in part on the selected trajectory.

16. The one or more non-transitory computer-readable media of claim 15 , wherein evaluating the candidate trajectory is based at least in part on the temporal logic formula that is based at least in part on a symbol representing a portion of the environment proximate to the autonomous vehicle.

17. The one or more non-transitory computer-readable media of claim 16 , the operations further comprising one or more of:
receiving the symbol from map data representing the environment; or
determining the symbol based at least in part on sensor data captured by the autonomous vehicle.

18. The one or more non-transitory computer-readable media of claim 16 , wherein the temporal logic formula comprises at least one of a linear temporal logic formula or a signal temporal logic formula.

19. The one or more non-transitory computer-readable media of claim 16 , the operations further comprising:
generating an automaton based at least in part on the temporal logic formula; and
evaluating the candidate trajectory using the automaton, wherein the automaton comprises at least one of a Rabin automaton, a Büchi automaton, a Streett automaton, a Parity automaton, or a Muller automaton;
wherein selecting the candidate trajectory as the selected trajectory is further based at least in part on evaluating

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