Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.

Dynamic Programming for Nondeterministic and Stochastic Hybrid Systems Group

Hybrid systems are a challenging class of dynamical systems that integrate continuous and discrete dynamics. The former describe the evolution of continuous (real valued) state, input and output variables, typically through ordinary differential equations (in continuous time) or difference equations (in discrete time). The latter describe the evolution of discrete (finite or countably valued) state, input and output variables, typically through finite state machines, Petri nets or other abstract computational machines. The defining feature of hybrid systems is the coupling of these two diverse types of dynamics; for example, allowing the flow of the continuous state to depend on the discrete state and the transitions of the discrete state to depend on the continuous state. Hybrid systems have been the focus of intense research since the early 1990's, by control theorists, computer scientists and applied mathematicians. The main motivation for this work has been the importance of hybrid systems in a range of applications, especially in the area of embedded computation and control systems.

Much of the work on hybrid systems has focused on deterministic models that completely characterize the future of the system without allowing any uncertainty. In practice, it is often desirable to introduce some uncertainty in the models, to allow, for example, under-modeling of certain parts of the system. To address this need, researchers in discrete event and hybrid systems have introduced what are known as non-deterministic models. Here the evolution is defined in a declarative way (the system specifies what solutions are allowed) as opposed to the imperative way more common in continuous dynamical systems (the system specifies what the solution must be). Non-deterministic hybrid systems allow uncertainty to enter in a number of places: choice of continuous evolution (modeled, for example, by a differential inclusion), choice of discrete transition destination, or choice between continuous evolution and a discrete transition.

For some applications this type of non-deterministic modeling may be too coarse. For example, in Air TrafficManagement (ATM) the question ''Is it possible for a fatal accident to happen in the ATM system?'' may be interesting, but the answer (which is most likely ''yes'') does not convey nearly as much information as the answers to the questions ''What is the probability that a fatal accident happens in the ATM system?'' and ''How can the probability of a fatal accident be reduced?'' The need for finer, probabilistic analysis of uncertain systems has led to the study of an even wider class of hybrid systems, that allow things such as random failures causing unexpected transitions from one discrete state to another, or random task execution times which affect how long the system spends in different modes. Randomness may also enter the picture through noise in one or more continuous components of the system, in which case we must resort to stochastic differential equations. In this case, if a mode switch is the result of a continuous variable reaching a certain level (e.g., a tank containing fluid whose level exceeds a specific value), then the random fashion in which this variable evolves in time affects the associated switching event.

Our group has been conducting research into the fundamental properties of non-deterministic and stochastic hybrid systems, computational methods, and applications to air traffic management and systems biology. Fundamental questions of interest include existence and uniqueness of solutions for hybrid and stochastic hybrid systems, stability and reachability questions. The computational methods we develop revolve primarily around randomized methods, such as Monte Carlo simulation, Markov chain Monte Carlo, and statistical learning theory in the context of neural networks.


Our research is supported by the following projects:

Swiss National Science Foundation






Earlier related projects include:




Feednet Back