We introduce the concept of memoryless concretization relation ( <?TeX $\operatorname{MCR}$?> Math 1 ) to describe abstraction within the context of controller synthesis. This relation is a specific instance of alternating simulation relation ( <?TeX $\operatorname{ASR}$?> Math 2 ), where it is possible to simplify the controller architecture. In the case of <?TeX $\operatorname{ASR}$?> Math 3 , the concretized controller needs to simulate the concurrent evolution of two systems, the original and abstract systems, while for <?TeX $\operatorname{MCR}$?> Math 4 , the designed controllers only need knowledge of the current concrete state. We demonstrate that the distinction between <?TeX $\operatorname{ASR}$?> Math 5 and <?TeX $\operatorname{MCR}$?> Math 6 becomes significant only when a non-deterministic quantizer is involved, such as in cases where the state space discretization consists of overlapping cells. We also show that any abstraction of a system that alternatingly simulates a system can be completed to satisfy <?TeX $\operatorname{MCR}$?> Math 7 at the expense of increasing the non-determinism in the abstraction. We clarify the difference between the <?TeX $\operatorname{MCR}$?> Math 8 and the feedback refinement relation ( <?TeX $\operatorname{FRR}$?> Math 9 ), showing in particular that the former allows for non-constant controllers within cells. This provides greater flexibility in constructing a practical abstraction, for instance, by reducing non-determinism in the abstraction. Finally, we prove that this relation is not only sufficient, but also necessary, for ensuring the above properties.

We tackle the problem of pedestrian indoor navigation with Magneto-Inertial Dead Reckoning technology (MIDR) with the integration of the data provided by a Magneto-Inertial Measurement Unit (MIMU). This method is well-known in the literature and very efficient if the spatial distribution of the magnetic field is nonuniform and the gradient of sufficiently high magnitude. However, the quality of the magnetic information decreases as the pedestrian moves toward a weak magnetic zone. We propose, characterize and test a new correction technique of the MDIR velocity based on the detection of walking steps and dynamical modeling of the walk itself.

In this paper, we develop tools to analyze stability properties of discrete-time switched linear systems driven by switching signals belonging to a given ω- regular language. More precisely, we assume switching signals to be generated by a Büchi automaton where the alphabet corresponds to the modes of the switched system. We define notions of attractivity and uniform stability for this type of systems and also of uniform exponential stability when the considered Büchi automaton is deterministic. We then provide sufficient conditions to check these properties using Lyapunov and automata theoretic techniques. For a subclass of such systems with invertible matrices, we show that these conditions are also necessary. We finally show an example of application in the context of synchronization of oscillators over a communication network.

Symbolic control aims at designing "correct by construction" controllers for continuous dynamical systems, by using algorithmic discrete synthesis techniques. The key concept in symbolic control is that of symbolic model (also called finite abstraction), which is a finite-state dynamical system, obtained by abstracting continuous trajectories over a finite set of symbols. When the symbolic and the continuous dynamics are formally related by some behavioral relationship (e.g. simulation or bisimulation relations), controllers synthesized for the symbolic model using discrete synthesis techniques can be refined to certified controllers for the original continuous system. Computation of finite abstractions is often based on discretization of the state and input spaces and therefore the symbolic control approach suffers from scalability issues. However, the design of large systems can still be tackled by means of compositional techniques. In this talk, we will present some recent results on compositional synthesis in the symbolic control approach. Firstly, we will present an approach to compute abstractions of systems made of several, possibly overlapping components. Secondly, we will show how to synthesize decentralized (and possibly asynchronous) controllers for invariance properties, by combining these overlapping abstractions and assume-guarantee contracts. In the last part of the talk, motivated by the use of parametric assume-guarantee contracts for stability properties, we will show recent developments on abstraction-based quantitative synthesis.

In this work, we present an application of symbolic control and contract based design techniques to vehicle platooning. We use a compositional approach based on continuous-time assume-guarantee contracts. Each vehicle in the platoon is assigned an assume-guarantee contract; and a controller is synthesized using symbolic control to enforce the satisfaction of this contract. The assume-guarantee framework makes it possible to deal with different types of vehicles and asynchronous controllers (i.e controllers with different sampling periods). Numerical results illustrate the effectiveness of the approach.

