# US 12,179,798 B2 · Tree policy planning for autonomous vehicle driving solutions

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

- Number: US 12,179,798 B2
- Document ID: US12179798B2
- Status: Granted
- Kind: B2
- Application number: 17/132,806
- Filed: 2020-12-23
- Published: 2021-05-13
- Granted: 2024-12-31
- Earliest claimed: 2018-12-05
- Assignees: Waymo LLC
- Applicants: Waymo LLC
- Inventors: Jared Stephen Russell; Clovis Scotti
- Web page: https://patentgrep.com/patent/US12179798B2

## CPC

- B60W 60/0016: {of the vehicle or its occupants}
- B60W 50/0097: {Predicting future conditions}
- B60W 60/0011: {involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles}
- B60W 60/00274: {considering possible movement changes}
- G08G 1/166: {for active traffic, e.g. moving vehicles, pedestrians, bikes}
- B60W 2552/53: Road markings, e.g. lane marker or crosswalk
- B60W 2554/4041: Position
- B60W 2554/4042: Longitudinal speed
- B60W 2554/4044: Direction of movement, e.g. backwards
- B60W 2556/10: Historical data
- B60W 2556/50: of positioning data, e.g. GPS [Global Positioning System] data
- 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
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

An autonomous vehicle is operated along a route according to a nominal driving solution that takes into account one or more first constraints including a first predicted trajectory for an agent vehicle. An alternate scenario is determined based on one or more second external constraints that include a second predicted trajectory for the agent vehicle different from the first predicted trajectory. A risk factor on the nominal driving solution is determined for the alternative scenario, and a secondary driving solution is determined based on the risk factor and the one or more second external constraints. A candidate switching point is identified where the secondary driving solution diverges from the nominal driving solution, and the nominal driving solution is revised up to the candidate switching point based on the secondary driving solution. The autonomous vehicle is then operated based on the revised nominal driving solution.

## Claims

### Claim 1

A method for operating an autonomous vehicle, the method comprising:
detecting, by one or more computing devices, an agent vehicle in an environment of the autonomous vehicle;
determining, by the one or more computing devices, a nominal driving solution for the autonomous vehicle along a portion of a route on a road based on one or more first external constraints, the one or more first external constraints including a first predicted trajectory of a plurality of possible trajectories for the agent vehicle;
determining, by the one or more computing devices, an alternate scenario that includes one or more second external constraints that are different from the one or more first external constraints, the one or more second external constraints including a second predicted trajectory of the plurality of possible trajectories for the agent vehicle;
determining, by the one or more computing devices, a risk factor on the nominal driving solution for the alternate scenario;
determining, by the one or more computing devices, a secondary driving solution based on the risk factor and the one or more second external constraints in the alternate scenario;
identifying, by the one or more computing devices, a candidate switching point where the secondary driving solution diverges from the nominal driving solution;
revising, by the one or more computing devices, the nominal driving solution up to the candidate switching point based on the secondary driving solution; and
operating, by the one or more computing devices, the autonomous vehicle based on the revised nominal driving solution.

### Claim 2 (depends on 1)

The method of claim 1, wherein the determining the nominal driving solution includes selecting the one or more first external constraints that allow a longest distance traveled by the autonomous vehicle along the portion of the route.

### Claim 3 (depends on 1)

The method of claim 1, wherein the determining the nominal driving solution includes selecting the one or more first external constraints that are most likely to occur along the portion of the route.

### Claim 4 (depends on 1)

The method of claim 1, wherein the determining of the alternate scenario includes selecting the one or more second external constraints based on whether the one or more second external constraints meet a minimum threshold likelihood of occurring.

### Claim 5 (depends on 1)

The method of claim 1, wherein the determining of the alternate scenario includes selecting the one or more second external constraints based on whether the one or more second external constraints meet a minimum threshold level of risk posted to the autonomous vehicle along the portion of the route.

### Claim 6 (depends on 1)

The method of claim 1, wherein the determining the risk factor is based on where along the portion of the route that a level of risk to the autonomous vehicle posed by the alternate scenario exceeds a maximum threshold level of risk.

### Claim 7 (depends on 1)

