# US 2025/0206342 A1 · Trajectory planning based on tree search expansion

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

- Number: US 2025/0206342 A1
- Document ID: US20250206342A1
- Status: Published application
- Kind: A1
- Application number: 18/394,408
- Filed: 2023-12-22
- Published: 2025-06-26
- Earliest claimed: 2023-12-22
- Assignees: Zoox, Inc.
- Applicants: Zoox, Inc.
- Inventors: Timothy Caldwell; Yan Chang; Aaron Huang; Gary Linscott; Peter Scott Schleede; Ke Sun; Xianan Huang
- Web page: https://patentgrep.com/patent/US20250206342A1

## CPC

- B60W 60/0011: {involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles}
- 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

## Abstract

Techniques for determining a vehicle trajectory that causes a vehicle to navigate in an environment relative to one or more objects are described herein. In some cases, the techniques described herein relate to selectively expanding a tree structure (e.g., a decision tree structure) to efficiently search for simulation data that can be used to evaluate vehicle control trajectories. The tree structure may include state nodes representing observed and/or predicted environment states, and action nodes representing candidate actions the vehicle may take. By selectively and incrementally expanding the tree structure, more optimal trajectories can be determined without exhaustively evaluating every possible outcome.

## Claims

### Claim 1

A system comprising:
one or more processors; and
one or more non-transitory computer-readable media storing computer-executable instructions that, when executed, cause the one or more processors to perform operations comprising:
receiving a set of actions for controlling a vehicle through an environment;
generating a tree structure by:
creating a plurality of nodes associated with controlling the vehicle in accordance with an action of the set of actions over a period of time corresponding to a receding horizon;
determining, for an intermediate node and based at least on a machine learned model, an estimated cost associated with a trajectory passing from a root node to the intermediate node;
determining, based on the estimated cost, whether to expand the intermediate node;
expanding a set of nodes that are deeper than the intermediate node to an end of the period of time; and
determining whether to include a final node in the tree structure based at least in part on whether a corresponding trace reaches a termination state;
determining, based at least in part on the tree structure, a trace through the tree structure having a lowest cost, the trace associated with an optimal trajectory; and
controlling the vehicle based at least in part on the optimal trajectory.

### Claim 2 (depends on 1)

The system of claim 1, wherein the intermediate node is associated with a set of layers of the tree structure that excludes a first layer and a final layer of tree structure.

### Claim 3 (depends on 1)

The system of claim 1, wherein the intermediate node is expanded based on the estimated cost and a known cost associated with reaching a state corresponding to the intermediate node, and wherein the known cost is determined based on at least one of:
a safety cost associated with reaching the state,
a comfort cost associated with reaching the state, or
a measure determined based on compliance of an action associated with the state with a policy.

### Claim 4 (depends on 1)

The system of claim 1, wherein the set of actions comprises at least one of:
slowing the vehicle down,
turning the vehicle to left,
turning the vehicle to right, or
speeding the vehicle up.

### Claim 5 (depends on 1)

The system of claim 1, the operations comprising:
expanding the intermediate node and refraining from expanding a second intermediate node based at least in part on determining that the estimated cost associated with the intermediate node exceeds a second estimated cost associated with the second intermediate node.

### Claim 6

A method comprising:
creating a plurality of nodes associated with a tree structure for controlling a vehicle, the tree structure comprising a root node and an intermediate node;
determining, for the intermediate node and based at least on a machine learned model, an estimated cost associated with a trajectory passing from the root node to the intermediate node;
determining, based on the estimated cost, whether to expand the intermediate node;
expanding a set of nodes that are deeper than the intermediate node to an end of a period of time;
determining, based at least in part on the tree structure, a trace through the tree structure having a lowest cost; and
controlling the vehicle based at least in part on the trace.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
expanding a node of the tree structure that is deeper in the tree structure than the intermediate node until the end of the period of time.

### Claim 8 (depends on 6)

The method of claim 6, comprising:
refraining from expanding a node of the tree structure that is deeper than the intermediate node in the tree structure based on determining that a corresponding trace fails to reach a termination state.

### Claim 9 (depends on 6)

The method of claim 6, wherein a first number of intermediate node layers is determined based on at least one of:
at least two less than a total number of layers associated with the tree structure, or
an amount of available computational resources at a time associated with generating the tree structure.

### Claim 10 (depends on 6)

The method of claim 6, further comprising:
determining a lower bound for the estimated cost based on a cost associated with reaching the intermediate node; and
determining an upper bound for the estimated cost based on a deviation between a path comprising the intermediate node and a maximum-cost path.

### Claim 11 (depends on 10)

The method of claim 10, wherein determining the tree structure comprises:
expanding a node of the tree structure with a respective tree depth value that falls below a threshold range.

### Claim 12 (depends on 10)

The method of claim 10, wherein determining the tree structure comprises:
expanding a node of the tree structure that is associated with a predefined action sequence.

### Claim 13 (depends on 6)

The method of claim 6, wherein the estimated cost is determined based on at least one of:
environment state data representing a state characteristic of an environment of the vehicle at a first predicted state associated with the intermediate node; or
object data representing a characteristic of at least one of a dynamic object or the vehicle at the first predicted state.

### Claim 14

One or more non-transitory computer-readable media storing instructions executable by one or more processors, wherein the instructions, when executed, cause the one or more processors to perform operations comprising:
creating a plurality of nodes associated with a tree structure for controlling a vehicle, the tree structure comprising a root node and an intermediate node;
determining, for the intermediate node and based at least on a machine learned model, an estimated cost associated with a trajectory passing from the root node to the intermediate node;
determining, based on the estimated cost, whether to expand the intermediate node;
expanding a set of nodes that are deeper than the intermediate node to an end of a period of time;
determining, based at least in part on the tree structure, a trace through the tree structure having a lowest cost; and
controlling the vehicle based at least in part on the trace.

### Claim 15 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, the operations further comprising:
expanding a node of the tree structure that is deeper in the tree structure than the intermediate node until the end of the period of time.

### Claim 16 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, the operations further comprising:
refraining from expanding a node of the tree structure that is deeper than the intermediate node in the tree structure based on determining that a corresponding trace fails to reach a termination state.

### Claim 17 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, wherein a first number of intermediate node layers is determined based on at least one of:
at least two less than a total number of layers associated with the tree structure, or
an amount of available computational resources at a time associated with generating the tree structure.

### Claim 18 (depends on 14)

The one or more non-transitory computer-readable media of claim 14, wherein:
determining a lower bound for the estimated cost based on a cost associated with reaching the intermediate node; and
determining an upper bound for the estimated cost based on a deviation between a path comprising the intermediate node and a maximum-cost path.

### Claim 19 (depends on 18)

The one or more non-transitory computer-readable media of claim 18, wherein determining the tree structure comprises:
expanding a node of the tree structure with a respective tree depth value that falls below a threshold range.

### Claim 20 (depends on 18)

The one or more non-transitory computer-readable media of claim 18, wherein determining the tree structure comprises:
expanding a node of the tree structure that is associated with a predefined action sequence.
