Computing the Drivable Area of Autonomous Road Vehicles in Dynamic Road Scenes

This paper presents an algorithm for overapproximating the drivable area of road vehicles in the presence of time-varying obstacles. The drivable area can be used to detect whether a feasible trajectory exists and in which area one can limit the search of drivable trajectories. For this purpose, we abstract the considered road vehicle by a point mass with bounded velocity and acceleration. Our algorithm calculates the reachable occupancy at discrete time steps. At each time step, the set is represented by a union of finitely many sets, which are each the Cartesian product of two 2-D convex polytopes. We demonstrate our method with three examples: i) a traffic situation with identical dynamic constraints in the x- and y-directions; ii) a highway scenario with different lateral and longitudinal constraints of the dynamics; and iii) a highway scenario with different traffic predictions. The examples demonstrate that we can compute the drivable area quickly enough to deploy our approach in real vehicles.