In this paper, the problem of triggering early warning for intra-operative hypotension (IOH) is addressed. Recent studies on the Hypotension Prediction Index have demonstrated a gap between the results presented during model development and clinical evaluation. Thus, there is a need for better collaboration between data scientists and clinicians who need to agree on a common basis to evaluate those models. In this paper, we propose a comprehensive framework for IOH prediction: to address several issues inherent to the commonly used fixed-time-to-onset approach in the literature, a sliding window approach is suggested. The risk prediction problem is formalized with consistent precision-recall metrics rather than the receiver-operator characteristic. For illustration, a standard machine learning method is applied using two different datasets from non-cardiac and cardiac surgery. Training is done on a part of the non-cardiac surgery dataset and tests are performed separately on the rest of the non-cardiac dataset and cardiac dataset. Compared to a realistic clinical baseline, the proposed method achieves a significant improvement on the non-cardiac surgeries (precision of 48% compared to 32% for a recall of 28% (p$< $0.001)). For cardiac surgery, this improvement is less significant but still demonstrate the generalization of the model.

Abstract Cyber-physical systems are complex environments that combine physical devices (i.e., sensors and actuators) with a software controller. The ubiquity of these systems and dangers associated with their failure require the implementation of mechanisms to monitor, verify and guarantee their correct behaviour. This paper presents ParetoLib 2.0, a Python tool for offline monitoring and specification mining of cyber-physical systems. ParetoLib 2.0 uses signal temporal logic (STL) as the formalism for specifying properties on time series. ParetoLib 2.0 builds upon other tools for evaluating and mining STL expressions, and extends them with new functionalities. ParetoLib 2.0 implements a set of new quantitative operators for trace analysis in STL, a novel mining algorithm and an original graphical user interface. Additionally, the performance is optimised with respect to previous releases of the tool via data-type annotations and multi core support. ParetoLib 2.0 allows the offline verification of STL properties as well as the specification mining of parametric STL templates. Thanks to the implementation of the new quantitative operators for STL, the tool outperforms the expressiveness and capabilities of similar runtime monitors.

Self-triggered controllers have the potential to improve the state-of-the-art of Cyber-Physical Systems (CPSs) by enhancing the performance of the underlying closed-loop control systems. However, a major concern in deploying a self-triggered controller in a safety-critical CPS is that the stabilizing self-triggered controller may not always guarantee the satisfaction of the safety constraints. We propose a self-triggered control scheme that deals with the safe scheduling of control tasks for uncertain continuous-time linear systems. We derive a computationally efficient scheduling function that computes an upper bound on the next sampling period as a function of the current state in the presence of additive disturbance. To reduce the computational complexity of online reachability analysis and increase accuracy, we compute a large sequence of reachable sets offline and use these precomputed sets to derive a low-complexity online scheduling function that computes sufficiently large bounds in real time. We evaluate our algorithm on three high-dimensional benchmark control systems, where two of the examples have a twelve-dimensional joint state plus feedback input. Experimental results demonstrate that our self-triggered control algorithm guarantees the safety of the closed-loop control system through negligible online computation, establishing the feasibility of its practical implementation.

Timed formalisms such as Timed Automata (TA), Signal Temporal Logic (STL) and Timed Regular expressions (TRE) have been previously applied as behaviour specifications for monitoring or runtime verification, in particular, under the form of pattern-matching, i.e. computing the set of all the segments of a given system run that satisfy the specification.

In this paper we present ShapEx, a tool that generates random behaviors from shape expressions, a formal specification language for describing sophisticated temporal behaviors of CPS. The tool samples a random behavior in two steps: (1) it first explores the space of qualitative parameterized shapes and then (2) instantiates parameters by sampling a possibly non-linear constraint. We implement several sampling strategies in the tool that we present in the paper and demonstrate its applicability on two use scenarios.

