# US 2024/0199083 A1 · Machine-learned cost estimation in tree search trajectory generation for vehicle control

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0199083 A1
- Document ID: US20240199083A1
- Status: Published application
- Kind: A1
- Application number: 18/084,419
- Filed: 2022-12-19
- Published: 2024-06-20
- Earliest claimed: 2022-12-19
- Assignees: Zoox, Inc.
- Applicants: Zoox, Inc.
- Inventors: Yan Chang; Aaron Huang; Peter Scott Schleede; Gary Linscott; Marin Kobilarov; Ethan Miller Pronovost; Ke Sun; Xiangyu Xie
- Web page: https://patentgrep.com/patent/US20240199083A1

## CPC

- B60W 60/0027: {using trajectory prediction for other traffic participants}
- B60W 50/0097: {Predicting future conditions}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 20/00: Machine learning
- B60W 30/12: Lane keeping
- B60W 30/18163: {Lane change; Overtaking manoeuvres}
- B60W 2554/20: Static objects
- B60W 2554/40: Dynamic objects, e.g. animals, windblown objects
- B60W: CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A machine-learned architecture for estimating the cost determined by a cost function for a prediction node of a tree search for exploring potential paths for controlling a vehicle may include two portions: a set up portion that includes models trained to process static data and a second portion that processes dynamic object data. The respective portions of the architecture may comprise various models that determine intermediate outputs that may be projected into a space associated with estimated cost. That estimated cost may identify an estimate of an output of the cost function for paths that are based on a particular prediction node of the tree search.

## Claims

### Claim 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:
receiving environment state data indicating static characteristics of an environment associated with a vehicle;
receiving dynamic object data indicating at least one of a historical or a current state of at least one of a dynamic object or the vehicle;
receiving prediction node data indicating one or more actions performed by the vehicle to reach a future state indicated by a prediction node of a tree search, the future state comprising future vehicle state and at least one of a predicted environment state, or a predicted dynamic object state;
determining, by a first machine-learned model and based at least in part on the environment state data, environment features;
determining, by a second machine-learned model and based at least in part on the dynamic object data, dynamic features;
initializing a third machine-learned model based at least in part on the dynamic features;
determining, by the third machine-learned model and based at least in part on the environment features and the prediction node data, a first output;
aggregating, by an encoder, the first output and the dynamic features as an encoded output;
determining, by a decoder and based at least in part on the encoded output, an estimated cost; and
determining a trajectory for controlling a vehicle based at least in part on the estimated cost.

### Claim 2 (depends on 1)

The system of claim 1, wherein:
the estimated cost is associated with the prediction node indicating a predicted state of the environment, the dynamic object, and the vehicle at a future time; and
the estimated cost estimates a total cost determined by a cost function for one or more candidate actions that may be taken by the vehicle at the future time based on the predicted state of the environment to reach a termination point.

### Claim 3 (depends on 2)

The system of claim 2, wherein determining the total cost associated with one or more candidate trajectories by the cost function comprises determining a cost associated with a first candidate action of the one or more candidate actions and wherein the cost function determines the cost based at least in part on at least one of:
a proximity sub-cost based at least in part on a distance the first candidate action would bring the vehicle from an object location or predicted object location;
a safety sub-cost associated with the first candidate action;
a comfort sub-cost associated with the first candidate action; or
a progress sub-cost associated with the first candidate action.

### Claim 4 (depends on 2)

The system of claim 2, wherein the operations further comprising training at least one of the first machine-learned model, the second machine-learned model, the third machine-learned model, the encoder, or the decoder based at least in part on:
determining a cost based at least in part on the cost function and a candidate action associated with the prediction node;
determining a difference between the cost and the estimated cost; and
altering a parameter of at least one of the first machine-learned model, the second machine-learned model, the third machine-learned model, the encoder, or the decoder to reduce the difference.

### Claim 5 (depends on 1)

The system of claim 1, wherein initializing the third machine-learned model comprises:
determining a portion of the dynamic features associated with the dynamic object; and
adding the portion of the dynamic features to at least one of a node or hidden layer of the third machine-learned model.

### Claim 6 (depends on 1)

The system of claim 1, wherein the first machine-learned model, the second machine-learned model, and the third machine-learned model are portions of a single machine-learned model.

### Claim 7

A method comprising:
receiving environment state data indicating static characteristics of an environment associated with a vehicle;
receiving dynamic object data indicating at least one of a historical or a current state of at least one of a dynamic object or the vehicle;
determining, by a first machine-learned model and based at least in part on the environment state data, environment features;
determining, by a second machine-learned model and based at least in part on the dynamic object data, dynamic features;
initializing a third machine-learned model based at least in part on the dynamic features;
determining, by the third machine-learned model and based at least in part on the environment features and prediction node data indicating one or more actions performed by the vehicle to reach a future state indicated by a prediction node of a tree search, a first output;
aggregating, by an encoder, the first output and the dynamic features as an encoded output;
determining, by a decoder and based at least in part on the encoded output, an estimated cost; and
determining a trajectory for controlling a vehicle based at least in part on the estimated cost.

### Claim 8 (depends on 7)

The method of claim 7, wherein:
the estimated cost is associated with the prediction node indicating a predicted state of the environment, the dynamic object, and the vehicle at a future time; and
the estimated cost estimates a total cost output by a cost function for one or more candidate actions that may be taken by the vehicle at the future time based on the predicted state of the environment to reach a termination point.

### Claim 9 (depends on 8)

