As mentioned above, trajectory planning in the form of piecewise polynomials is a well-studied problem when the temporal assignment is fixed. However, as temporal assignment determines the coefficients in the cost function, it affects the resultant optimal trajectory to a great extent. People have long found it difficult to efficiently obtain an optimal time allocation, especially when planning the trajectory in a complex environment. The authors of [1]} formulate the problem in the QP form with a time penalty and conduct gradient descent to iteratively find a better time allocation. However, the computation time of the method becomes the major obstacle to widely using it in real-time trajectory planning. Heuristics methods [2]} have also been used to achieve better time allocation. Notwithstanding, such methods do not guarantee optimal time allocation and can lead to suboptimal trajectories. Another strategy to find optimal time allocation is to decouple trajectory planning into two problems: a spatial one and a temporal one, and then make use of convex second-order conic program (SOCP) reformulation to find optimal time allocation [3]}. However, this method may be infeasible when the initial and final states are not static.
