We present a scalable set-valued safety-preserving controller for constrained continuous-time linear time-invariant (LTI) systems subject to additive, unknown but bounded disturbance or uncertainty. The approach relies upon a conservative approximation of the discriminating kernel using robust maximal reachable sets---an extension of our earlier work on computation of the viability kernel for high-dimensional systems. Based on ellipsoidal techniques for reachability, a piecewise ellipsoidal algorithm with polynomial complexity is described that under-approximates the discriminating kernel under LTI dynamics. This precomputed piecewise ellipsoidal set is then used online to synthesize a permissive state-feedback safety-preserving controller. The controller is modeled as a hybrid automaton and can be formulated such that under certain conditions the resulting control signal is continuous across its transitions. We show the performance of the controller on a twelve-dimensional flight envelope protection problem for a quadrotor with actuation saturation and unknown wind disturbances.
The notion of approximate bisimulation @cite_21 can be used to construct a discrete abstraction of the continuous state space such that the observed behavior of the corresponding abstract system is close'' to that of the original continuous system. Girard in a series of papers @cite_20 @cite_42 @cite_6 use this notion to construct safety-preserving controllers for approximately bisimilar discrete abstractions and prove that the controller is for the original systems. The technique is applied to incrementally stable switched systems (for which approximately bisimilar discrete abstractions of arbitrary precision can be constructed) with autonomous or affine dynamics, and safety-preserving switched controllers are synthesized. The abstraction, however, relies on sampling of time and space (i.e. gridding) and therefore its applicability appears to be limited to low-dimensional systems---even when multi-scale abstraction (adaptive gridding) techniques are employed.
@cite_21 @cite_42 @cite_6 @cite_20
2074027094 1980222041 2962709723 2122311520
In this paper, we define the notion of approximate bisimulation relation between two continuous systems. While exact bisimulation requires that the observations of two systems are and remain identical, approximate bisimulation allows the observations to be different provided the distance between them remains bounded by some parameter called precision. Approximate bisimulation relations are conveniently defined as level sets of a so-called bisimulation function which can be characterized using Lyapunov-like differential inequalities. For a class of constrained linear systems, we develop computationally effective characterizations of bisimulation functions that can be interpreted in terms of linear matrix inequalities and optimal values of static games. We derive a method to evaluate the precision of the approximate bisimulation relation between a constrained linear system and its projection. This method has been implemented in a Matlab toolbox: MATISSE. An example of use of the toolbox in the context of safety verification is shown. We propose a technique for the synthesis of safety controllers for switched systems using multi-scale abstractions. To this end we build on a recent notion of multi-scale discrete abstractions for incrementally stable switched systems. These abstractions are defined on a sequence of embedded lattices approximating the state-space, the finer ones being used only in a restricted area where fast switching is needed. This makes it possible to deal with fast switching while keeping the number of states in the abstraction at a reasonable level. We present a synthesis algorithm that exploits the specificities of multi-scale abstractions. The abstractions are computed on the fly during controller synthesis. The finest scales of the abstraction are effectively explored only when fast switching is needed, that is when the system approaches the unsafe set. We provide experimental results that show drastic improvements of the complexity of controller synthesis using multi-scale abstractions instead of uniform abstractions. In this paper, we consider the problem of controller design using approximately bisimilar abstractions with an emphasis on safety and reachability specifications. We propose abstraction-based approaches to controller synthesis for both types of specifications. We start by synthesizing a controller for an approximately bisimilar abstraction. Then, using a concretization procedure, we obtain a controller for our initial system that is proved ''correct by design''. We provide guarantees of performance by giving estimates of the distance of the synthesized controller to the maximal (i.e., the most permissive) safety controller or to the time-optimal reachability controller. Finally, we use these techniques, combined with discrete approximately bisimilar abstractions of switched systems developed recently, for switching controller synthesis. This paper deals with the synthesis of state-feedback controllers using approximately bisimilar abstractions with an emphasis on safety problems. Such problems consist in synthesizing a controller that restricts the behaviors of a system so that its outputs remain in some specified safe set. One is usually interested in designing a controller that is as permissive as possible since this enables to ensure, a posteriori, secondary control objectives. Using the natural refinement technique for approximately bisimilar abstractions, a controller for a system can be synthesized from a controller for an abstraction. However, these controllers have some limitations in terms of performances, implementation cost and robustness. The main contribution of this paper is a new procedure for the synthesis of controllers for safety specifications using approximately bisimilar abstractions. Given a controller for an abstraction, we describe an approach for synthesizing a controller for the system that does not suffer from the previous limitations. Moreover, we show that if the controller of the abstraction is the maximal controller (i.e. the most permissive) then we can evaluate the distance between the synthesized controller and the maximal controller of the system. This distance can be made arbitrarily small by choosing sufficiently precise abstractions. We apply our results to synthesis problems for switched systems.