Ensuring Drivability of Planned Motions from Simple Models Using Formal Methods

Abstract

Motion planning of automated vehicles requires dynamical models to ensure that obtained trajectories are drivable. An often overlooked aspect is that usually simplified models are used for motion planning, which do not always sufficiently conform to the real behavior of vehicles. Thus, collision avoidance and drivability is not necessarily ensured. We address this problem by modeling vehicles as differential inclusions composed from simple dynamics plus set-based uncertainty; conformance testing is used to determine the required uncertainty. To quickly provide the set of solutions of these uncertain models, we provide pre-computed reachable sets (i.e. union of all possible solutions) for pre-selected motion primitives. The reachable sets of vehicles are obtained by a novel combination of optimization techniques and reachability analysis – they enable us to guarantee safety by checking their mutual non-intersection for consecutive time intervals. The benefits of our approach are demonstrated by numerical experiments.