Floating point error is a drawback of embedded systems implementation that is difficult to avoid. Computing rigorous upper bounds of roundoff errors is absolutely necessary for the validation of critical software. This problem of computing rigorous upper bounds is even more challenging when addressing non-linear programs. In this paper, we propose and compare two new algorithms based on Bernstein expansions and sparse Krivine-Stengle representations, adapted from the field of the global optimization, to compute upper bounds of roundoff errors for programs implementing polynomial and rational functions. We also provide the convergence rate of these two algorithms. We release two related software package FPBern and FPKriSten, and compare them with the state-of-the-art tools. We show that these two methods achieve competitive performance, while providing accurate upper bounds by comparison with the other tools.

Floating point error is a notable drawback of embedded systems implementation. Computing rigorous upper bounds of roundoff errors is absolutely necessary for the validation of critical software. This problem of computing rigorous upper bounds is even more challenging when addressing non-linear programs. In this paper, we propose and compare two new methods based on Bernstein expansions and sparse Krivine-Stengle representations, adapted from the field of the global optimization, to compute upper bounds of roundoff errors for programs implementing polynomial functions. We release two related software package FPBern and FPKriSten, and compare them with state of the art tools. We show that these two methods achieve competitive performance, while computing accurate upper bounds by comparison with other tools.

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.

In this work we present parallelotope bundles, i.e., sets of parallelotopes for a symbolic representation of polytopes. We define a compact representation of these objects and show that any polytope can be canonically expressed by a bundle. We propose efficient algorithms for the manipulation of bundles. Among these, we define techniques for computing tight over-approximations of polynomial transformations. We apply our framework, in combination with the Bernstein technique, to the reachability problem for polynomial dynamical systems. The accuracy and scalability of our approach are validated on a number of case studies.

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.

Parameter determination is an important task in the development of biological models. In this paper we consider parametric polynomial dynamical systems and address the following parameter synthesis problem: find a set of parameter values so that the resulting system satisfies a desired property. Our synthesis technique exploits the Bernstein polynomial representation to solve the synthesis problem using linear programming. We apply our framework to two case studies involving epidemic models.

In this paper, we present the strategy for trajectory planning that was used on-board the vehicle that completed the 103 km of the Bertha-Benz-Memorial-Route fully autonomously. We suggest a local, continuous method that is derived from a variational formulation. The solution trajectory is the constrained extremum of an objective function that is designed to express dynamic feasibility and comfort. Static and dynamic obstacle constraints are incorporated in the form of polygons. The constraints are carefully designed to ensure that the solution converges to a single, global optimum.

This paper is concerned with the reachability computation for non-linear systems using hybridization. The main idea of hybridization is to approximate a non-linear vector field by a piecewise-affine one. The piecewise-affine vector field is defined by building around the set of current states of the system a simplicial domain and using linear interpolation over its vertices. To achieve a good time-efficiency and accuracy of the reachability computation on the approximate system, it is important to find a simplicial domain which, on one hand, is as large as possible and, on the other hand, guarantees a small interpolation error. In our previous work[8], we proposed a method for constructing hybridization domains based on the curvature of the dynamics and showed how the method can be applied to quadratic systems. In this paper we pursue this work further and present two main results. First, we prove an optimality property of the domain construction method for a class of quadratic systems. Second, we propose an algorithm of curvature estimation for more general non-linear systems with non-constant Hessian matrices. This estimation can then be used to determine efficient hybridization domains. We also describe some experimental results to illustrate the main ideas of the algorithm as well as its performance.

This paper is concerned with reachable set computation for non-linear systems using hybridization. The essence of hybridization is to approximate a non-linear vector field by a simpler (such as affine) vector field. This is done by partitioning the state space into small regions within each of which a simpler vector field is defined. This approach relies on the availability of methods for function approximation and for handling the resulting dynamical systems. Concerning function approximation using interpolation, the accuracy depends on the shapes and sizes of the regions which can compromise as well the speed of reachability computation since it may generate spurious classes of trajectories. In this paper we study the relationship between the region geometry and reachable set accuracy and propose a method for constructing hybridization regions using tighter interpolation error bounds. In addition, our construction exploits the dynamics of the system to adapt the orientation of the regions, in order to achieve better time-efficiency. We also present some experimental results on a high-dimensional biological system, to demonstrate the performance improvement.

