Trajectory generation using temporal logic and tree search

• US 10,133,275 B1
• Filed: 06/23/2017
• Issued: 11/20/2018
• 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:
  US15/632,147
• Time in Patent Office: 515 Days
• Field of Search: 701 25, 706 41, 706 46, 706932
• 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 for implementing a control algorithm for 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 one or more symbols, the one or more symbols including at least one static symbol or at least one dynamic symbol;

determine, based at least in part on the one or more symbols, one or more features;

determine, based at least in part on the one or more symbols or the one or more features, one or more predicates;

determine, based at least in part on the one or more symbols, one or more features, or one or more predicates, one or more linear temporal logic (LTL) formulas;

determine, based at least in part on the one or more LTL formulas, one or more automaton;

utilize a Monte Carlo Tree Search (MCTS) to generate one or more candidate trajectories;

evaluate the one or more candidate trajectories using the one or more automaton, wherein the one or more automaton verifies that the one or more candidate trajectories satisfies the one or more LTL formulas associated with the one or more automaton;

determine, based at least in part on a cost function, a cost associated with a trajectory of the one or more candidate trajectories;

select, as a selected trajectory, the trajectory of the one or more candidate trajectories based at least in part on the cost; and

control the autonomous vehicle based at least in part on the selected trajectory.

2. The system of claim 1, the instructions further executable by the one or more processors to receive the one or more symbols from at least one of map data representing at least a portion of an environment or from a perception system of the autonomous vehicle that determines the one or more symbols using sensor data captured by the autonomous vehicle.

3. The system of claim 1, the instructions further executable by the one or more processors to evaluate the one or more features based at least in part on the one or more symbols to return a numerical value associated with the one or more symbols.

4. The system of claim 1, the instructions further executable by the one or more processors to evaluate the one or more predicates based at least in part on at least one of the one or more symbols or the one or more features to return at least one of a Boolean value or a confidence level associated with a state of the one or more symbols or the one or more features.

5. The system of claim 1, the instructions further executable by the one or more processors to add at least one node to the MCTS based at least in part on a machine learning algorithm comprising a neural network.

6. The system of claim 1, wherein a first node of the MCTS includes a snapshot of an environment including the one or more symbols, the one or more features, the one or more predicates, and the one or more LTL formulas, and wherein the instructions are further executable by the one or more processors to add a second node to the MCTS that includes an update of the environment associated with the snapshot over time.

7. The system of claim 1, the instructions further executable by the one or more processors to:

determine that the selected trajectory satisfies the one or more LTL formulas; and

determine that the cost associated with the selected trajectory is a lowest cost with respect to trajectories of the one or more candidate trajectories that satisfy the one or more LTL formulas.

8. The system of claim 1, the instructions further executable by the one or more processors to:

determine that a candidate trajectory of the one or more candidate trajectories violates, as a violation, the one or more LTL formulas associated with the one or more automaton; and

assign a penalty to the candidate trajectory based at least in part on a degree of the violation of the one or more LTL formulas.

9. A method comprising:

determining one or more symbols of an environment proximate to an autonomous vehicle;

generating a context of the environment based at least in part on the one or more symbols;

populating a tree search with one or more candidate trajectories;

selecting, as a selected trajectory, a trajectory of the one or more candidate trajectories based at least part on an evaluation of the selected trajectory with respect to one or more temporal logic formulas or on one or more costs; and

controlling the autonomous vehicle based at least in part on the selected trajectory.

10. The method of claim 9, further comprising:

populating the tree search with a first snapshot of the environment, the first snapshot based at least in part on the environment at a first time;

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 to generate a second snapshot, the evolving including applying the action to the first snapshot; and

adding a node to the tree search based at least in part on the second snapshot, the node representing a speculative snapshot associated with the environment associated with a second time after the first time.

11. The method of claim 9, wherein generating the context includes:

determining one or more features based at least in part on the one or more symbols;

determining one or more predicates based at least in part on the one or more symbols or the one or more features; and

determining the one or more temporal logic formulas based at least in part on the one or more symbols, the one or more features, and the one or more predicates.

12. The method of claim 9, further comprising selecting a fallback trajectory to implement in an event of a failure of one or more components of the autonomous vehicle.

13. The method of claim 9, wherein the one or more symbols comprise a dynamic symbol representing a vehicle proximate to the autonomous vehicle, and wherein the one or more candidate trajectories are based at least in part on a prediction associated with a motion of the dynamic symbol over time.

14. The method of claim 9, further comprising generating one or more automaton based at least in part on the one or more temporal logic formulas, the method further comprising evaluating the one or more candidate trajectories using the one or more automaton, wherein the one or more automaton includes at least one of a Rabin automaton, a Bü

chi automaton, a Streett automaton, a Parity automaton, or a Muller automaton.

15. A 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;

determine one or more symbols of an environment proximate to an autonomous vehicle;

generate a context of the environment based at least in part on the one or more symbols;

populate a tree search with one or more candidate trajectories;

select, as a selected trajectory, a trajectory of the one or more candidate trajectories based at least part on an evaluation of the selected trajectory with respect to one or more temporal logic formulas or on one or more costs; and

control the autonomous vehicle based at least in part on the selected trajectory.

16. The system of claim 15, the instructions further executable by the one or more processors to:

populate the tree search with a first snapshot of the environment, the first snapshot based at least in part on the environment at a first time;

select an action based at least in part on the first snapshot and at least one machine learning algorithm;

evolve 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.

17. The system of claim 15, the instructions further executable by the one or more processors to:

determine one or more features based at least in part on the one or more symbols;

determine one or more predicates based at least in part on the one or more symbols or the one or more features; and

determine the one or more temporal logic formulas based at least in part on the one or more symbols, the one or more features, and the one or more predicates.

18. The system of claim 15, wherein the temporal logic formulas include at least one of linear temporal logic (LTL) formulas or signal temporal logic (STL) formulas.

19. The system of claim 15, wherein the one or more symbols comprise a dynamic symbol representing a vehicle proximate to the autonomous vehicle, and wherein the one or more candidate trajectories are based at least in part on a prediction associated with a motion of the dynamic symbol over time.

20. The system of claim 15, the instructions further executable by the one or more processors to:

generate one or more automaton based at least in part on the one or more temporal logic formulas; and

evaluate the one or more candidate trajectories using the one or more automaton, wherein the one or more automaton includes at least one of a Rabin automaton, a Bü

chi automaton, a Streett automaton, a Parity automaton, or a Muller automaton.