Switching Logic Synthesis for Reachability


Taly, A., & Tiwari, A. (2010, October). Switching logic synthesis for reachability. In Proceedings of the tenth ACM international conference on Embedded software (pp. 19-28).


We consider the problem of driving a system from some initial configuration to a desired configuration while avoiding some unsafe configurations. The system to be controlled is a dynamical system that can operate in different modes. The goal is to synthesize the logic for switching between the modes so that the desired reachability property holds.

In this paper, we first present a sound and complete inference rule for proving reachability properties of single mode continuous dynamical systems. Next, we present an inference rule for proving controlled reachability in multi-modal continuous dynamical systems. From a constructive proof of controlled reachability, we show how to synthesize the desired switching logic. We show that our synthesis procedure is sound and produces only non-zeno hybrid systems.

In practice, we perform a constructive proof of controlled reachability by solving an Exists-Forall formula in the theory of reals. We present an approach for solving such formulas that combines symbolic and numeric solvers. We demonstrate our approach on some examples. All results extend naturally to the case when, instead of reachability, interest is in until properties.

Read more from SRI