Trajectory generation using temporal logic and tree search

• US 10,691,127 B2
• Filed: 11/16/2018
• Issued: 06/23/2020
• Est. Priority Date: 03/01/2017
• Status: Active Grant

• Current Assignee: Zoox Inc. (Amazon.com, Inc.)
• Original Assignee: Zoox Inc. (Amazon.com, Inc.)
• Inventors: Kobilarov, Marin, Caldwell, Timothy, Raman, Vasumathi, Paxton, Christopher, Kiiski, Joona Markus Petteri, Askeland, Jacob Lee, Somers, Robert Edward
• Primary Examiner(s): Marc-Coleman, Marthe Y
• Application Number:
  US16/193,801
• Publication Number:
  US 20190101919A1
• Time in Patent Office: 585 Days
• Field of Search: 701 27
• CPC Class Codes: B60W 2420/403 Image sensing, e.g. optical camera
• CPC Class Codes: B60W 2420/408 Radar; Laser, e.g. lidar
• CPC Class Codes: B60W 2554/4026 Cycles
• CPC Class Codes: B60W 2554/4029 Pedestrians
• CPC Class Codes: B60W 2554/80 Spatial relation or speed relative to objects
• CPC Class Codes: B60W 30/09 Taking automatic action to avoid collision, e.g. braking and steering
• CPC Class Codes: B60W 60/0011 involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles
• CPC Class Codes: B60W 60/0016 of the vehicle or its occupants
• CPC Class Codes: B60W 60/00276 for two or more other traffic participants
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G05D 1/0055 with safety arrangements
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology
• CPC Class Codes: G06N 3/08 Learning methods

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.

Claims

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 the candidate trajectory using the automaton.

20. The one or more non-transitory computer-readable media of claim 15, 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.