We consider a new way of describing complex control problems for dynamic systems called hybrid programs. Hybrid program is a finite state automaton whose states describe elementary tasks of reachability and safety defined on a transition system ([3, 5]). The proposed approach to complex control problems description could be seen as an alternative to linear temporal logic (see e.g. [1]). We provide an example to illustrate the approach.

No abstract available.

Timing contracts for embedded controller implementation specify the constraints on the time instants at which certain operations are performed such as sampling, actuation, computation, etc. Several previous works have focused on stability analysis of embedded control systems under such timing contracts. In this paper, we consider the scheduling of embedded controllers on a shared computational platform. Given a set of controllers, each of which is subject to a timing contract, we synthesize a dynamic scheduling policy, which guarantees that each timing contract is satisfied and that the shared computational resource is allocated to at most one embedded controller at any time. The approach is based on a timed game formulation whose solution provides a suitable scheduling policy. In the second part of the paper, we consider the problem of synthesizing a set of timing contracts that guarantee at the same time the schedulability and the stability of the embedded controllers.

Timing contracts for embedded controller implementation specify the constraints on the time instants at which certain operations are performed such as sampling, actuation, computation, etc. In this paper, we consider the problem of verifying the stability of embedded control systems under such timing contracts. Reformulating the problem in the framework of impulsive linear systems, we provide theoretical conditions for stability and a verification algorithm based on reachability analysis. In the second part of the paper, given a model of the plant and of the controller we propose an approach to synthesize timing contracts that guarantee stability.

We describe an application of symbolic control to ventilation regulation in buildings. The monotonicity property of a nonlinear control system subject to disturbances, modeling the process, is exploited to obtain symbolic abstractions, in the sense of alternating simulation. The resulting abstractions consist of non-deterministic finite transition systems, for which we can synthesize supervisory safety controllers to keep the room temperatures within prescribed bounds. To choose among possible control inputs preserving safety, we consider the problem of minimizing a given cost function and apply a receding horizon control scheme. The approach has been applied to temperature regulation on a small-scale building equipped with underfloor air distribution (UFAD). To the best of our knowledge, this is the first report of experimental implementation of symbolic controllers.

By appealing to the small-gain theorem of one of the authors (Girard), we show that the 13-variable sodium-channel component of the 67-variable IMW cardiac-cell model (Iyer-Mazhari-Winslow) can be replaced by an approximately bi-similar, 2-variable HH-type (Hodgkin-Huxley) abstraction. We show that this substitution of (approximately) equals for equals is safe in the sense that the approximation error between sodium-channel models is not amplified by the feedback-loop context in which it is placed. To prove this feedback-compositionality result, we exhibit quadratic-polynomial, exponentially decaying bisimulation functions between the IMW and HH-type sodium channels, and also for the IMW-based context in which these sodium-channel models are placed. These functions allow us to quantify the overall error introduced by the sodium-channel abstraction and subsequent substitution in the IMW model. To automate computation of the bisimulation functions, we employ the SOSTOOLS optimization toolbox. Our experimental results validate our analytical findings. To the best of our knowledge, this is the first application of δ-bisimilar, feedback-assisting, compositional reasoning in biological systems.

We introduce CoSyMA, a tool for automatic controller synthesis for incrementally stable switched systems based on multi-scale discrete abstractions. The tool accepts a description of a switched system represented by a set of differential equations and the sampling parameters used to define an approximation of the state-space on which discrete abstractions are computed. The tool generates a controller - if it exists - for the system that enforces a given safety or time-bounded reachability specification. We illustrate by examples the synthesized controllers and the significant performance gains during their computation.

