TL;DR
This paper introduces a novel method for generating safe driving trajectories for autonomous vehicles in unknown environments. It achieves this by computing a "Forward Reachable Set" (FRS) that accounts for the difference between a simplified vehicle model used for planning and the vehicle's actual, more complex dynamics. This FRS is then used at runtime to efficiently prune unsafe trajectories, ensuring collision avoidance.
What Problem Does This Paper Address?
Ensuring the safety of autonomous vehicles, especially in unpredictable environments with static obstacles, is a critical challenge. While high-fidelity models can accurately describe a vehicle's behavior, using them for real-time trajectory planning is computationally prohibitive. Conversely, using simplified models for planning can lead to a gap between the planned trajectory and what the vehicle can actually execute, potentially resulting in collisions. This paper tackles this problem by bridging this gap: it develops a method to design safe trajectories using a low-fidelity model while guaranteeing that a high-fidelity model can safely follow them, even in the presence of model mismatch and unforeseen obstacles.
Methods
The core of the proposed method involves three main steps:
- Forward Reachable Set (FRS) Computation (Offline): The authors first compute a conservative FRS. This set represents all possible states and trajectories the high-fidelity vehicle model can reach when attempting to follow trajectories generated by a lower-fidelity model, over a finite time horizon. This computation accounts for model mismatch using a bounded error function
g. The FRS is computed using a convex optimization formulation, specifically a semidefinite program (SDP) based on polynomial representations. - Set Intersection (Runtime): At runtime, the precomputed FRS is intersected with the detected obstacles in the environment. This step efficiently eliminates trajectory parameters that would lead to a collision. This is formulated as another optimization problem to find an inner approximation of the "safe" set of trajectory parameters (
Ksafe). - Trajectory Optimization (Runtime): Finally, an optimal trajectory is selected from the remaining safe set (
Ksafe) by optimizing a user-specified cost function (e.g., minimizing acceleration, reaching a goal). This optimization is performed subject to the constraint that the chosen trajectory parameters belong toKsafe.
A key theoretical contribution is a theorem that establishes the relationship between sensing, planning, and braking time horizons to guarantee safety.
Datasets
Not discussed in the paper. The authors use a simulated environment with randomly generated obstacles and a goal for evaluation.
Key Insights and Ideas
- Bridging the Model Gap: The central idea of using a low-fidelity model for planning while guaranteeing safety for a high-fidelity model is a powerful approach. The FRS acts as a crucial intermediary, encapsulating the uncertainty introduced by this model mismatch.
- Runtime Safety Verification: Intersecting the FRS with obstacles at runtime provides an efficient way to prune unsafe trajectories. This is more practical than trying to plan with a high-fidelity model directly.
- Theoretical Safety Guarantees: The paper provides a theoretical framework that links sensing, planning, and braking times to ensure that a safe trajectory always exists, even in challenging scenarios. This is a significant step towards provably safe autonomous driving.
- Leveraging Convex Optimization: The use of semidefinite programming for FRS computation and set intersection allows for robust and efficient solutions, even with complex dynamics and constraints.
Key Results
- The method was demonstrated in simulation using a kinematic Dubins car as the low-fidelity model and a dynamic unicycle as the high-fidelity model.
- In 1000 simulated trials with randomized obstacles and goals, no crashes were detected.
- Approximately 82% of trials successfully reached the goal.
- 15% of trials involved an emergency braking maneuver, demonstrating the system's ability to handle critical situations.
- The FRS computation was computationally intensive (79 hours, 150 GB memory), but this is an offline step.
- Runtime set intersection and trajectory optimization were found to be significantly faster, with set intersection being the bottleneck for planning time (
Tplan), scaling with the number of obstacles.
Limitations and Future Work
- Computational Cost of FRS: The offline computation of the FRS is currently very time-consuming and memory-intensive, limiting its applicability to scenarios where precomputation is feasible.
- Conservativeness of FRS: The current approach uses an outer approximation of the FRS, which can lead to overly conservative behavior, as seen in one of the simulation examples where a braking maneuver was initiated even though a path through an obstacle's "hole" was possible.
- Model Uncertainty: The paper assumes a bounded error function
gthat is polynomial. Extending this to more general forms of uncertainty and incorporating confidence level sets is a future direction. - Dynamic Obstacles: The current method is designed for static obstacles. Extending it to handle dynamic environments is a significant area for future research.
- Real-time Performance: While the runtime steps are faster, achieving consistent real-time performance (e.g.,
Tplan = 0.5s) remains a challenge, especially with a large number of obstacles. The authors suggest pausing the simulation to guarantee replanning time. - Hybrid Systems: Exploring FRS computation for hybrid systems and using convex optimization for global nonlinear trajectory optimization are also proposed future research directions.
Summary updated