Formal Verification of an Autonomous Vehicle System
Tichakorn Wongpiromsarn, Richard M Murray
Conference on Decision and Control, 2008 (submitted)
Model checking is a widely used technique for formal verification of distributed systems. It works by effectively examining the complete reachable state space of a model in order to determine whether the system satisfies its requirements or desired properties. The complexity of an autonomous vehicle system, however, renders model checking of the entire system infeasible due to the state explosion problem. In this paper, we illustrate how to exploit the structure of the system to systematically decompose the overall system-level requirements into a set of component-level requirements. Each of the components can then be model checked separately. A case study is presented where we formally verify the state consistency between different software modules of Alice, an autonomous vehicle developed by the California Institute of Technology for the 2007 DARPA Urban Challenge.
- Preprint: http://www.cds.caltech.edu/~murray/preprints/wm08-cdc_s.pdf