Differential dynamic programming (DDP) based planning architecture for autonomous driving vehicles

Patent metadata

Field	Value
Publication number	US-11586209-B2
Application number	US-202016843545-A
Country	US
Kind code	B2
Filing date	Apr 8, 2020
Priority date	Apr 8, 2020
Publication date	Feb 21, 2023
Grant date	Feb 21, 2023

Abstract

In one embodiment, method performed by an autonomous driving vehicle (ADV) that determines, within a driving space, a plurality of routes from a current location of the ADV to a desired location. The method determines, for each route of the plurality of routes, an objective function to control the ADV autonomously along the route and, for each of the objective functions, performs Differential Dynamic Programming (DDP) optimization in view of a set of constraints to produce a path trajectory. The method determines whether at least one of the path trajectories satisfies each constraint and, in response to a path trajectory satisfying each of the constraints, selects the path trajectory for navigating the ADV from the current location to the desired location.

First claim

What is claimed is:

1. A computer-implemented method performed by an autonomous driving vehicle (ADV), the method comprising:
determining, within a driving space, a plurality of routes from a current location of the ADV to a desired location;
for each of the routes, performing a differential dynamic programming (DDP) optimization using an objective function in view of a first set of constraints to produce a path trajectory, including calculating a cost for the objective function;
determining whether at least one of the path trajectories satisfies each of the constraints based on the DDP optimization;
responsive to determining that at least one path trajectory satisfies each of the constraints, selecting one path trajectory having a lowest cost of the DDP optimization for navigating the ADV from the current location to the desired location; and
responsive to determining that none of the path trajectories satisfy all of the first set of constraints
automatically relaxing one or more constraints of the first set of constraints to produce a second set of constraints,
for each of the objective functions, performing the DDP optimization in view of the second set of constraints to produce a new path trajectory, and
selecting one of the new path trajectories that satisfies each constraint of the second set of constraints.

2. The method of claim 1 , wherein the first and second sets of constraints comprises at least one of a velocity range of the ADV, an acceleration range of the ADV, a distance in front of the ADV, or a speed limit within the driving space.

3. The method of claim 1 further comprising, for each of the path trajectories, ranking the path trajectory's optimized objective function based on the cost for the function, wherein, responsive to determining that at least two path trajectories satisfy each constraint of the first set of constraints, the one path trajectory that is selected has a ranked optimized objective function that is higher than other ranked optimized objective functions.

4. The method of claim 1 , wherein automatically relaxing the one or more constraints comprises at least one of increasing the one or more constraints by a predetermined threshold or removing one or more constraints, such that the second set of constraints includes the first set of constraints less than the removed one or more constraints.

5. The method of claim 1 , wherein the DDP optimization is performed upon each of the objective functions in parallel with one another.

6. The method of claim 3 , wherein each objective function includes a plurality of costs associated with navigating along its respective route, wherein ranking comprises assigning a highest rank to a path trajectory with an objective function which has a lowest subset of costs with respect to corresponding costs of other objective functions.

7. The method of claim 1 , wherein determining whether at least one of the path trajectories satisfies each constraint comprises identifying a feasible solution associated with at least one of the optimized objective functions in view of all of the constraints.

8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations, the operations comprising:
determining, within a driving space, a plurality of routes from a current location of an autonomous driving vehicle (ADVO to a desired location;
for each of the routes, performing a differential dynamic programming (DDP) optimization using an objective function in view of a first set of constraints to produce a path trajectory, including calculating a cost for the objective function;
determining whether at least one of the path trajectories satisfies each of the constraints based on the DDP optimization;
responsive to determining that at least one path trajectory satisfies each of the constraints, selecting one path trajectory having a lowest cost of the DDP optimization for navigating the ADV from the current location to the desired location; and
responsive to determining that none of the path trajectories satisfy all of the first set of constraints automatically relaxing one or more constraints of the first set of constraints to produce a second set of constraints,
for each of the objective functions, performing the DDP optimization in view of the second set of constraints to produce a new path trajectory, and
selecting one of the new path trajectories that satisfies each constraint of the second set of constraints.

9. The non-transitory machine-readable medium of claim 8 , wherein the first and second sets of constraints comprises at least one of a velocity range of the ADV, an acceleration range of the ADV, a distance in front of the ADV, or a speed limit within the driving space.

10. The non-transitory machine-readable medium of claim 8 , wherein the machine-readable medium comprises further instructions, which when executed by the processor, causes the processor to perform operations, comprising, for each of the path trajectories, ranking the path trajectory's optimized objective function based on the cost for the function, wherein in response to determining that at least two path trajectories satisfy each constraint of the set of constraints, the one path trajectory that is selected has a ranked optimized function that is higher than other ranked optimized objective functions.

11. The non-transitory machine-readable medium of claim 10 , wherein automatically relaxing the one or more constraints comprises at least one of increasing the one or more constraints by a predetermined threshold or removing one or more constraints, such that the second set of constraints includes the first set of constraints less than the removed one or more constraints.

12. The non-transitory machine-readable medium of claim 8 , wherein the DDP optimization is performed upon each of the objective functions in parallel with one another.

13. The non-transitory machine-readable medium of claim 10 , wherein each objective function includes a plurality of costs associated with navigating along its respective route, wherein the ranking comprises assigning a highest rank to a path trajectory with an objective function which has a lowest subset of costs with respect to corresponding costs of other objective functions.

14. The non-transitory machine-readable medium of claim 8 , wherein determining whether at least one of the path trajectories satisfies each constraint comprises identifying a feasible solution associated with at least one of the optimized objective functions in view of all of the constraints.

15. A data processing system, comprising:
a processor; and
a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations, the operations including
determining, within a driving space, a plurality of routes from a current location of an autonomous driving vehicle (ADV) to a desired location,
for each of the routes, performing a differential dynamic programming (DDP) optimization using an objective function in view of a first set of constraints to produce a path trajectory, including calculating a cost for the objective function,
determining whether at least one of the path trajectories satisfies each of the constraints based on the DDP optimization,
responsive to determining that at least one path trajectory satisfies each of the constraints, selecting one path trajectory having a lowest cost of the DDP optimization for navigating the ADV from the current location to the desired location,
responsive to determining that no

Assignees

• Baidu Usa Llc

Inventors

• Luo Qi
• Zhou Jinyun
• Jiang Shu
• Tao Jiaming
• Wang Yu
• Xu Jiaxuan
• Xu Kecheng
• Miao Jinghao
• Hu Jiangtao

Classifications

• G01C21/3453 Primary

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G01C21/3407

  specially adapted for specific applications · CPC title

• G01C21/165

  combined with non-inertial navigation instruments · CPC title

• G01C21/3415 Primary

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title

• B60W30/00

  Purposes of road vehicle drive control systems not related to the control of a particular sub-unit, e.g. of systems using conjoint control of vehicle sub-units · CPC title