Safe Trajectory Synthesis for Autonomous Driving in Unforeseen Environments

Shreyas Kousik, Sean Vaskov, Matthew Johnson-Roberson, Ramanarayan VasudevanarXiv 2017 · OpenReview

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:

  1. 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.
  2. 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).
  3. 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 to Ksafe.

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 g that 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

Abstract

Path planning for autonomous vehicles in arbitrary environments requires a guarantee of safety, but this can be impractical to ensure in real-time when the vehicle is described with a high-fidelity model. To address this problem, this paper develops a method to perform trajectory design by considering a low-fidelity model that accounts for model mismatch. The presented method begins by computing a conservative Forward Reachable Set (FRS) of a high-fidelity model's trajectories produced when tracking trajectories of a low-fidelity model over a finite time horizon. At runtime, the vehicle intersects this FRS with obstacles in the environment to eliminate trajectories that can lead to a collision, then selects an optimal plan from the remaining safe set. By bounding the time for this set intersection and subsequent path selection, this paper proves a lower bound for the FRS time horizon and sensing horizon to guarantee safety. This method is demonstrated in simulation using a kinematic Dubin's car as the low-fidelity model and a dynamic unicycle as the high-fidelity model.
BibTeX
@misc{kousik2017safe,
  author = {Shreyas Kousik and Sean Vaskov and Matthew Johnson-Roberson and Ramanarayan Vasudevan},
  title = {{Safe Trajectory Synthesis for Autonomous Driving in Unforeseen Environments}},
  year = {2017},
  eprint = {1705.00091},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.00091},
}
Figure