Parallelized tree-based decision scheme for autonomous vehicle

Abstract

A system or method implemented by an autonomous vehicle involves determining a path plan to reach a destination from an origin. The path plan includes two or more path steps indicating tasks to be completed to reach the destination. The method includes, during traversal of the path plan by the autonomous vehicle, evaluating one or more of the two or more path steps of a planning horizon to determine a behavior plan for the planning horizon. The planning horizon is based on a current position of the autonomous vehicle, the behavior plan includes a speed and a trajectory, and the evaluating includes performing a cost analysis using a parallelized tree-based decision scheme at each of two or more simulation intervals within the planning horizon. The evaluating and the determining the behavior plan is repeated at two or more positions of the autonomous vehicle from the origin to the destination.

What is claimed is: 
     
       1. A method implemented by an autonomous vehicle, the method comprising:
 determining, using a processor, a path plan to reach a destination from an origin of the autonomous vehicle, the path plan including two or more path steps that indicate tasks to be completed to reach the destination; 
 during traversal of the path plan by the autonomous vehicle, evaluating, using the processor, one or more of the two or more path steps that are part of a planning horizon to determine a behavior plan for the planning horizon, the planning horizon being based on a current position of the autonomous vehicle, the behavior plan including a speed and a trajectory for the autonomous vehicle to complete the one or more of the two or more path steps, and the evaluating including performing a cost analysis using a parallelized tree-based decision scheme at each of two or more simulation intervals within the planning horizon, wherein the determining the path plan includes determining a primary path plan including two or more primary path steps prior to the traversal and determining an alternate path plan including two or more alternate path steps during the traversal for a same planning horizon, the evaluating the one or more of the two or more path steps that are part of the planning horizon includes determining if one or more of the two or more alternate path steps are in the planning horizon, and evaluating the one or more of the two or more alternate path steps in the planning horizon based on the determining indicating that the one or more of the two or more alternate path steps are in the planning horizon; 
 repeating the evaluating and the determining the behavior plan for the planning horizon at two or more positions of the autonomous vehicle from the origin to the destination; and 
 controlling operation of the vehicle according to the behavior plan determined at each planning horizon. 
 
     
     
       2. The method according to  claim 1 , wherein the performing the cost analysis includes obtaining a decision tree for each of the one or more of the two or more path steps in the simulation interval within the planning horizon indicating optional actions associated with each of the one or more of the two or more path steps in the planning horizon. 
     
     
       3. The method according to  claim 2 , wherein the performing the cost analysis includes determining a cost associated with each of the optional actions of each of the decision trees associated with each of the one or more of the two or more path steps in the simulation interval within the planning horizon. 
     
     
       4. The method according to  claim 2 , wherein determining the behavior plan includes selecting a lowest-cost action among the optional actions for each of the two or more simulation intervals within the planning horizon. 
     
     
       5. The method according to  claim 1 , wherein the repeating the evaluating and the determining the behavior plan is performed continuously during the traversal of the path plan by the autonomous vehicle. 
     
     
       6. The method according to  claim 1 , wherein during the traversal of the path plan, the determining the behavior plan also includes the performing the cost analysis for conditions indicating tasks that are encountered in real-time and are additional to the tasks indicated by path steps. 
     
     
       7. The method according to  claim 1 , wherein the evaluating the one or more of the two or more path steps includes obtaining a decision tree for each of the one or more of the two or more primary path steps in the planning horizon indicating optional actions associated with each of the one or more of the two or more primary path steps in the two or more simulation intervals within the planning horizon and obtaining a decision tree for each of the one or more of the two or more alternate path steps in the two or more simulation intervals within the planning horizon indicating optional actions associated with each of the one or more of the two or more alternate path steps in the planning horizon. 
     
     
       8. The method according to  claim 7 , wherein the performing the cost analysis includes determining a primary cost associated with each of the optional actions of each of the decision trees associated with each of the one or more of the two or more primary path steps in each of the two or more simulation intervals within the planning horizon and determining an alternate cost associated with each of the optional actions of each of the decision trees associated with each of the one or more of the two or more alternate path steps in each of the two or more simulation intervals within the planning horizon. 
     
     
       9. The method according to  claim 8 , further comprising comparing the primary cost and the alternate cost to select between the behavior plan from the primary path plan and the behavior plan from the alternate path plan to traverse with the autonomous vehicle. 
     
     
       10. A system in an autonomous vehicle, the system comprising:
 a memory device configured to store a path plan to reach a destination from an origin of the autonomous vehicle, the path plan including two or more path steps; and 
 a processor configured to evaluate one or more of the two or more path steps that are part of a planning horizon to determine a behavior plan defining operation of the vehicle for the planning horizon, during traversal of the path plan by the autonomous vehicle, the planning horizon being based on a current position of the autonomous vehicle, the behavior plan including a speed and a trajectory for the autonomous vehicle to complete the one or more of the two or more path steps, and the evaluating including performing a cost analysis using a parallelized tree-based decision scheme at each of two or more simulation intervals within the planning horizon, and to repeat a process of determining the behavior plan for the planning horizon at two or more positions of the autonomous vehicle from the origin to the destination, wherein the operation of the vehicle is controlled according to the behavior plan determined at each planning horizon and the processor is configured to determine a primary path plan including two or more primary path steps prior to the autonomous vehicle leaving the origin and to determine an alternate path plan including two or more alternate path steps for a same planning horizon after the autonomous vehicle has left the origin and prior to the autonomous vehicle reaching the destination, to determine if one or more of the two or more alternate path steps are in the planning horizon, and to evaluate the one or more of the two or more alternate path steps in the planning horizon based on the determining indicating that the one or more of the two or more alternate path steps are in the planning horizon. 
 
     
     
       11. The system according to  claim 10 , wherein the processor is configured to obtain a decision tree for each of the one or more of the two or more path steps in the planning horizon indicating optional actions associated with each of the one or more of the two or more path steps in the simulation interval within the planning horizon. 
     
     
       12. The system according to  claim 11 , wherein the processor is configured to determine a cost associated with each of the optional actions of each of the decision trees associated with each of the one or more of the two or more path steps in the simulation interval within the planning horizon. 
     
     
       13. The system according to  claim 11 , wherein the processor is configured to select a lowest-cost action among the optional actions for each of the two or more simulation intervals within the planning horizon. 
     
     
       14. The system according to  claim 10 , wherein repeating the process of determining the behavior plan is performed continuously during the traversal of the path plan by the autonomous vehicle. 
     
     
       15. The system according to  claim 10 , wherein during the traversal of the path plan, the processor is configured to determine the behavior plan by additionally performing the cost analysis for conditions indicating tasks that are encountered in real-time and are additional to the tasks indicated by path steps. 
     
     
       16. The system according to  claim 10 , wherein the processor is configured to obtain a decision tree for each of the one or more of the two or more primary path steps in the planning horizon indicating optional actions associated with each of the one or more of the two or more primary path steps in the two or more simulation intervals within the planning horizon and to obtain a decision tree for each of the one or more of the two or more alternate path steps in the two or more simulation intervals within the planning horizon indicating optional actions associated with each of the one or more of the two or more alternate path steps in the planning horizon. 
     
     
       17. The system according to  claim 16 , wherein the processor is configured to determine a primary cost associated with each of the optional actions of each of the decision trees associated with each of the one or more of the two or more primary path steps in each of the two or more simulation intervals within the planning horizon and to determine an alternate cost associated with each of the optional actions of each of the decision trees associated with each of the one or more of the two or more alternate path steps in each of the two or more simulation intervals within the planning horizon. 
     
     
       18. The system according to  claim 17 , wherein the processor is configured to compare the primary cost and the alternate cost to select between the behavior plan from the primary path plan and the behavior plan from the alternate path plan to traverse with the autonomous vehicle.