Machine-learned cost estimation in tree search trajectory generation for vehicle control

1 . A system comprising:

one or more processors; and

a memory storing processor-executable instructions that, when executed by the one or more processors, cause the system to perform operations comprising:

determining, by a machine-learned model, a first estimated cost of moving a vehicle from a first vehicle state indicated by a prediction node of a tree to a termination point, the first estimated cost indicating an estimated lowest cost of reaching the termination point from the first vehicle state and associated with at least one of safety, progress along a route, or passenger comfort associated with reaching the termination point;

determining, by the machine-learned model, a second estimated cost associated with a root node of the tree, the root node of the tree indicating a current state of the vehicle;

determining, by a cost function, a predicted cost for moving the vehicle from the root node to the termination point, the predicted cost indicating an upper bound cost associated with the root node;

determining a first sub-loss based at least in part on a difference between the second estimated cost and the predicted cost;

determining a second sub-loss based at least in part on a difference between the first estimated cost, a third estimated cost determined by the machine-learned model for a future vehicle state following the first vehicle state or an expected value of the third estimated cost, and a transition cost of an action to move from the future vehicle state;

modifying, based at least in part on the first sub-loss and the second sub-loss, a parameter of the machine-learned model; and

transmitting the machine-learned model to the vehicle for the vehicle to determine a trajectory for controlling the vehicle based at least in part on an output of the machine-learned model.

2 . The system of claim 1 , wherein determining the second sub-loss further comprises weighting, based at least in part on a convergence of a tree search that generated the tree, the difference between the first estimated cost, the third estimated cost or the expected value of the third estimated cost, and the transition cost of the action to move from the future vehicle state.

3 . The system of claim 2 , wherein weighting based at least in part on the convergence comprises determining increasing a weight as a difference between a second upper bound cost determined for the prediction node and a lower bound cost determined for the prediction node decreases.

4 . The system of claim 1 , wherein determining the second sub-loss further comprises adjusting the second sub-loss based at least in part on an estimate of a difference between the estimated lowest cost associated with the action for moving from the future vehicle state to the termination point and a cost associated with an optimal action for reaching the termination point.

5 . The system of claim 4 , wherein determining the estimate of the difference between the estimated lowest cost and the cost associated with the optimal action comprises one or more of:

multiplying a constant by a difference between a second upper bound cost determined for the prediction node and a lower bound cost determined for the prediction node, or

randomly sampling, as the estimate, a value between zero and the second upper bound cost minus the lower bound cost.

6 . One or more non-transitory computer-readable media storing processor-executable instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

determining, by a machine-learned model, a first estimated cost of operating a vehicle from a first vehicle state indicated by a prediction node of a tree to a termination point, the first estimated cost indicating an estimated lowest cost of reaching the termination point from the first vehicle state;

determining, by the machine-learned model, a second estimated cost associated with a root node of the tree;

determining, by a cost function, a predicted cost for operating the vehicle from the root node to the termination point;

determining a first sub-loss based at least in part on a difference between the second estimated cost and the predicted cost;

determining a second sub-loss based at least in part on a difference between the first estimated cost, a third estimated cost determined by the machine-learned model for a future vehicle state following the first vehicle state or an expected value of the third estimated cost, and a transition cost of an action to operate from the future vehicle state; and

modifying, based at least in part on the first sub-loss and the second sub-loss, a parameter of the machine-learned model.

7 . The one or more non-transitory computer-readable media of claim 6 , wherein determining the second sub-loss further comprises weighting, based at least in part on a convergence of a tree search that generated the tree, the difference between the first estimated cost, the third estimated cost or the expected value of the third estimated cost, and the transition cost of the action to operate from the future vehicle state.

8 . The one or more non-transitory computer-readable media of claim 7 , wherein weighting based at least in part on the convergence comprises determining increasing a weight as a difference between a upper bound cost determined for the prediction node and a lower bound cost determined for the prediction node decreases.

9 . The one or more non-transitory computer-readable media of claim 6 , wherein determining the second sub-loss further comprises adjusting the second sub-loss based at least in part on an estimate of a difference between the estimated lowest cost associated with the action for operating from the future vehicle state to the termination point and a cost associated with an optimal action for reaching the termination point.

10 . The one or more non-transitory computer-readable media of claim 9 , wherein determining the estimate of the difference between the estimated lowest cost and the cost associated with the optimal action comprises one or more of:

