Motion planning using spatio-temporal convex corridors

1 . A computer implemented method for motion planning for an autonomous vehicle, comprising:

receiving data defining: (i) a first dimension upper bound of a spatio-temporal convex corridor in a first spatial dimension as a concave function of time between a corridor start time and a corridor end time, and (ii) a first dimension lower bound of the spatio-temporal convex corridor in the first spatial dimension as a convex function of time between the corridor start time and the corridor end time, the first spatial dimension corresponding to a first spatio-temporal plane;

computing a plurality of control point times within the corridor start time and the corridor end time, the plurality of control point times including at least a start control point time, an end control point time and an intermediate control point time between the start control point time and the end control point time;

determining, for each control point time in the plurality of control point times, a respective first control point maximum value that corresponds to a value of the first dimension upper bound at the control point time;

determining, for each control point time in the plurality of control point times, a respective first control point minimum value that corresponds to a value of the first dimension lower bound at the control point time;

computing, for each control point time in the plurality of control point times, a respective first dimension control point value based on the respective first control point maximum value and the respective first control point minimum value for the control point time, the respective first dimension control point values collectively defining a first curve segment that is within the first dimension upper bound and the first dimension lower bound of the spatio-temporal convex corridor; and

outputting a planned trajectory for controlling an operation of the autonomous vehicle based on the first curve segment.

2 . The method of claim 1 wherein computing the respective first dimension control point values is performed to collectively optimize a first defined cost function for the first curve segment through the spatio-temporal convex corridor in the first spatio-temporal plane.

3 . The method of claim 1 wherein the first spatial dimension corresponds to one of: (i) a longitudinal distance along a tangent vector of a road and (ii) a lateral distance to the road along a normal vector of the road.

4 . The method of claim 1 wherein the first spatial dimension corresponds to a distance axis in a three dimensional Cartesian coordinate system having time as another axis.

5 . The method of claim 1 wherein:

the received data also defines: (iii) a second dimension upper bound of the spatio-temporal convex corridor in a second spatial dimension as a concave function of time between the corridor start time and corridor end time, and (iv) a second dimension lower bound of the spatio-temporal convex corridor in the second spatial dimension as a convex function of time between the corridor start time and the corridor end time, the second spatial dimension corresponding to a second spatio-temporal plane that coincides in time with the first spatio-temporal plane;

the method comprising:

determining, for each control point time of the plurality of control point times, a respective second control point maximum value that corresponds to a value of the second dimension upper bound at the control point time;

determining, for each control point time of the plurality of control point times, a respective second control point minimum that corresponds to a value of the second dimension lower bound at the control point time;

computing, for each control point time in the plurality of control point times, a respective second dimension control point value based on the respective second control point maximum value and the respective second control point minimum value for the control point time, the respective second dimension control point values collectively defining a second curve segment that falls within the second dimension upper bound of the spatio-temporal convex corridor and the second dimension upper bound of the spatio-temporal convex corridor;

wherein the planned trajectory is outputted based on both the first curve segment and the second curve segment.

6 . The method of claim 5 wherein computing the respective second dimension control point values is performed to collectively optimize a second defined cost function for the second curve segment through the spatio-temporal convex corridor in the second spatio-temporal plane.

7 . The method of claim 5 wherein the first spatial dimension corresponds x of a road and the second spatial dimension corresponds to a lateral distance to the road along a normal vector of the road.

8 . The method of claim 5 wherein the first spatial dimension and second spatial dimension correspond respectively to a first distance axis and a second distance axis in a three dimensional Cartesian coordinate system having time as a third axis.

9 . The method of claim 1 wherein the first curve segment is an n-order parametric curve and the plurality of control point times includes n+1 plurality of control point times that are uniformly spaced in time.

10 . The method of claim 9 wherein the first curve segment is an n-order Bezier curve.

11 . The method of claim 9 wherein the first curve segment is an n-order B-spline curve.

12 . The method of claim 1 wherein the received data defines respective first dimension upper bounds and first dimension lower bounds for a plurality of successive spatio-temporal convex corridors; respective first curve segments are generated for each of the successive spatio-temporal convex corridors; and the planned trajectory for the autonomous vehicle extends through the plurality of successive spatio-temporal convex corridors and is computed based on the respective first curve segments.

13 . The method of claim 12 comprising computing constraints for each of the successive spatio-temporal convex corridors to provide continuity for the planned trajectory that extends through the successive spatio-temporal convex corridors, wherein the respective first curve segments generated for each of the successive spatio-temporal convex corridors are also based on the constraints.

