Formally Verified Safety Net for Waypoint Navigation Neural Network Controllers

Alexei Kopylov, Stefan Mitsch, Aleksey Nogin, Michael A. Warren

Abstract

This paper describes a formal model of a “location, heading and speed” waypoint navigation task for an autonomous ground vehicle—that is, a task of navigating the vehicle towards a particular location so that it has the desired heading and speed when in that location. Our novel way of modeling this task makes formal reasoning over controller correctness tractable. We state our model in differential dynamic logic (dL), which we then use to establish a formal definition of waypoint feasibility and formally verify its validity in the KeYmaera X interactive theorem prover. The formal machine-checked proof witnesses that for any waypoint we consider feasible, the vehicle can indeed be controlled to reach it within the prescribed error bound. We also describe how we use these formal definitions and theorem statements to inform training of neural network controllers for performing this waypoint navigation task. Note that in our approach we do not need to rely on the neural network controller always being perfect—instead, the formal model allows a synthesis of a correct-by-construction safety net for the controller that checks whether the neural network output is safe to act upon and present a safe alternative if it is not.
BibTeX
@inproceedings{kopylov2021formally,
  author = {Alexei Kopylov and Stefan Mitsch and Aleksey Nogin and Michael A. Warren},
  title = {{Formally Verified Safety Net for Waypoint Navigation Neural Network Controllers}},
  booktitle = {FM},
  year = {2021},
  doi = {10.1007/978-3-030-90870-6\_7},
}

Loading related content...

Figure