We consider verification problems for transition systems enriched with a metric structure. We believe that these metric transition systems are particularly suitable for the analysis of cyber-physical systems in which metrics can be naturally defined on the numerical variables of the embedded software and on the continuous states of the physical environment. We consider verification of bounded and unbounded safety properties, as well as bounded liveness properties. The transition systems we consider are nondeterministic, finitely branching, and with a finite set of initial states. Therefore, bounded safety/liveness properties can always be verified by exhaustive exploration of the system trajectories. However, this approach may be intractable in practice, as the number of trajectories usually grows exponentially with respect to the considered bound. Furthermore, since the system we consider can have an infinite set of states, exhaustive exploration cannot be used for unbounded safety verification. For bounded safety properties, we propose an algorithm which combines exploration of the system trajectories and state space reduction using merging based on a bisimulation metric. The main novelty compared to an algorithm presented recently by Lerda et al. [2008] consists in introducing a tuning parameter that improves the performance drastically. We also establish a procedure that allows us to prove unbounded safety from the result of the bounded safety algorithm via a refinement step. We then adapt the algorithm to handle bounded liveness verification. Finally, the effectiveness of the approach is demonstrated by applying it to the analysis of implementations of an embedded control loop.

Bridging the gap between model-based design and platform-based implementation is one of the critical challenges for embedded software systems. In the context of embedded control systems that interact with an environment, a variety of errors due to quantization, delays, and scheduling policies may generate executable code that does not faithfully implement the model-based design. In this article, we show that the performance gap between the model-level semantics of linear dynamic controllers, for example, the proportional-integral-derivative (PID) controllers and their implementation-level semantics, can be rigorously quantified if the controller implementation is executed on a predictable time-triggered architecture. Our technical approach uses lifting techniques for periodic time-varying linear systems in order to compute the exact error between the model semantics and the execution semantics. Explicitly computing the impact of the implementation on overall system performance allows us to compare and partially order different implementations with various scheduling or timing characteristics.

When available, discrete abstractions provide an appealing approach to controller synthesis. Recently, an approach for computing discrete abstractions of incrementally stable switched systems has been proposed, using the notion of approximate bisimulation. This approach is based on sampling of time and space where the sampling parameters must satisfy some relation in order to achieve a certain precision. Particularly, the smaller the sampling period, the finer the lattice approximating the state-space and the larger the number of states in the abstraction. This renders the use of these abstractions for synthesis of fast switching controllers computationally prohibitive. In this paper, we present a novel class of multiscale discrete abstractions for switched systems that allows us to deal with fast switching while keeping the number of states in the abstraction at a reasonable level. The transitions of our abstractions have various durations: for transitions of longer duration, it is sufficient to consider abstract states on a coarse lattice; for transitions of shorter duration, it becomes necessary to use finer lattices. These finer lattices are effectively used only on a restricted area of the state-space where the fast switching occurs. We show how to use these abstractions for multiscale synthesis of self-triggered switching controllers for reachability specifications under time optimization. We illustrate the merits of our approach by applying it to the boost DC-DC converter.

This paper deals with the synthesis of state-feedback controllers using approximately bisimilar abstractions with an emphasis on safety problems.

Bridging the gap between model-based design and platform-based implementation is one of the critical challenges for embedded software systems.In the context of embedded control systems that interact with an environment, a variety of errors due to quantization, delays, and scheduling policies may generate executable code that does not faithfully implement the model-based design. In this paper, we show that the performance gap between the model-level semantics of proportional-integral-derivative (PID) controllers and their implementation-level semantics can be rigorously quantified if the controller implementation is executed on a predictable time-triggered architecture. Our technical approach uses lifting techniques for periodic, time-varying linear systems in order to compute the exact error between the model semantics and the execution semantics. Explicitly computing the impact of the implementation on overall system performance allows us to compare and partially order different implementations with various scheduling or timing characteristics.

Mapping a set of feedback control components to executable code introduces errors due to a variety of factors such as discretization, computational delays, and scheduling policies. We argue that the gap between the model and the implementation can be rigorously quantified leading to predictability if the implementation is viewed as a sequence of control blocks executed in statically allocated time slots on a time-triggered platform. For linear systems controlled by linear controllers, we show how to calculate the exact error between the model-level semantics and the execution semantics of an implementation, allowing us to compare different implementations. The calculated error of different implementations is demonstrated using simulations on illustrative examples