14 . A system for path planning for an autonomous vehicle, the system comprising a processing system comprising one or more processors and one or more memories coupled to the one or more processors, the one or more memories storing executable instructions that, when executed by the one or more processors, cause the system to perform a method comprising:

receiving data defining: (i) a first dimension upper bound of a spatio-temporal convex corridor in a first spatial dimension as a concave function of time between a corridor start time and a corridor end time, and (ii) a first dimension lower bound of the spatio-temporal convex corridor in the first spatial dimension as a convex function of time between the corridor start time and the corridor end time, the first spatial dimension corresponding to a first spatio-temporal plane;

computing a plurality of control point times within the corridor start time and the corridor end time, the plurality of control point times including at least a start control point time, an end control

point time and an intermediate control point time between the start control point time and the end control point time;

determining, for each control point time in the plurality of control point times, a respective first control point maximum value that corresponds to a value of the first dimension upper bound at the control point time;

determining, for each control point time in the plurality of control point times, a respective first control point minimum value that corresponds to a value of the first dimension lower bound at the control point time;

computing, for each control point time in the plurality of control point times, a respective first dimension control point value based on the respective first control point maximum value and the respective first control point minimum value for the control point time, the respective first dimension control point values collectively defining a first curve segment that is within the first dimension upper bound and the first dimension lower bound of the spatio-temporal convex corridor; and

outputting a planned trajectory for controlling an operation of the autonomous vehicle based on the first curve segment.

15 . The system of claim 14 wherein computing the first dimension control point values is performed to collectively optimize a first defined cost function for the first curve segment through the spatio-temporal convex corridor in the first spatio-temporal plane.

16 . The system of claim 14 wherein the first spatial dimension corresponds to one of: (i) a longitudinal distance along a tangent vector of a road and (ii) a lateral distance to the road along a normal vector of the road.

17 . The system of claim 14 wherein the first spatial dimension corresponds to a distance axis in a three dimensional Cartesian coordinate system having time as another axis.

18 . The system of claim 14 wherein:

the received data also defines: (iii) a second dimension upper bound of the spatio-temporal convex corridor in a second spatial dimension as a concave function of time between the corridor start time and corridor end time, and (iv) a second dimension lower bound of the spatio-temporal convex corridor in the second spatial dimension as a convex function of time between the corridor start time and the corridor end time, the second spatial dimension corresponding to a second spatio-temporal plane that coincides in time with the first spatio-temporal plane;

the method comprising:

determining, for each control point time of the plurality of control point times, a respective second control point maximum value that corresponds to a value of the second dimension upper bound at the control point time;

determining, for each control point time of the plurality of control point times, a respective second control point minimum that corresponds to a value of the second dimension lower bound at the control point time;

computing, for each control point time in the plurality of control point times, a respective second dimension control point value based on the respective second control point maximum value and the respective second control point minimum value for the control point time, the respective second dimension control point values collectively defining a second curve segment that falls within the second dimension upper bound of the spatio-temporal convex corridor and the second dimension upper bound of the spatio-temporal convex corridor;

wherein the planned trajectory is outputted based on both the first curve segment and the second curve segment.

19 . The system of claim 18 wherein computing the respective second dimension control point values is performed to collectively optimize a second defined cost function for the second curve segment through the spatio-temporal convex corridor in the second spatio-temporal plane.

20 . A non-transient computer-readable medium storing processor executable instructions which, when executed by a processor of a processing system, cause the processing system to perform a method comprising:

receiving data defining: (i) a first dimension upper bound of a spatio-temporal convex corridor in a first spatial dimension as a concave function of time between a corridor start time and a corridor end time, and (ii) a first dimension lower bound of the spatio-temporal convex corridor in the first spatial dimension as a convex function of time between the corridor start time and the corridor end time, the first spatial dimension corresponding to a first spatio-temporal plane;

computing a plurality of control point times within the corridor start time and the corridor end time, the plurality of control point times including at least a start control point time, an end control point time and an intermediate control point time between the start control point time and the end control point time;

determining, for each control point time in the plurality of control point times, a respective first control point maximum value that corresponds to a value of the first dimension upper bound at the control point time;

determining, for each control point time in the plurality of control point times, a respective first control point minimum value that corresponds to a value of the first dimension lower bound at the control point time;

computing, for each control point time in the plurality of control point times, a respective first dimension control point value based on the respective first control point maximum value and the respective first control point minimum value for the control point time, the respective first dimension ontrol point values collectively defining a first curve segment that is within the first dimension upper bound and the first dimension lower bound of the spatio-temporal convex corridor; and

outputting a planned trajectory for controlling an operation of the autonomous vehicle based on the first curve segment.