The method of claim 1, wherein the candidate switching point is where a threshold confidence level is reached regarding whether the alternate scenario has occurred.

### Claim 8 (depends on 1)

The method of claim 1, wherein the revising of the nominal driving solution includes adjusting a speed profile to prepare the autonomous vehicle for a potential switch to the secondary driving solution.

### Claim 9

A system comprising:
a perception system; and
one or more computing devices configured to:
detect, using the perception system, an agent vehicle in an environment of an autonomous vehicle;
determine a nominal driving solution for the autonomous vehicle along a portion of a route on a road based on one or more first external constraints, the one or more first external constraints including a first predicted trajectory of a plurality of possible trajectories for the agent vehicle;
determine an alternate scenario that includes one or more second external constraints that are different from the one or more first external constraints, the one or more second external constraints including a second predicted trajectory of the plurality of possible trajectories for the agent vehicle;
determine a risk factor on the nominal driving solution for the alternate scenario;
determine a secondary driving solution based on the risk factor and the one or more second external constraints in the alternate scenario;
identify a candidate switching point where the secondary driving solution diverges from the nominal driving solution;
revise the nominal driving solution up to the candidate switching point based on the secondary driving solution; and
operate the autonomous vehicle based on the revised nominal driving solution.

### Claim 10 (depends on 9)

The system of claim 9, wherein the nominal driving solution is determined based on the one or more first external constraints that allow a longest distance traveled by the autonomous vehicle along the portion of the route.

### Claim 11 (depends on 9)

The system of claim 9, wherein the nominal driving solution is determined based on the one or more first external constraints that are most likely to occur along the portion of the route.

### Claim 12 (depends on 11)

The system of claim 11, wherein the nominal driving solution is revised based on an adjusted speed profile that prepares the autonomous vehicle for a potential switch to the secondary driving solution.

### Claim 13 (depends on 9)

The system of claim 9, wherein the alternate scenario is determined based on the one or more second external constraints that have a minimum threshold likelihood of occurring and based on the one or more second external constraints that have a minimum threshold level of risk posted to the autonomous vehicle along the portion of the route.

### Claim 14 (depends on 9)

The system of claim 9, wherein the risk factor is determined based on where along the portion of the route that a level of risk to the autonomous vehicle posed by the alternate scenario exceeds a maximum threshold level of risk.

### Claim 15 (depends on 9)

The system of claim 9, wherein the candidate switching point is where a threshold confidence level is reached regarding whether the alternate scenario has occurred.

### Claim 16 (depends on 9)

The system of claim 9, further comprising the autonomous vehicle.

### Claim 17

A non-transitory, tangible computer-readable medium on which computer-readable instructions of a program are stored, the instructions, when executed by one or more computing devices, cause the one or more computing devices to perform a method for operating an autonomous vehicle, the method comprising:
detecting an agent vehicle in an environment of the autonomous vehicle;
determining a nominal driving solution for the autonomous vehicle along a portion of a route on a road based on one or more first external constraints, the one or more first external constraints including a first predicted trajectory of a plurality of possible trajectories for the agent vehicle;
determining an alternate scenario that includes one or more second external constraints that are different from the one or more first external constraints, the one or more second external constraints including a second predicted trajectory of the plurality of possible trajectories for the agent vehicle;
determining a risk factor on the nominal driving solution for the alternate scenario;
determining a secondary driving solution based on the risk factor and the one or more second external constraints in the alternate scenario;
identifying a candidate switching point where the secondary driving solution diverges from the nominal driving solution;
revising the nominal driving solution up to the candidate switching point based on the secondary driving solution; and
operating the autonomous vehicle based on the revised nominal driving solution.

### Claim 18 (depends on 17)

The medium of claim 17, wherein the determining the nominal driving solution includes selecting the one or more first external constraints that allow a longest distance traveled by the autonomous vehicle along the portion of the route.

### Claim 19 (depends on 17)

The medium of claim 17, wherein the determining the nominal driving solution includes selecting the one or more first external constraints that are most likely to occur along the portion of the route.

### Claim 20 (depends on 17)

The medium of claim 17, wherein the determining the risk factor is based on where along the portion of the route that a level of risk to the autonomous vehicle posed by the alternate scenario exceeds a maximum threshold level of risk.