Relaxation optimization model to plan an open space trajectory for autonomous vehicles

Patent metadata

Field	Value
Publication number	US-11409284-B2
Application number	US-201916413315-A
Country	US
Kind code	B2
Filing date	May 15, 2019
Priority date	May 15, 2019
Publication date	Aug 9, 2022
Grant date	Aug 9, 2022

Abstract

In one embodiment, an open space model is generated for a system to plan trajectories for an ADV in an open space. The system perceives an environment surrounding an ADV including one or more obstacles. The system determines a target function for the open space model based on constraints for the one or more obstacles and map information. The system iteratively, performs a first quadratic programming (QP) optimization on the target function based on a first trajectory while fixing a first set of variables, and performs a second QP optimization on the target function based on a result of the first QP optimization while fixing a second set of variables. The system generates a second trajectory based on results of the first and the second QP optimizations to control the ADV autonomously according to the second trajectory.

First claim

What is claimed is:

1. A computer-implemented method for operating an autonomous driving vehicle, the method comprising:
determining a target function for an open space model based on one or more obstacles and map information within a proximity of an autonomous driving vehicle (ADV);
iteratively, until a predetermined converged condition is satisfied,
performing a first quadratic programming (QP) optimization on the target function based on a first trajectory while fixing a first set of variables of the target function, and
performing a second QP optimization on the target function based on a result of the first QP optimization while fixing a second set of variables of the target function, wherein the first set of variables of the target function includes dual variables that are used to calculate a distance between each of the one or more obstacles and the ADV;

generating a second trajectory based on results of the first and the second QP optimizations; and
controlling the ADV autonomously according to the second trajectory.

2. The method of claim 1 , further comprising applying a hybrid A-star (A*) search algorithm to the open space model to generate the first trajectory.

3. The method of claim 1 , wherein the second set of variables includes variables for control of the ADV and trajectory.

4. The method of claim 1 , wherein the target function includes a quadratic cost function for the first QP optimization and the second QP optimization.

5. The method of claim 1 , wherein the open space model is to generate a trajectory for the ADV without following a reference line or traffic lines.

6. The method of claim 1 , wherein the open space model includes a vehicle dynamic model for the ADV.

7. 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 a target function for an open space model based on one or more obstacles and map information within a proximity of an autonomous driving vehicle (ADV);
iteratively, until a predetermined converged condition is satisfied,
performing a first quadratic programming (QP) optimization on the target function based on a first trajectory while fixing a first set of variables of the target function, and
performing a second QP optimization on the target function based on a result of the first QP optimization while fixing a second set of variables of the target function, wherein the first set of variables of the target function includes dual variables that are used to calculate a distance between each of the one or more obstacles and the ADV;

generating a second trajectory based on results of the first and the second QP optimizations; and
controlling the ADV autonomously according to the second trajectory.

8. The non-transitory machine-readable medium of claim 7 , wherein the operations further comprise applying a hybrid A-star (A*) search algorithm to the open space model to generate the first trajectory.

9. The non-transitory machine-readable medium of claim 7 , wherein the second set of variables includes variables for control of the ADV and trajectory.

10. The non-transitory machine-readable medium of claim 7 , wherein the target function includes a quadratic cost function for the first and the second QP optimizations.

11. The non-transitory machine-readable medium of claim 7 , wherein the open space model is to generate a trajectory for the ADV without following a reference line or traffic lines.

12. The non-transitory machine-readable medium of claim 7 , wherein the open space model includes a vehicle dynamic model for the ADV.

13. 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 a target function for an open space model based on one or more obstacles and map information within a proximity of an autonomous driving vehicle (ADV),
iteratively, until a predetermined converged condition is satisfied,
performing a first quadratic programming (QP) optimization on the target function based on a first trajectory while fixing a first set of variables of the target function, and
performing a second QP optimization on the target function based on a result of the first QP optimization while fixing a second set of variables of the target function, wherein the first set of variables of the target function includes dual variables that are used to calculate a distance between each of the one or more obstacles and the ADV,

generating a second trajectory based on results of the first and the second QP optimizations, and
controlling the ADV autonomously according to the second trajectory.

14. The system of claim 13 , wherein the operations further comprise applying a hybrid A-star (A*) search algorithm to the open space model to generate the first trajectory.

15. The system of claim 13 , wherein the second set of variables includes variables for control of the ADV and trajectory.

16. The system of claim 13 , wherein the target function includes a quadratic cost function for the first and the second QP optimizations.

17. The system of claim 13 , wherein the open space model is to generate a trajectory for the ADV without following a reference line or traffic lines.

18. The system of claim 13 , wherein the open space model includes a vehicle dynamic model for the ADV.

Assignees

• Baidu Usa Llc

Inventors

• He Runxin
• Zhou Jinyun
• Luo Qi
• Song Shiyu
• Miao Jinghao
• Hu Jiangtao
• Wang Yu
• Xu Jiaxuan
• Jiang Shu

Classifications

• G06F16/9537

  Spatial or temporal dependent retrieval, e.g. spatiotemporal queries · CPC title

• G05B13/042 Primary

  in which a parameter or coefficient is automatically adjusted to optimise the performance · CPC title

• G05D1/0212 Primary

  with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287) · CPC title

• G05D2201/0213

  Physics · mapped topic

• G05D1/0088 Primary

  characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00) · CPC title