This paper presents a consistent framework for continuous stereo self-calibration. Based on a practical analysis of the sensitivity of stereo reconstruction to camera calibration uncertainties, we identify important parameters for self-calibration. We evaluate different geometric constraints for estimation and tracking of these parameters: bundle adjustment with reduced structure representation relating corresponding points in image sequences, the epipolar constraint between stereo image pairs, and trilinear constraints between image triplets. Continuous, recursive calibration refinement is obtained with a robust, adapted iterated extended Kalman filter. To achieve high accuracy, physically relevant geometric optimization criteria are formulated in a Gauss-Helmert type model. The self-calibration framework is tested on an active stereo system. Experiments with synthetic data as well as on natural indoor and outdoor imagery indicate that the different constraints are complementing each other and thus a method combining two of the above constraints is proposed: While reduced order bundle adjustment gives by far the most accurate results (and might suffice on its own in some environments), the epipolar constraint yields instantaneous calibration that is not affected by independently moving objects in the scene. Hence, it expedites and stabilizes the calibration process.

The paper deals with the problem of computing schedules for multi-threaded real-time programs. In [14] we introduced a scheduling method based on the geometrization of PV programs. In this paper, we pursue this direction further by showing a property of the geometrization that permits finding good schedules by means of efficient geometric computation. In addition, this geometric property is also exploited to reduce the scheduling problem to a simple path planning problem originating from robotics, for which we developed a scheduling algorithm using probabilistic path planning techniques. These results enabled us to implement a prototype tool that can handle models with up to 100 concurrent threads.

Embedded systems are increasingly finding their way into a growing range of physical devices. These embedded systems often consist of a collection of software threads interacting concurrently with each other and with a physical, continuous environment. While continuous dynamics have been well studied in control theory, and discrete and distributed systems have been investigated in computer science, the combination of the two complexities leads us to the recent research on hybrid systems . This paper addresses the formal analysis of such hybrid systems. Predicate abstraction has emerged to be a powerful technique for extracting finite-state models from infinite-state discrete programs. This paper presents algorithms and tools for reachability analysis of hybrid systems by combining the notion of predicate abstraction with recent techniques for approximating the set of reachable states of linear systems using polyhedra. Given a hybrid system and a set of predicates, we consider the finite discrete quotient whose states correspond to all possible truth assignments to the input predicates. The tool performs an on-the-fly exploration of the abstract system. We present the basic techniques for guided search in the abstract state-space, optimizations of these techniques, implementation of these in our verifier, and case studies demonstrating the promise of the approach. We also address the completeness of our abstraction-based verification strategy by showing that predicate abstraction of hybrid systems can be used to prove bounded safety.

The goal of this paper is to demonstrate the application of the algorithmic analysis of hybrid systems to idle speed control. This problem can be formulated as to design a safety hybrid controller. In principle, such controllers can be derived from the maximal invariant set. It is, however, hard to compute this set for a nonlinear hybrid system with both continuous control and disturbance inputs. We propose to use a class of piecewise constant control functions, which allows to develop an effective synthesis algorithm based on reachability computations. In addition, we show how assume-guarantee reasoning from automatic verification can be used to reduce the computational complexity.

This paper describes the modeling language CHARON for modular design of interacting hybrid systems. The language allows specification of architectural as well as behavioral hierarchy and discrete as well as continuous activities. The modular structure of the language is not merely syntactic, but is exploited by analysis tools and is supported by a formal semantics with an accompanying compositional theory of refinement. We illustrate the benefits of CHARON in the design of embedded control software using examples from automated highways concerning vehicle coordination.

In this paper, we suggest a novel methodology for synthesizing switching controllers for continuous and hybrid systems whose dynamics are defined by linear differential equations. We formulate the synthesis problem as finding the conditions upon which a controller should switch the behavior of the system from one "mode" to another in order to avoid a set of bad states and propose an abstract algorithm that solves the problem by an iterative computation of reachable states. We have implemented a concrete version of the algorithm, which uses a new approximation scheme for reachability analysis of linear systems.