The method of claim 8, wherein determining the total cost associated with one or more candidate actions by the cost function comprises determining a cost associated with a first candidate action of the one or more candidate actions and wherein the cost function determines the cost based at least in part on at least one of:
a proximity sub-cost based at least in part on a distance the first candidate action would bring the vehicle from an object location or predicted object location;
a safety sub-cost associated with the first candidate action;
a comfort sub-cost associated with the first candidate action; or
a progress sub-cost associated with the first candidate action.

### Claim 10 (depends on 8)

The method of claim 8, further comprising training at least one of the first machine-learned model, the second machine-learned model, the third machine-learned model, the encoder, or the decoder based at least in part on:
determining a cost based at least in part on the cost function and a candidate action associated with the prediction node;
determining a difference between the cost and the estimated cost; and
altering a parameter of at least one of the first machine-learned model, the second machine-learned model, the third machine-learned model, the encoder, or the decoder to reduce the difference.

### Claim 11 (depends on 7)

The method of claim 7, wherein initializing the third machine-learned model comprises:
determining a portion of the dynamic features associated with the dynamic object; and
adding the portion of the dynamic features to at least one of a node or hidden layer of the third machine-learned model.

### Claim 12 (depends on 7)

The method of claim 7, wherein the first machine-learned model, the second machine-learned model, and the third machine-learned model are portions of a single machine-learned model.

### Claim 13 (depends on 8)

The method of claim 8, wherein:
the prediction node is a first prediction node among a plurality of prediction nodes of the tree search and the estimated cost is a first estimated cost associated with the first prediction node;
the method further comprises:
determining multiple estimated costs associated with the plurality of prediction nodes, and
determining that the first estimated cost is a lowest estimated cost from among the multiple estimated costs; and
determining the trajectory comprises:
determining, by the cost function, a cost for each of a different series of candidate actions that are based at least in part on a future state indicated by the first prediction node; and
determining the trajectory based at least in part on a first series of candidate actions associated with a lowest cost.

### Claim 14

A non-transitory computer-readable medium storing processor-executable instructions that, when executed by one or more processors, cause one or more processors to perform operations comprising:
receiving environment state data indicating static characteristics of an environment associated with a vehicle;
receiving dynamic object data indicating at least one of a historical or a current state of at least one of a dynamic object or the vehicle;
determining, by a first machine-learned model and based at least in part on the environment state data, environment features;
determining, by a second machine-learned model and based at least in part on the dynamic object data, dynamic features;
initializing a third machine-learned model based at least in part on the dynamic features;
determining, by the third machine-learned model and based at least in part on the environment features and prediction node data indicating one or more actions performed by the vehicle to reach a future state indicated by a prediction node of a tree search, a first output;
aggregating, by an encoder, the first output and the dynamic features as an encoded output;
determining, by a decoder and based at least in part on the encoded output, an estimated cost; and
determining a trajectory for controlling a vehicle based at least in part on the estimated cost.

### Claim 15 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein:
the estimated cost is associated with the prediction node indicating a predicted state of the environment, the dynamic object, and the vehicle at a future time; and
the estimated cost estimates a total cost output by a cost function for one or more candidate actions that may be taken by the vehicle at the future time based on the predicted state of the environment to reach a termination point.

### Claim 16 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein determining the total cost associated with one or more candidate actions by the cost function comprises determining a cost associated with a first candidate action of the one or more candidate actions and wherein the cost function determines the cost based at least in part on at least one of:
a proximity sub-cost based at least in part on a distance the first candidate action would bring the vehicle from an object location or predicted object location;
a safety sub-cost associated with the first candidate action;
a comfort sub-cost associated with the first candidate action; or
a progress sub-cost associated with the first candidate action.

### Claim 17 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the operations further comprise training at least one of the first machine-learned model, the second machine-learned model, the third machine-learned model, the encoder, or the decoder based at least in part on:
determining a cost based at least in part on the cost function and a candidate action associated with the prediction node;
determining a difference between the cost and the estimated cost; and
altering a parameter of at least one of the first machine-learned model, the second machine-learned model, the third machine-learned model, the encoder, or the decoder to reduce the difference.

### Claim 18 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein initializing the third machine-learned model comprises:
determining a portion of the dynamic features associated with the dynamic object; and
adding the portion of the dynamic features to at least one of a node or hidden layer of the third machine-learned model.

### Claim 19 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the first machine-learned model, the second machine-learned model, and the third machine-learned model are portions of a single machine-learned model.

### Claim 20 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein:
the prediction node is a first prediction node among a plurality of prediction nodes of the tree search and the estimated cost is a first estimated cost associated with the first prediction node;
the operations further comprise:
determining multiple estimated costs associated with the plurality of prediction nodes, and
determining that the first estimated cost is a lowest estimated cost from among the multiple estimated costs; and
determining the trajectory comprises:
determining, by the cost function, a cost for each of a different series of candidate actions that are based at least in part on a future state indicated by the first prediction node; and
determining the trajectory based at least in part on a first series of candidate actions associated with a lowest cost from among the costs associated with the different series of candidate actions.

### Claim 21 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein the cost function is a first cost function, the cost is a first cost, the difference is a first difference, and the operations further comprise:
receiving a second cost function;
determining a second cost based at least in part on the second cost function and the candidate action associated with the prediction node;
determining a second difference between the second cost and the estimated cost; and
altering the parameter of at least one of the first machine-learned model, the second machine-learned model, the third machine-learned model, the encoder, or the machine-learned decoder to reduce the second difference.

### Claim 22 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein a candidate action of the one or more candidate actions comprises one or more of:
a control policy for the vehicle to target,
maintaining a trajectory,
staying in a lane,
changing lanes,
accelerating, or
decelerating.
