Online Risk-Bounded Graph-Based Local Planning for Autonomous Driving With Theoretical Guarantees
Abdulrahman Ahmad, Majid Khonji, Khaled Elbassioni, Jorge Dias, Ameena Al Sumaiti
Abstract
Risk-bounded motion planning in dynamic environments for autonomous driving presents complex challenges, particularly in solving the nonconvex problem of ensuring continuous, safe, and real-time navigation towards a destination. This paper introduces an online graph-based local planning approach constrained by a user-defined driving style in terms of a risk budget <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta$</tex> for the entire mission. Our online approach assigns a risk bound to each motion planning decision, ensuring that the total risk consumed remains within <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta$</tex>. First, we construct a spatial lattice graph that adheres to the vehicle's curvature constraints. Then, the trajectory planning problem is reformulated as an online optimization problem, where decisions must be made sequentially without prior knowledge of future events. Therefore, we propose a reduction to the problem to be online multiple-choice knapsack problem (ON-MCKP), where the knapsack items are candidate paths generated by solving constrained shortest-path problems. To solve the ON-MCKP, we deploy online algorithms that offer theoretical guarantees on the risk allocation throughout the entire mission. The effectiveness of our method is demonstrated empirically, showing significant improvements in the objective without violating safety constraints.
BibTeX
@inproceedings{icra2025_onlineriskbounde,
title = {Online Risk-Bounded Graph-Based Local Planning for Autonomous Driving With Theoretical Guarantees},
author = {Abdulrahman Ahmad and Majid Khonji and Khaled Elbassioni and Jorge Dias and Ameena Al Sumaiti},
booktitle = {ICRA 2025},
year = {2025}
}