A Multi-Step Approach to Accelerate the Computation of Reachable Sets for Road Vehicles

We propose an approach for the fast computation of reachable sets of road vehicles while considering dynamic obstacles. The obtained reachable sets contain all possible behaviors of vehicles and can be used for motion planning, verification, and criticality assessment. The proposed approach precomputes computationally expensive parts of the reachability analysis. Further, we partition the reachable set into cells and construct a directed graph storing which cells are reachable from which cells at preceding time steps. Using this approach, considering obstacles reduces to deleting nodes from the directed graph. Although this simple idea ensures an efficient computation, the discretization can introduce considerable over-approximations. Thus, the main novelty of this paper is to reduce the over-approximations by intersecting reachable sets propagated from multiple points in time. We demonstrate our approach on a large range of scenarios for automated vehicles showing a faster computation time compared to previous approaches while providing the same level of accuracy.