Abstract
Velocity Planning for self-driving vehicles in a complex environment is one of the most challenging tasks. It must satisfy the following three requirements: safety with regards to collisions; respect of the maximum velocity limits defined by the traffic rules; comfort of the passengers. In order to achieve these goals, the jerk and dynamic objects should be considered, however, it makes the problem as complex as a non-convex optimization problem. In this paper, we propose a linear programming (LP) based velocity planning method with jerk limit and obstacle avoidance constraints for an autonomous driving system. To confirm the efficiency of the proposed method, a comparison is made with several optimization-based approaches, and we show that our method can generate a velocity profile which satisfies the aforementioned requirements more efficiently than the compared methods. In addition, we tested our algorithm on a real vehicle at a test field to validate the effectiveness of the proposed method.
Introduction
Planning an optimal velocity profile for autonomous vehicles involves a delicate balance between safety, legality, and passenger comfort. While safety and speed limits are straightforward constraints, passenger comfort is largely dictated by "jerk"—the rate of change of acceleration. In spatial-domain planning (arc-length $s$), jerk constraints are non-linear and non-convex. This complexity typically forces a choice between computationally expensive non-convex solvers, which are unsuitable for real-time use, and simplifying heuristics that may compromise safety or comfort.
Methods: Linearizing the Velocity Planning Problem
The proposed method overcomes these challenges by transforming the non-convex optimization into a Linear Programming (LP) task through a two-step linearization process.
1. Velocity Limit Filtering for Obstacle Avoidance
Instead of treating dynamic obstacles as complex spatio-temporal constraints, the algorithm employs a Velocity Limit Filter. By predicting the trajectories of dynamic objects, the system analytically calculates the maximum safe speed for specific road segments. These are then treated as hard velocity limits within the optimization.
2. Jerk Linearization via Reference Filtering
To handle non-linear jerk equations, a "rough draft" velocity profile is first generated using a Forward-Backward Jerk Filter. This heuristic provides a baseline velocity ($v_f$). By substituting $v_f$ into the complex jerk equations, the non-linear terms are linearized.
The final LP formulation maximizes velocity while strictly adhering to acceleration, jerk, and the pre-calculated obstacle avoidance limits.
Results and Discussion
The performance of the LP-based planner was evaluated through numerical simulations and real-world vehicle testing using the Autoware platform.
Computational Efficiency
The LP method demonstrated exceptional speed, solving the planning problem in just 5.10 ms. This is nearly 700 times faster than the Non-Convex approach (3463 ms), making it highly suitable for real-time autonomous driving.
Constraint Satisfaction
Unlike "pseudo-jerk" Quadratic Programming (QP) methods, which often fail to accurately model jerk at varying speeds, the proposed LP method successfully respected all physical limits. As shown in the comparison below, the LP method maintains a smooth velocity profile while keeping acceleration and jerk within defined bounds.
Real-World Validation
On-road experiments confirmed the vehicle's ability to handle complex scenarios, including car-following and sudden "cut-in" maneuvers, while maintaining a smooth and natural driving behavior that prioritizes passenger comfort.
Conclusion
By linearizing jerk constraints through reference filtering and converting dynamic obstacles into spatial velocity limits, this research provides a computationally efficient path to smooth autonomous driving. While the current model assumes known obstacle trajectories and decoupled path planning, it represents a significant step toward real-time, comfort-oriented velocity optimization. Future work will explore more integrated spacetime planning to handle highly chaotic urban environments.
Summary updated