Motion planning is one of the key modules in autonomous driving systems. The task of motion planning in a dynamic traffic environment is to generate trajectories for a lowlevel controller to follow considering collision-free safety constraints, dynamic feasibility, and comfort. A Frenet frame [1] is commonly used for motion planning due to the significant advantage of its independence from complex road geometry. The lateral motion (in the L direction) and longitudinal motion (in the S direction) can be projected onto the reference, which is usually the centerline of the road with an arbitrary shape. Including the time dimension T , a 3D S -L -T coordinate system can be established for insightful and convenient planning.
Path-speed (or Layered planning) is a practical realtime solution to decompose a planning problem into two stages: path planning and speed planning [2]- [5]. A path (S -L) is generated in the first stage in a static or low-speed environment. The generation of the speed profile (S -T or L -T ) in the speed planning stage allows an AV to respond to dynamic obstacles. The significant limitation of layered sity, Pittsburgh, PA, the USA jdolan@andrew.cmu.edu planning is that it is prone to be suboptimal in the presence of dynamic obstacles in complicated scenarios.
Spatio-temporal planning considers spatial and temporal maneuvers simultaneously [6]- [8]. This method of direct optimization in the 3D S -L -T space is generally superior to the layered planning approach due to the larger search space. See the motivating example illustrated in Fig. 1 (discussed in detail in Section III.A): in driving scenarios involving even small deviations along the lateral direction, coupled longitudinal and lateral planning helps guarantee global optimality. Ensuring safety is the vital objective of motion planning. Many existing speed planning methods use discrete time instants to impose safety constraints. However, a provable safety guarantee independent of sampling time in continuous time space is preferable. To address this problem, the spatial corridor is widely applied in trajectory generation. We are motivated by these efforts to further extend the spatial corridor to the spatio-temporal domain to cope better with dynamic obstacles. The convex hull property of Bézier polynomials is leveraged to enforce that the continuous trajectory always falls into a safe spatio-temporal region. In addition, such an optimization problem's solution space is enlarged via our proposed trapezoidal-prism-shaped corridors.
The main contributions of our work can be briefly described as follows:
1) We propose an efficient convexification algorithm to construct 3D convex-feasible regions consisting of trapezoidal-prism-shaped corridors. 2) We provide a sufficient condition on coefficients of the Bézier polynomials to theoretically guarantee the trajectory's safety in trapezoidal-prism corridors. Compared with existing cuboidal corridors [6], the condition is relaxed and the solution space is significantly enlarged, which leads to a higher chance of finding an optimal solution. The remainder of this paper is structured as follows. We review related works in Sec. II. We introduce necessary notations and background materials in Sec. III. The 3D convex safe region construction is presented in Sec. IV. In Sec. V, we present our optimization formulation. The simulation results and analysis can be found in Sec. VI. We make concluding remarks in Sec. VII.
Speed planning techniques can be classified into three categories: 1) search and optimization; 2) sampling lattices and selecting the minimum-cost trajectory; 3) approximated optimization. The Search and optimization method searches for the best candidate speed profile and optimizes the curve for smoothness; see the post-optimization method [3], the Baidu EM motion planner [9], and the Piecewise-Jerk Speed Optimization [10]. The Sampling approach samples different speed lattices combined with path lattices. The generated local spatial-temporal trajectories are evaluated and the one with minimum cost is selected. Related works can be found in [2]- [5]. Most works in the first and the second categories conduct search and optimization directly in the S -T graph. Approximated optimization considers a vehicle dynamic model in a sequential optimization problem; see convex feasible set algorithm [11] and optimal control methods, such as model predictive control (MPC) [12] and constrained iterative linear quadratic regulator (CiLQR) [13]. The advantage of these approaches is that they mitigate the planning and control inconsistency problem since the dynamic model has already been considered in the planning layer. However, the disadvantage is the high computation cost.
The spatial corridor is widely used in trajectory generation. Some previous works generate the corridors in a static environment and cannot deal with dynamic obstacles [14], [15]. Liu et al. [16] find a convex feasible set around the reference trajectory, but the computation complexity restricts the method for real-time applications. Our previous work proposes the use of trapezoidal corridors for convexifying 2D space in the S -T graph [17]. Zhang et al. present a general convex spatio-temporal corridors-based approach [18]. Xu et al. propose using a modified vertical cell decomposition approach for speed planning in [19]. All these methods suffer from the limitations of the layered planning approach discussed in the previous section. Ding et al. use the spatiotemporal semantic corridor (SSC) method to uniformly express obstacles and traffic rules in the 3D S -L -T space [6]. However, restricting the shape of the corridors to simple cuboids drastically limits the search space for optimization in complex scenarios. Our proposed method of extending trapezoid-shaped 2D corridors in S -T to 3D S -L -T space significantly enlarges the solution space for trajectory optimization. This enables us to extend the spatial corridor to the spatio-temporal domain to cope with dynamic obstacles while meeting the real-time requirement.
Previously, monomial basis polynomials have been used to generate trajectories [1], [9]. However, these methods often fail to represent highly constrained maneuvers in the presence of dynamic obstacles. They also fail to give safety guarantees between sample points, as the constraints are only enforced/checked on a finite set of sampled points. In [20], a smooth and continuous speed profile is computed by proper curve concatenation without optimization and dynamic obstacles. Bézier polynomials combined with rectangular corridors was originated in the area of unmanned aerial vehicles (UAVs) [21], [22]. Ding et al. extended it for motion planning of unmanned ground vehicles (UGVs) [6]. The significant limitation is that the proposed cuboidal corridor representation fails to make the most of free space for optimization. In our work, we propose to use timedependent trapezoidal prism-shaped corridors and give sufficient conditions to enforce Bézier curves in these timedependent corridors for safety. It is theoretically proved that the trapezoidal prism-shaped corridors can enlarge the solution space for improved optimization.
In this section, we briefly introduce background materials on the S -L -T graph, Bézier polynomials, and trajectory representations using piecewise Bézier polynomials.
The S -L -T graph represents all traffic participants' positions at each time step including the past, current, and prediction. As an example, in Fig. 1a, we take the case of two cars moving at constant speeds for simplicity. The scenario is described as follows: car A and the ego vehicle are driving in a lane which has a static obstacle (e.g., a construction site). A lane change maneuver is enforced for both vehicles. We list the following typical entities:
1) Static obstacle (6-zero-slope-faces type): As the most simple entity, all the six faces have zero slopes, see the bird'seye view of the yellow block in Fig. 1a and the cuboid in the S -L -T plot in Fig. 1b.
2) Moving car with only longitudinal motion (4-zeroslope-faces type): Car C moving straight forward is an example shown in Fig. 1a. The top and bottom faces of Car C in Fig. 1b have zero slopes. The two faces (see another angle of view for left and right faces in Fig. 1c) are perpendicular to the S -L plane without slopes. The side length of the parallelogram along the L axis is the width of the vehicle plus the safety region. The side length of the parallelogram along the S axis is the length of the vehicle plus half the length of the ego vehicle as a safety region.
3) Moving car with longitudinal and lateral motions (2-zero-slope-faces type): Car A moving left and forward is an example shown in Fig. 1a. As we can see in Fig. 1b, only the top and down faces are zero-slope.
The 3D free space in the S -L -T graph is nonconvex in general. We propose an over-approximation of the 2-zero-slope-faces type parallelepiped, e.g., car A in Fig. 1b, into a 4-zero-slope-faces type parallelepiped, see the pink inflated space in Fig. 1b and Fig. 1d. There are two significant benefits of doing so: 1) we will show that in the presence of such parallelepipeds, we can extend our 2D corridor construction algorithm [17] to construct 3D trapezoidal prism-shaped corridors efficiently; 2) though we pay the cost of losing some space due to over-approximation, the safety corridor is still significantly larger than the existing cuboidal corridors. Note that the transformation between 2D and 3D in our method is without the loss of search space. Thus, in summary, we make a good trade-off between exactness and efficiency. The faces chosen for the overapproximation step are decided by a simple minimization of the volume of search space compromised in the process. Intuitively, if the lateral velocity is less than the longitudinal velocity of the vehicle, the corresponding faces are chosen for over-approximation.
A Bézier polynomial is a polynomial function represented by linear combinations of Bernstein bases. The nth-order Bézier polynomial is written as
where the Bernstein bases satisfy b
The coefficients of the polynomial c i (i = 0, 1, . . . , n) are also called control points. Compared to monomial polynomials, Bézier curves have the following properties:
• The time interval is defined on t ∈ [0, 1].
• The Bézier polynomial starts at control point B(0) = c 0 and ends at B(1) = c n . • Convex hull property: The Bézier curve B(t) is confined within the convex hull of control points. • Hodograph property: By the hodograph property, the derivative of B(t), Ḃ(t), can also be written as a Bézier polynomial with control points c 1 i = n•(c i+1 -c i ) , i = 0, 1, . . . , n -1. By applying the convex hull property to the derivative Bézier curve, the entire dynamical profile of the original curve B(t) can be confined within a given dynamical range.
To mitigate the numerical instability issue, piecewise Bézier polynomials with lower orders are used instead of using a high-order Bézier polynomial for the whole planning horizon. Each piece of the trajectory is associated with one trapezoidal-prism corridor. Note that B(t) is defined on a fixed time interval [0, 1]. For a whole trajectory with m + 1 pieces, in each piece [T k , T k+1 ] (k = 0, 1, . . . , m), we use a scaling transformation and translation transformation in the time domain to map it into the interval [0, 1] [13]. Then, the whole piece-wise trajectory in one dimension σ ∈ {s, l} is:
where h i is the scaling transformation factor and T i is the translation transformation factor for i = 0, 1, . . . , m with setting T 0 = 0.
In this section, a convexification algorithm is introduced to construct convex corridors from the original non-convex optimization problem for real-time solving. A reference trajectory is often used to provide a warm start to the optimization process. In this work, we use simple piecewise functions for generating valid reference waypoints in the configuration space of the ego vehicle.
Suppose the whole safe region is divided into m+1 pieces with time intervals [T 0 , T 1 ] , . . . , [T m , T ] and T = T m+1 , with each interval corresponding to a convex safe region. The details of such a convexification algorithm will be introduced in the next section. The k-th convex safe region in S -L-T space can be represented as
where s i and l i are the longitudinal and lateral coordinates of the i th control point respectively, p k 0 , p k 1 are bias and skew of the lower bound and p k 0 , p k 1 are those of the upper bound. h k denotes the length of the k-th time interval and satisfies
Then, the whole safe region is the union of a set of piecewise-safe sub-regions: Fig. 2: Scenario in Fig. 1b after over-approximating car A Algo. 1 outlines the 3D trapezoidal corridor generation process. The original non-convex space is sliced along the L axis at the starting or ending L coordinates of any obstacles in the S -L -T graph. This generates 3D chunks of the non-convex space which can be projected in a 2D S -T graph without the loss of any search space. As an example, in Fig. 2a, any slices at L coordinates in the range [1, 3) will give us the 2D S -T cross-section as seen in Fig. 2c. Similarly, any slice at an L coordinate between [3, 6.7) will give us the S -T graph as seen in Fig. 2d. The inputs to Algo. 1 are the upper and lower bounds in the S and L direction w.r.t. the ego vehicle and the road. The bounds are measured over a time horizon using a discrete time interval ∆. For each slice, we construct 2D convex corridors in the corresponding S -T graph. In this work, we extend the 2D convex trapezoidal corridor generation algorithm in our previous work [17]. The new algorithm is presented as Algo.
Algo. 2 outlines the construction of 2D piecewise-convex safe regions in any given S -T cross-section along the L axis. The lower and upper bounds in the S direction serve as inputs to this algorithm. We refer readers to [17] for further details about the working of Algo. 2. A key modification in our work is that in the subroutine SingleRegionCaculate(), we also initialize the upper and lower boundaries of the regions in the L direction (Algo. 3. Lines 6,7). Our overapproximation step and the design of Algo. 1 guarantee that these boundaries are the same for all 2D convex regions generated by Algo. 2. Thus, we essentially get 2D trapezoidal-shaped corridors dragged along the L axis to form 3D trapezoidal prism-shaped convex corridors. Finally, RegionSplit() is used to check the length of each 2D convex region. If it is above a user-defined threshold (e.g., 1 s in our experimental setting), it will be split into multiple subregions, for which the time intervals are all below the threshold. This refinement operation aims to avoid underfitting. This 2D corridor generation process is repeated for all distinct obstacle boundaries in our S -L -T graph (Line 1, Algo. 1). The initialization of bounds along the L axis ensures that we get 3D trapezoidal-shaped convex corridors. Since the length of the corridors in the L direction is given by the starting or ending of the obstacles in the S -L-T space, we can guarantee the safety of all the corridors generated using Algo. 1. Note that for the space divided by obstacles, we select the unique space enclosing the reference trajectory using the SelectCorridors() method. For yielding to car A, the corridors lying in the green region of Fig. 2c and2d are chosen according to the 3D reference waypoints. Note that once the corridors are selected, the whole optimization is solved as a single problem and not decomposed into individual optimizations for separate corridors.
In this section, we discuss more about the limitations of using the cuboidal corridors. We then discuss the safety enforcement in our trapezoidal prism-shaped corridors. The formulation of quadratic optimization using the newly designed convex solution space is introduced thereafter.
As discussed in Sec. III C, the convex hull property of the Bézier curves is used to enforce that the trajectory in the S -L -T graph stays in the safe region S. We first formally define a corridor for our trajectory generation: Definition 1. Let the coefficients of the Bézier Polynomial be c i ∈ Ω, i = 0, 1, . . . , n. Each control point has two dimensions -{S, L}. These control points lying in the safe region S form a subset S cor ⊆ S, which is called a corridor.
in the S -L -T graph [6]. Constraints of the control points of cuboidal corridors are given by the following proposition: Proposition 1. If a trajectory has control points in each time interval satisfying
end , i = 0, 1, . . . , n, k = 0, 1, . . . , m}, f (t) is guaranteed to be safe, and the upper bounds and lower bounds form cuboidal corridors S cub .
Input: lbs, ubs, lb l , ub l , nums, ∆ Output: regions 1 Initialize: regions[0], i = 0, j = 1 / * i and j are counters for meta-pieces and resulting convex regions, respectively * / 2 SingleRegionCalculate(region, 0, lbs[0], ubs[0], lbs [1],
3 ubs [1], lb l , ub l ) 4 regions.append(region)
The proof of safety enforcement in rectangular corridors can be found in [17], and can be straightforwardly extended to the third dimension L for cuboidal corridors.
The optimization fails if any lower bound (p k 0 + h k p k 1 ) is greater than the upper bound (p k 0 ). In order to avoid this, the time interval of the k-th corridor must satisfy h k ≤
In [6], Ding et al. propose a seed generation and cube inflation method to adjust time intervals. However, this method generates a significant number of corridors and optimized variables, which leads to a high computation cost. In common driving scenarios (Fig. 1), we have p k 1 > 0 or p k 1 > 0, due to which the cuboidal corridors fail to cover all the safe regions. As a result, the search space is sub-optimal and the constraints on control points to enforce the trajectory are overtightened.
The sufficient conditions of control points c i to keep the longitudinal and the lateral trajectory safe and in our proposed trapezoidal-prism corridors are built upon the following lemma.
Lemma 1. Let M ∈ R (n+1)×(n+1) denote the transition matrix from the Bernstein basis b 0 n (t), b 1 n (t), . . . , b n n (t) to the monomial basis 1, t, t 2 , . . . , t n . We have M i,0 = 1, 0 ≤ M i,j ≤ 1, i = 0, 1, . . . , n, j = 0, 1, . . . , n.
The proof can be found in [17]. We leverage the following theorem meant for 2D trapezoidal corridors to construct 3D trapezoidal prism-shaped corridors.
Theorem 1. For a trajectory, if it has control points in each time interval satisfying
The upper and lower bounds in the S and L directions help form a trapezoidal prism-shaped corridor S trp .
The proof for the 2D case of the above theorem can be found in [17], and can be easily extended to another dimension L.
In Theorem 1, conditions on c s i are
Compared to the safety enforcement in cuboidal corridors in Proposition 1, we have
The advantage of having trapezoidal corridors is twofold: i) By the proof of
, the lower boundaries are guaranteed to be smaller than the upper boundaries all the time. Recall that for the rectangular corridors, we need to always check h k ≤
ii) The constraints are relaxed, therefore the solution space is enlarged compared with the rectangular corridors (see the illustration for the comparison in Fig. 3).
The objective function is established as
(1) where s r (t) and l r (t) are the reference longitudinal and lateral trajectories, and v r s and v r l are the reference velocities in the two directions. For J s and J l , their first terms penalize the deviation from the reference; the second ones penalize the deviation between the actual and reference speed; the third and the fourth terms penalize acceleration and jerk, respectively. The last terms penalize the deviation of the ending position from the reference. We used Optuna [23] for tuning all the 10 parameters.
The optimization considers the following constraints:
• Boundary Constraints: The piecewise curve starts from fixed position, speed, and acceleration, i.e., c 0,l i h
where c k,l i is the control point for the lth-order derivative of the k-th Bézier curve. Note that c k,l i has two dimensions: {S, L}.
• Continuity Constraints: The piecewise curve must be continuous at the connected time points for position, speed, and acceleration.
k+1 , l = 0, 1, 2, k = 0, 1, . . . , m-1
• Safety Constraints: With our proposed trapezoidal-prism corridors, safety constraints for the longitudinal dimension of the control point can be given as
, k = 0, 1, . . . , m and those for the lateral dimension of the control point can be given as
• Physical Constraints: The physical constraints under consideration include the limit of a vehicle's velocity, acceleration, and jerk. We can use the hodograph property of a Bézier curve to calculate velocity, acceleration, and jerk. The constraints are given by
where k = 0, 1, . . . , m and it follows that c k,l+1 i = (nl) c k,l i+1 -c k,l i . The upper bounds β k,1 are determined by speed limits on road and centripetal acceleration constraints. Let a cm be the maximum acceleration permitted and κ k the maximum curvature of the path for t ∈ [T k , T k+1 ] (see [24] for details). The lateral acceleration constraints are given by
The bounds on longitudinal and lateral accelerations and jerks are constant for different pieces of speed profiles. Then, the trajectory optimization process can be formulated as a quadratic programming (QP) problem as
We refer readers to the appendix of our previous work [25] for the detailed formulation process. This problem can be solved in real-time by a modern solver such as OSQP [26].
Our framework has been implemented using C++11. All simulations are carried out on a personal computer with a 2.60 GHz Intel i10-10750H processor.
We conduct numerical simulations to compare the proposed approach with cuboidal corridors [6]. The planning horizon is 7 s. Different road scenarios are as follows:
1) Merging into another lane due to road construction: Consider the scenario in Fig. 1. We project different stations of the vehicles onto the S -L -T graph. The initial velocity and the acceleration of the ego vehicle are v s (0) = 7.0 m/s, v l (0) = 0 m/s and a s (0) = 0 m/s 2 , a l (0) = 0 m/s 2 , respectively. Fig. 3a and Fig. 3b show Bézier curves generated by cuboidal (red, [6]) and trapezoidal-prism (green, ours) corridors for the scenario presented in Fig. 1. From Fig. 3c, we observe that the maximum acceleration required for our method is less than that needed by the cuboidal corridors approach. The superiority of using trapezoidal corridors is more clear from Fig. 3d, which records the lateral acceleration of both the methods. We observe that our approach yields a smoother acceleration plot with minimal jerk and the lower maximum acceleration. We also test the maximum initial conditions of both the methods for the same scenario to show the effect of the enlarged search space. While using trapezoidal corridors, we can generate a trajectory for a s = 2 m/s 2 , v s = 10.5 m/s, a l = 1.2 m/s 2 , v l = 2 m/s where the bounds on longitudinal acceleration are [-3, 2] m/s 2 and those on lateral acceleration are [-2, 2] m/s 2 . Using the cuboidal corridors fails to generate a trajectory for these initial conditions and is only successful when the initial velocity in the longitudinal direction is reduced to 9 m/s.
2) Overtaking a low-speed vehicle in front: We test our planner on overtaking a slowly moving car in front by lane changing twice (second time to merge back into the original lane of the ego vehicle). In layered planning techniques, these kinds of scenarios are typically tackled by considering the obstacle to be static for a few seconds. Hence, this approach proves to be conservative. The differences in the longitudinal acceleration graphs between the two corridor generation techniques can be seen in Fig. 4. Clearly, using the trapezoidal corridors generates a trajectory with much lower acceleration. Here, the vehicle in front is assumed to be moving with v s = 5 m/s and the ego vehicle's initial condition is v s = 7 m/s. 3) Unprotected left turn: As shown in Fig. 5a, there are two cars coming from the front which obstruct the ego vehicle from making a left turn without yielding to them. As seen in Fig. 5b, our planner can successfully find a trajectory while meeting all the safety and dynamic feasibility constraints. Since the ego vehicle needs to yield to the cars in front, we also test the maximum initial velocity (v s = 1 m/s) and acceleration (a s = 0.5 m/s 2 ) in the longitudinal direction for this case. If the distance between Car A and Car B is sufficient for the ego vehicle to go in between them, our planner finds the corresponding trajectory (Fig. 5c). In this scenario, the additional search space obtained by trapezoidal corridors is not used at all, as the trajectory passing through the enlarged search space can only result in a lane change, which is not desired. Hence, both the trajectories obtained are the same and overlap each other, as seen in Fig. 5.
The simulations in this part are conducted on the Com-monRoad platform [27], which provides an interactive simulated and non-interactive real traffic environment for validating motion planning algorithms. A given scenario is considered "solved" when the ego vehicle reaches the desired goal region while satisfying all the constraints. We visualize the bird's-eye view simulation of the lane change scenario in Fig. 1. The results obtained using our approach can be seen in Fig. 6. The cuboidal corridor approach did not yield a collision-free trajectory as it failed to replan owing to the lack of search space. It also had significantly high acceleration as can be observed in Fig. 3c.
In this paper, we propose a novel convexification algorithm for generating safety corridors in the S -L -T space. We show that our method of trapezoidal prism-shaped corridors enlarges the solution space as compared to the existing cuboidal corridors-based method. We provide the sufficient conditions of control points in the trapezoidal corridors to provably guarantee the safety of trajectories represented by Bézier polynomials. Finally, we formulate the trajectory optimization as a QP problem. The numerical and CommonRoad simulations show that the proposed approach is superior in terms of optimality and low failure rates. Future work includes using a dynamic programming-based approach to generate a comfort-optimal reference trajectory in the S -L -T space.