Multi-profile quadratic programming (MPQP) for optimal gap selection and speed planning of autonomous driving

A method of controlling an autonomous vehicle, the method implemented using a vehicle control system including a processor communicatively coupled to a memory device, the method comprising:

• forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, the ST graph dynamically and continuously updated based on sensor readings of the autonomous driving vehicle;
• segmenting the ST graph into cells, wherein viable cells represent discretized viable unoccupied spaces in the ST graph;
• finding passage ways for the autonomous driving vehicle based on the viable cells, wherein finding passage ways comprises:
• progressing one time step forward from an initial origin;
• expanding each passage way by combining overlapping viable cells;
• discarding each passage way having non-overlapping viable cells;
• and
• providing all expanded passage ways formed by combining the overlapping viable cells when a corresponding time segment ends;
• and
• generating a lower bound and an upper bound for each expanded passage way accounting for kinematic limits limiting movement of the autonomous driving vehicle, the lower bound and the upper bound formed by connecting a lower end and an upper end of combined overlapping viable cells forming each pathway, and
• selecting a desired expanded passage way using quadratic programming (QP) optimization when multiple expanded passage ways are found;
• wherein the lower bound and the upper bound are adjusted through the ST graph and segmented at each time segment allowing for integration of the lower and upper bounds into the QP optimization, a slack variable added to the lower bound and the upper bound preventing inequality constraints.

A method for generating operable driving areas for an autonomous driving vehicle based on a path trajectory of the autonomous driving vehicle, comprising:

• forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, the ST graph is dynamically and continuously update based on sensor readings of the autonomous driving vehicle;
• segmenting the ST graph into cells, wherein viable cells represent discretized viable unoccupied spaces in the ST graph, wherein each cell is defined at each time segment on the ST graph by minimum smin and maximum smax bounds in distance;
• finding passage ways for the autonomous driving vehicle based on the viable cells, wherein each passage way is processed separately and in parallel, wherein finding each passage way comprises:
• progressing one time step forward from an initial origin;
• expanding each passage way by combining overlapping viable cells;
• discarding each passage way having non-overlapping viable cells;
• and
• providing all expanded passage ways formed by combining the overlapping viable cells when a corresponding time segment ends;
• and
• generating a lower bound and an upper bound for each expanded passage way, accounting for kinematic limits limiting movement of the autonomous driving vehicle, wherein generating the lower bound and the upper bound of each expanded passage way comprises:
• connecting lower ends of overlapping viable cells of a respective expanded passage way;
• and
• connecting upper ends of overlapping viable cells of the respective expanded passage way;
• and
• selecting a desired expanded passage way using quadratic programming (QP) optimization when multiple expanded passage ways are found, wherein each expanded passage way is processed using QP optimization separately and in parallel;
• wherein the lower bound and the upper bound are adjusted through the ST graph and segmented at each time segment allowing for integration of the lower and upper bounds into the QP optimization, a slack variable added to the lower bound and the upper bound preventing inequality constraints.