Jerk Constrained Velocity Planning for an Autonomous Vehicle: Linear Programming Approach

Yutaka Shimizu, Takamasa Horibe, Fumiya Watanabe, Shinpei Kato

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.

Velocity profiles illustrating the pre-filtering steps for obstacle avoidance and jerk constraints.

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.

Comparative analysis of velocity, acceleration, and jerk profiles for LP, Non-Convex, and Pseudo-QP methods.

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

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.
BibTeX
@inproceedings{shimizu2022jerk,
  author = {Yutaka Shimizu and Takamasa Horibe and Fumiya Watanabe and Shinpei Kato},
  title = {{Jerk Constrained Velocity Planning for an Autonomous Vehicle: Linear Programming Approach}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2022},
  doi = {10.1109/icra46639.2022.9812155},
}

Loading related content...

Figure