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.


A Stochastic Games Framework for Verification and Control of Discrete Time Stochastic Hybrid Systems


J. Ding, M. Kamgarpour, S. Summers, A. Abate, J. Lygeros, C. J. Tomlin

Automatica, vol. 49, no. 9, pp. 26652674

We describe a framework for analyzing probabilistic reachability and safety problems for discrete time stochastic hybrid systems within a dynamic games setting. In particular, we consider finite horizon zero-sum stochastic games in which a control has the objective of reaching a target set while avoiding an unsafe set in the hybrid state space, and a rational adversary has the opposing objective. We derive an algorithm for computing the maximal probability of achieving the control objective, subject to the worst-case adversary behavior. From this algorithm, sufficient conditions of optimality are also derived for the synthesis of optimal control policies and worst-case disturbance strategies. These results are then specialized to the safety problem, in which the control objective is to remain within a safe set. We illustrate our modeling framework and computational approach using both a tutorial example with jump Markov dynamics and a practical application in the domain of air traffic management.


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
title = "A stochastic games framework for verification and control of discrete time stochastic hybrid systems ",
journal = "Automatica ",
volume = "49",
number = "9",
pages = "2665 - 2674",
year = "2013",
note = "",
issn = "0005-1098",
doi = "",
url = "",
author = "Jerry Ding and Maryam Kamgarpour and Sean Summers and Alessandro Abate and John Lygeros and Claire Tomlin",
keywords = "Hybrid systems",
keywords = "Stochastic systems",
keywords = "Dynamic games",
keywords = "Controller synthesis",
keywords = "Reachability "
Permanent link