Solving the Minimum-Time Velocity Planning Problem through an Hypergraph-Based Approach

In a previous work an algorithm with linear-time computational complexity with respects to the number of variables is presented, providing an optimal solution for the minimum-time velocity planning problem. One limitation of such work is that the obtained velocity profile is not sufficiently smooth. In this work we try to obtain a smoother velocity profile, adding additional constraints on the absolute value of the second derivative of velocity with respect to the arc-length. We propose an algorithm that is able to efficiently solve the minimum-time velocity planning problem when only the lower bound of the second derivative of the velocity is considered. We will also see that the minimum time velocity planning problem under consideration belongs to a more general class of optimization problems, which can be tackled by the same approach. The approach is illustrated through an example and tested over a set of randomly generated instances. Properties of the proposed algorithm are proved.