I Introduction
Motion planning is one of the main components of an autonomous driving system with an essential role in generating feasible, safe trajectories. Semantic safe corridors and Bezier curves are commonly employed in optimizationbased motion planning to guarantee safety, thanks to the convex hull property of Bezier curves. The idea is to generate a spatial safety corridor based on the surrounding occupancies, and use the corridor as a constraint in trajectory planning. The trajectories are then generated in (Frenet) frame [3] or (Cartesian) frame [11], aiming to optimize the overall swiftness, smoothness, and smartness [4], under the constraints of continuity, vehicle dynamics limitation, traffic rules, and above all, safety [8].
One reason for using optimizationbased approaches is that convex corridors guarantee the convexity of the problem, allowing for solving the motion planning problem as a quadratic programming problem [13], which are wellstudied and can be implemented using offtheshelf solvers [10]. Among different parametric curves, piecewise Bezier curves are more popular as the convex hull property of Bezier curves^{1}^{1}1The Bezier curve defined by control points lies in the convex hull of the given control points, which is also called the control polygon. [1] guarantees the curve segments to be confined within the corresponding safety corridor [5]. As a result, the safety of the generated trajectories are guaranteed.
The spatial corridors can be extended to spatiotemporal corridors to account for dynamic objects and predicted occupations in upcoming environments. When corridors consist of spatial dimension with no timedependency (e.g. defined in plane or in plane), the convex hull property holds, which allows for using general convex corridors for maximum search space coverage as utilized in [7]. However, when there is a timedependency, i.e. corridors are defined in spatiotemporal frames (e.g. or planes), the convex hull property does not generally hold, as shown in Fig. 2, imposing a limitation on the shape of corridors. This is stemmed from the fact that the spatial axis and the temporal axis are not equivalent.
The convex hull property problem is often addressed by restricting the shape of corridors to be rectangular [2], where the convex hull property is ensured, resulting in a large uncovered search space and conservative or unsmoothed trajectories. The uncovered search space may lead to optimization failure in crowded scenarios, where no trajectories can be found within the corridors. As an extension, multiple rectangular corridors can be chained together to reduce the uncovered search space as illustrated in Fig. 1
, at the expense of significantly increasing the dimension of the optimization vector. This approach tends to be computationally intensive as it requires a sequential optimization steps to optimize a trajectory segment for each corridor and ensuring continuity from one segment to the next. Another method is to use a sampling based approach that supports general convex corridor shapes
[9]. However the samplingbased approaches generally results in suboptimal solutions, and there is no guarantee to find an optimal trajectory. A recent approach is to employ trapezoidal corridors [6] with a sufficient condition for convex hull property to hold. The trapezoidal shape is effective in reducing the number of corridors, specifically in dynamic scenarios when there are objects with constant speed. While this is an improvement compared to the previous methods, the uncovered space can still be significant in certain scenarios. Fig. 3 A1 shows a case when there is a decelerating front vehicle, and Fig. 3 A2 shows a cutin vehicle that with accelerating and decelerating speed profile. By comparing Fig. 3 B1/C1 and Fig. 3 B2/C2, one can see that in both cases, trapezoidal corridors have larger uncovered search space than that of general convex corridors, which may lead to unnecessary harsh brakes in motion planning.The convex hull property in the timedependent cases depends on the shape of the corridor, which precludes using arbitrary shaped corridors. Naturally, more complicated shapes cover more search space and yield better optimization results. An ideal case is to use general convexshaped corridors. As the main contribution of this paper, we prove a sufficient condition to guarantee the convex hull property for general convex corridors in spatiotemporal frames. The use of general convex corridors can shrink the uncovered search space to , compared to of trapezoidal corridors.
This paper is organized as follows: Section II converts the main theorem into an equivalent theorem. Section III decomposes the theorem into several lemmas and proves them by recurrence. Section IV shows that the uncovered search space is under continuity assumptions. Section V compares the proposed approach with the state of the art approach quantitatively under simulated scenarios. Section VI provides deeper analysis to the proposed approach. Section VII presents our conclusions.
Ii Problem Formulation
Considering a convex spatiotemporal corridor defined in . The upper bound function is concave, while the lower bound function is convex. We pick control points in the corridor to form a scaled Bezier curve [2] of degree which is defined in . The vertical axis label is a generic spacial label, which could represent , , , , or any spacial variable, as shown in Fig. 4 A. The vertical coordinate of the ith control point is noted as . We want to find a sufficient condition to make sure the Bezier curve lies in the corridor.
Theorem II.1
If the series (i=0, 1, …, n) satisfies
(1) 
the scaled Bezier curve generated from control points lies in the corridor.
Theorem II.1 shows that it suffices to pick the control points with equal time spacing, and the range of each control point is the value of the upper bound/lower bound functions at the corresponding time.
To simplify the proof of theorem II.1, without loss of generality, we can scale the time interval back to , consider the upper bound function only, and pick the control points along the upper bound function with equal time spacing (which will generate the highest possible Bezier curve). The vertical coordinate of the ith control point thus satisfies . The polyline of the control polygon formed with these control points is defined as CPETS (control polygon of equal time spacing), as shown in the red polyline in Fig. 4 B. Due to the property of concave functions, we have . This yields theorem II.2, which is equivalent to theorem II.1.
Theorem II.2
, the Bezier curve satisfies CPETS, where is a concave function, , and is the Bernstein polynomial which is defined as .
Iii Proof of the Main Theorem
Iiia Lemmas
Lemma III.1
For two functions and , if and (resp. ), (resp. ), we have (resp. ).
Using Lagrange’s mean value theorem, , such that
(2) 
Lemma III.2
Suppose is an ascending series, then the Bezier curve is an ascending function.
Taking the derivative of ,
(3) 
Lemma III.3
Suppose is a concave (convex) series, i.e. (resp. ) , then the Bezier curve is a concave (convex) function.
Taking the second derivative of ,
(4) 
Corollary III.3.1
Suppose is a concave (convex) series, the Bezier curve passes the first and the last control point, and is inferior than the first and the last segment of the CPETS.
Lemma III.4
, if the upper bound function defined in is ascending (resp. descending) and concave, for series , and , we have , i.e. the Bezier curve is bounded by the CPETS.
We only need to prove lemma III.4 for the case that is ascending. For the descending case, it suffices to replace with and it returns to the ascending case, thanks to a property of Bezier curve that its orientation can be reversed and its control points keep unchanged by replacing with .
The series is ascending and concave due to the properties of . Applying lemma III.2 and lemma III.3, is ascending and concave. We will prove lemma III.4 by recurrence. For , it is easy to verify that lemma III.4 holds using lemma III.1.
Suppose the lemma holds for , when , using the recurrence definition of Bezier curve:
(5) 
We only need to show that lemma III.4 holds for intervals , , … , , because for the first and the last interval, lemma III.4 holds due to corollary III.3.1.
The recurrence definition (5) means that is a combination of two lower degree Bezier curves. One is formed with , the other is formed with . With the assumption of recurrence, and , we have
(6) 
where
(7) 
Now we will use the monotony of . , note , we have . As we know is ascending, from (8) we have
(9) 
This concludes the proof for . Lemma III.4 is thus proven.
Corollary III.4.1
, if the upper bound function defined in is ascending (resp. descending) and concave, for series , we have .
Using lemma III.4, the proof is trivial due to the fact that CPETS is bounded by .
Lemma III.5
, if the concave upper bound function defined in is ascending in and is descending in , for series , we have .
(11) 
It is easy to verify that is ascending, , is descending, , and the pointwise minimum function of and is , as shown in (12).
(12) 
To better illustrate the idea of this proof, Fig. 5 shows the graphs of functions , and . The curve represents , represents , and represents . Our objective is to bound with and so that we can take the common part of the bounds, which is .
Applying corollary III.4.1, we have
(13) 
As and , we have
(14) 
(15) 
This concludes the proof.
Corollary III.5.1
, if the concave upper bound function defined in is ascending in and is descending in , for series , and , we have , i.e. the Bezier curve is bounded by the CPETS.
One can notice that the CPETS itself can be treated as a concave upper bound function, and the CPETS of a CPETS is still itself. The proof is trivial by applying lemma III.5.
IiiB Proof of Theorem ii.2
Iv Search Space Coverage
We have proven the safety of the proposed method of choosing control points. Now we need to analyze the advantage of the proposed method, i.e. more search space coverage. From theorem II.1 we known that ( is the concave upper bound function) is the highest possible Bezier curve. It suffices to analyze the difference between the highest possible Bezier curve and . We are going to prove that the difference is if is twice differentiable.
Lemma IV.1
For two twice differentiable functions and defined in , if such that and , we have = .
The proof is trivial by applying Taylor’s formula on .
Lemma IV.2
If is a twice differentiable function defined in , and is the linear function passing and , then
Note , we have obviously and is twice differentiable. , from Taylor’s formula we have
(16) 
(17) 
Calculating the difference of (16) and (17) yields
(18) 
From (18) we know that = , so = . From (16) we know that = + = . This concludes the proof.
Corollary IV.2.1
Suppose is a concave (convex) series, the Bezier curve is inferior than the first and the last segment of the CPETS, and the difference is .
Corollary IV.2.2
If the concave upper bound function is twice differentiable, the difference between and the CPETS is , where is the number of control points.
The proof is obvious by applying lemma IV.2 on interval ().
With corollary IV.2.2, it suffices to prove that the difference between the highest possible Bezier curve and the CPETS is .
Lemma IV.3
, if the upper bound function defined in is concave and twice differentiable, for series , and , note , we have =, i.e. the difference between the Bezier curve and CPETS is .
We will prove it by recurrence, similar to the proof of lemma III.4. For , it is easy to verify that lemma IV.3 holds using lemma IV.1.
Suppose lemma IV.3 holds for . When , we only need to show that lemma IV.3 holds for intervals , , … , , because for the first and the last interval, lemma IV.3 holds due to corollary IV.2.1.
With the assumption of recurrence, and , using the recurrence definition of Bezier curve (5), we have:
(19) 
where is defined in (7). One can use lemma IV.1 to verify that
(20) 
, note , one can verify that , and . Thus = = . From (19), (7) and (20), we have
(21) 
This concludes the proof for . Lemma IV.3 is thus proven.
V Simulation results
In this section, the motion planning results based on the general convex corridors are compared with trapezoidal corridorsbased planning. The same set of parameters (weights, time horizon) were used for both cases to make the results comparable. The scenario includes an ego vehicle and a decelerating front vehicle, similar to the scenario depicted in Fig. 3 A1. The corresponding corridors are shown in Fig. 6 A. A desirable planning should consider the smoothness and the closeness between the planned trajectory and the reference trajectory. It is also reasonable to consider a higher weight for the trajectory points in the near future compared to the latertime points. Therefore, the cost function is defined as (LABEL:eq:costFunction):
(22) 
where , , , , , , , . The terms and mean that the planning has an extra emphasis on the near future points. The initial speed of the planning is 5.5 . is a reference trajectory, which is generated by a uniformly accelerated motion with an acceleration of 0.05 . Note that we do not require the reference trajectory to be safe here. A reference trajectory with high acceleration could be unsafe, but it may result in a planned trajectory with a higher acceleration.
The motion planning problem is then converted into a QP (quadratic programming) problem, whose details are presented in [2] [6]. OSQP 0.5.1 is adopted as the solver to this problem. As shown in Fig. 6, the general convex corridor results in a larger search space, leading to much smaller deceleration compared to that of the trapezoidal corridor (0.52 1.0 ) and subsequently less harsh brakes and improved smoothness.
To evaluate the performance of this algorithm in a realtime, multiframe condition, a cutin scenario is set up in our simulator (developed based on ROS). The simulation scenario is based on an realworld scenario encountered in road test. The ego vehicle is cruising under a speed limit of 60 (16.77 ^{2}^{2}2Due to the performance of the speed controller, the ego vehicle’s actual speed is around 16 .), while another vehicle cuts in at s, at a distance of 22 and at a speed of 7 . The cutin vehicle decelerates at 0.5 for 3 seconds, then continues moving at a constant speed. There is an additional 5meter safety margin behind the cutin vehicle. The closeloop longitudinal dynamics of the ego vehicle is simulated by a firstorder dynamics with a time constant of 0.3 . The corridors are generated with the algorithm presented in [12] and [6], respectively for general convex shape and trapezoidal shape corridors.
The comparison is shown in Fig. 7. The lowest deceleration is 4.46 using general convex corridors, compared to 5.23 of using trapezoidal corridors. In the case of using general convex corridors, the lowest speed is registered at 3.41 , compared to that of trapezoidal corridors at 2.42 . Our proposed approach decelerates earlier, which helps in reducing the peak value of deceleration and the length of the deceleration period as an indication of an improved overall comfort.
Vi Discussion
This paper contains mainly two parts, a) deriving a sufficient condition for the convex hull property in spatiotemporal corridors, and b) estimating unsearched space. One can note that there is no continuity requirement for the concave upper bound function in a), but requires it to be twice differentiable in b). The requirement in b) can be relaxed to
using Rolle’s remainder of Taylor’s theorem but the error is also weakened to . Given the fact that the difference between the CPETS and the upper bound function is already , we can not achieve better result than .In this research, the unsearched space is quantified as an order of magnitude instead of an analytical expression. An expression can be obtained by calculating the error each time applying an inequality in the proof of lemma IV.3.
This paper is based on Bezier curves, however, since Bspline curves are piecewise Bezier curve, the theorems in this paper could potentially be extended to Bspline curves with some modifications.
Vii Conclusions
In this paper, we proved a sufficient condition to guarantee the convex hull property for general convex corridors in spatiotemporal frames. This theorem allows for using more complicated shapes to represent constraints as a form of spatiotemporal corridors. It was also shown that the uncovered search space can be shrunk to compared to of trapezoidal corridors, which is the best possible result under continuity assumptions. The use of general convex corridors yields less harsh brakes and enhanced the overall smoothness, specifically in scenarios involving objects with frequent acceleration/deceleration speed profile, which require more complex corridor shapes.
References
 [1] (1990) Bezier surface/surface intersection. IEEE computer graphics and applications 10 (1), pp. 50–58. Cited by: §I.
 [2] (2019) Safe trajectory generation for complex urban environments using spatiotemporal semantic corridor. IEEE Robotics and Automation Letters 4 (3), pp. 2997–3004. Cited by: §I, §II, §V.
 [3] (2018) Baidu apollo em motion planner. arXiv preprint arXiv:1807.08048. Cited by: §I.
 [4] (1995) Primitives for smoothing mobile robot trajectories. IEEE transactions on robotics and automation 11 (3), pp. 441–448. Cited by: §I.
 [5] (2018) Online safe trajectory generation for quadrotors using fast marching method and bernstein basis polynomial. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 344–351. Cited by: §I.
 [6] (2021) Speed planning using bezier polynomials with trapezoidal corridors. arXiv preprint arXiv:2104.11655. Cited by: §I, §V, §V.
 [7] (2018) The convex feasible set algorithm for real time optimization in motion planning. SIAM Journal on Control and optimization 56 (4), pp. 2712–2733. Cited by: §I.
 [8] (2020) Adaptive potential fieldbased path planning for complex autonomous driving scenarios. IEEE Access 8, pp. 225294–225305. Cited by: §I.
 [9] (2020) An autonomous driving framework for longterm decisionmaking and shortterm trajectory planning on frenet space. arXiv preprint arXiv:2011.13099. Cited by: §I.
 [10] (2016) Optimal trajectory planning for autonomous driving integrating logical constraints: an miqp perspective. In 2016 IEEE 19th international conference on intelligent transportation systems (ITSC), pp. 205–210. Cited by: §I.

[11]
(2018)
A fast integrated planning and control framework for autonomous driving via imitation learning
. In Dynamic Systems and Control Conference, Vol. 51913, pp. V003T37A012. Cited by: §I.  [12] (2021) Enable faster and smoother spatiotemporal trajectory planning for autonomous vehicles in constrained dynamic environment. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering 235 (4), pp. 1101–1112. Cited by: §V.
 [13] (2014) Motion planning under uncertainty for onroad autonomous driving. In 2014 IEEE International Conference on Robotics and Automation (ICRA), pp. 2507–2512. Cited by: §I.
Comments
There are no comments yet.