multiplying a constant by the difference between an upper bound cost determined for the prediction node and a lower bound cost determined for the prediction node, or

randomly sampling, as the estimate, a value between zero and the upper bound cost minus the lower bound cost.

11 . The one or more non-transitory computer-readable media of claim 10 , wherein:

determining the upper bound cost comprises:

determining, using the cost function, a cost of a default action that starts from an end of the action and continues until the termination point is reached;

determining, by the cost function, the transition cost associated with the action;

determining a total prediction cost based at least in part on a summation of the cost of the default action and the transition cost of the action; and

determining the upper bound cost to be the total prediction cost based at least in part on determining the total prediction cost is a minimum prediction cost from among multiple prediction costs; and

determining the lower bound cost comprises determining a minimum total transition cost of a child branch that depends from the prediction node.

12 . The one or more non-transitory computer-readable media of claim 11 , wherein determining the total prediction cost further comprises:

determining a terminal cost associated with a last prediction node in the tree associated with the termination point and reached by the default action; and

summing the terminal cost with the cost of the default action and the transition cost of the action.

13 . The one or more non-transitory computer-readable media of claim 6 , wherein the transition cost of the action to reach the future vehicle state is a minimum transition cost from among transition costs determined for different candidate actions for operating from the first vehicle state.

14 . The one or more non-transitory computer-readable media of claim 6 , wherein determining the predicted cost comprises determining an upper bound cost for operating from a current state indicate by the root node and determining the upper bound cost comprises:

determining multiple second predicted costs for operating from the first vehicle state indicated by the prediction node;

determining a minimum second predicted cost from among the multiple second predicted costs; and

summing the minimum second predicted cost with an intervening terminal cost determined for a second action between the current state indicated by the root node and the first vehicle state indicated by the prediction node.

15 . The one or more non-transitory computer-readable media of claim 14 , wherein determining the minimum second predicted cost comprises:

determining, using the cost function, a cost of a default action that starts from an end of the action and continues until the termination point is reached;

determining, by the cost function, the transition cost associated with the action;

determining, by a second cost function or a second machine-learned model, a terminal cost associated with a last prediction node in the tree associated with the termination point and reached by the default action; and

determining a total prediction cost based at least in part on a summation of the cost of the default action, the transition cost of the action, and the terminal cost.

16 . A method comprising:

determining, by a machine-learned model, a first estimated cost of operating a vehicle from a first vehicle state indicated by a prediction node of a tree to a termination point, the first estimated cost indicating an estimated lowest cost of reaching the termination point from the first vehicle state;

determining, by the machine-learned model, a second estimated cost associated with a root node of the tree;

determining, by a cost function, a predicted cost for operating the vehicle from the root node to the termination point;

determining a first sub-loss based at least in part on a difference between the second estimated cost and the predicted cost;

determining a second sub-loss based at least in part on a difference between the first estimated cost, a third estimated cost determined by the machine-learned model for a future vehicle state following the first vehicle state or an expected value of the third estimated cost, and a transition cost of an action to operate from the future vehicle state; and

modifying, based at least in part on the first sub-loss and the second sub-loss, a parameter of the machine-learned model.

17 . The method of claim 16 , wherein determining the second sub-loss further comprises weighting, based at least in part on a convergence of a tree search that generated the tree, the difference between the first estimated cost, the third estimated cost or the expected value of the third estimated cost, and the transition cost of the action to operate from the future vehicle state.

18 . The method of claim 17 , wherein weighting based at least in part on the convergence comprises determining increasing a weight as a difference between a upper bound cost determined for the prediction node and a lower bound cost determined for the prediction node decreases.

19 . The method of claim 16 , wherein determining the second sub-loss further comprises adjusting the second sub-loss based at least in part on an estimate of a difference between the estimated lowest cost associated with the action for operating from the future vehicle state to the termination point and a cost associated with an optimal action for reaching the termination point.

20 . The method of claim 19 , wherein determining the estimate of the difference between the estimated lowest cost and the cost associated with the optimal action comprises one or more of:

multiplying a constant by the difference between an upper bound cost determined for the prediction node and a lower bound cost determined for the prediction node, or

randomly sampling, as the estimate, a value between zero and the upper bound cost minus the lower bound cost.