A stochastic games framework for verification and control of discrete time stochastic hybrid systems. (English) Zbl 1364.93857
Summary: 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.
MSC:
| 93E20 | Optimal stochastic control |
| 93E03 | Stochastic systems in control theory (general) |
| 91A15 | Stochastic games, stochastic differential games |
| 93C55 | Discrete-time control/observation systems |
| 93B03 | Attainable sets, reachability |
| 49K45 | Optimality conditions for problems involving randomness |
References:
| [2] | Abate, A.; Katoen, J. P.; Lygeros, J.; Prandini, M., Approximate model checking of stochastic hybrid systems, European Journal of Control, 16, 6, 624-641 (2010) · Zbl 1216.93091 |
| [3] | Abate, A.; Prandini, M.; Lygeros, J.; Sastry, S., Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems, Automatica, 44, 11, 2724-2734 (2008) · Zbl 1152.93051 |
| [4] | Ames, A.; Sinnet, R.; Wendel, E., Three-dimensional kneed bipedal walking: a hybrid geometric approach, (Majumdar, R.; Tabuada, P., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, vol. 5469 (2009), Springer), 16-30 · Zbl 1237.70129 |
| [5] | Amin, S.; Cardenas, A.; Sastry, S., Safe and secure networked control systems under denial-of-service attacks, (Majumdar, R.; Tabuada, P., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, vol. 5469 (2009), Springer), 31-45 · Zbl 1237.90054 |
| [6] | Balluchi, A.; Benvenuti, L.; Di Benedetto, M.; Pinello, C.; Sangiovanni-Vincentelli, A., Automotive engine control and hybrid systems: challenges and opportunities, Proceedings of the IEEE, 88, 7, 888-912 (2000) |
| [8] | Bensoussan, A.; Menaldi, J., Stochastic hybrid control, Journal of Mathematical Analysis and Applications, 249, 1, 261-288 (2000) · Zbl 0967.93097 |
| [9] | Bertsekas, D. P.; Shreve, S. E., Stochastic optimal control: the discrete time case (1978), Academic Press: Academic Press New York, NY · Zbl 0471.93002 |
| [10] | Bertsekas, D. P.; Tsitsiklis, J., Neuro-dynamic programming (1996), Athena Scientific: Athena Scientific Belmont, MA · Zbl 0924.68163 |
| [11] | Breton, M.; Alj, A.; Haurie, A., Sequential Stackelberg equilibria in two-person games, Journal of Optimization Theory and Applications, 59, 1, 71-97 (1988) · Zbl 0631.90100 |
| [12] | Brown, L. D.; Purves, R., Measurable selections of extrema, The Annals of Statistics, 1, 5, 902-912 (1973) · Zbl 0265.28003 |
| [13] | Bujorianu, M., Extended stochastic hybrid systems and their reachability problem, (Alur, R.; Pappas, G., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, vol. 2993 (2004), Springer), 234-249 · Zbl 1135.93373 |
| [15] | Folland, G. B., Real analysis: modern techniques and their applications (1999), John Wiley & Sons: John Wiley & Sons New York, NY · Zbl 0924.28001 |
| [16] | Ghosh, R.; Tomlin, C., Symbolic reachable set computation of piecewise affine hybrid automata and its application to biological modelling: Delta-Notch protein signalling, Systems Biology, 1, 1, 170-183 (2004) |
| [17] | Glover, W.; Lygeros, J., A stochastic hybrid model for air traffic control simulation, (Alur, R.; Pappas, G. J., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, vol. 2993 (2004), Springer), 372-386 · Zbl 1135.93374 |
| [18] | Gonzalez-Trejo, J. I.; Hernandez-Lerma, O.; Hoyos-Reyes, L. F., Minimax control of discrete-time stochastic systems, SIAM Journal on Control and Optimization, 41, 5, 1626-1659 (2002) · Zbl 1045.90083 |
| [19] | Hansson, H.; Jonsson, B., A logic for reasoning about time and reliability, Formal Aspects of Computing, 6, 512-535 (1994) · Zbl 0820.68113 |
| [20] | Hespanha, J. P., Stochastic hybrid systems: application to communication networks, (Alur, R.; Pappas, G. J., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, vol. 2993 (2004), Springer), 47-56 |
| [21] | Hu, J.; Lygeros, J.; Sastry, S., Towards a theory of stochastic hybrid systems, (Lynch, N.; Krogh, B., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, vol. 1790 (2000), Springer), 160-173 · Zbl 0962.93082 |
| [22] | Hu, J.; Prandini, M.; Sastry, S., Aircraft conflict prediction in the presence of a spatially correlated wind field, IEEE Transactions on Intelligent Transportation Systems, 6, 3, 326-340 (2005) |
| [23] | Hwang, I.; Seah, C. E., Intent-based probabilistic conflict detection for the next generation air transportation system, Proceedings of the IEEE, 96, 12, 2040-2059 (2008) |
| [25] | Koutsoukos, X.; Riley, D., Computational methods for reachability analysis of stochastic hybrid systems, (Hespanha, J. P.; Tiwari, A., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, vol. 3927 (2006), Springer), 377-391 · Zbl 1178.93027 |
| [26] | Kuchar, J. K.; Yang, L. C., A review of conflict detection and resolution modeling methods, IEEE Transactions on Intelligent Transportation Systems, 1, 4, 179-189 (2000) |
| [27] | Kumar, P. R.; Shiau, T. H., Existence of value and randomized strategies in zero-sum discrete-time stochastic dynamic games, SIAM Journal on Control and Optimization, 19, 5, 617-634 (1981) · Zbl 0474.93053 |
| [28] | Kushner, H. J.; Dupuis, P., Numerical methods for stochastic control problems in continuous time (1992), Springer-Verlag: Springer-Verlag London, UK · Zbl 0754.65068 |
| [29] | Lincoln, P.; Tiwari, A., Symbolic systems biology: hybrid modeling and analysis of biological networks, (Alur, R.; Pappas, G., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, vol. 2993 (2004), Springer), 147-165 |
| [30] | Lygeros, J.; Tomlin, C.; Sastry, S., Controllers for reachability specifications for hybrid systems, Automatica, 35, 3, 349-370 (1999) · Zbl 0943.93043 |
| [31] | Maitra, A.; Parthasarathy, T., On stochastic games, Journal of Optimization Theory and Applications, 5, 4, 289-300 (1970) · Zbl 0181.23204 |
| [32] | Maitra, A.; Sudderth, W., Finitely additive stochastic games with Borel measurable payoffs, International Journal of Game Theory, 27, 2, 257-267 (1998) · Zbl 0947.91013 |
| [34] | Nowak, A. S., Universally measurable strategies in zero-sum stochastic games, The Annals of Probability, 13, 1, 269-287 (1985) · Zbl 0592.90106 |
| [35] | Paielli, R. A.; Erzberger, H., Conflict probability estimation for free flight, AIAA Journal of Guidance, Control and Dynamics, 20, 3, 588-596 (1997) · Zbl 0890.90138 |
| [36] | Prajna, S.; Jadbabaie, A.; Pappas, G., A framework for worst-case and stochastic safety verification using barrier certificates, IEEE Transactions on Automatic Control, 52, 8, 1415-1428 (2007) · Zbl 1366.93711 |
| [37] | Prandini, M.; Hu, J.; Lygeros, J.; Sastry, S., A probabilistic approach to aircraft conflict detection, IEEE Transactions on Intelligent Transportation Systems, 1, 4, 199-220 (2000) |
| [38] | Rieder, U., Non-cooperative dynamic games with general utility functions, (Raghavan, T. E.S.; Ferguson, T. S.; Parthasarathy, T.; Vrieze, O. J., Stochastic games and related topics (1991), Kluwer Academic Publishers), 161-174 · Zbl 0742.90098 |
| [39] | Rudin, W., Principles of mathematical analysis (1976), McGraw-Hill: McGraw-Hill New York, NY · Zbl 0148.02903 |
| [41] | Shapley, L. S., Stochastic games, Proceedings of the National Academy of Sciences, 39, 10, 1095-1100 (1953) · Zbl 0051.35805 |
| [42] | Summers, S.; Kamgarpour, M.; Lygeros, J.; Tomlin, C., A stochastic reach-avoid problem with random obstacles, (Proceedings of the 14th international conference on hybrid systems: computation and control (2011), ACM), 251-260 · Zbl 1364.93870 |
| [43] | Summers, S.; Lygeros, J., Verification of discrete time stochastic hybrid systems: a stochastic reach-avoid decision problem, Automatica, 46, 12, 1951-1961 (2010) · Zbl 1371.93220 |
| [44] | Tomlin, C.; Pappas, G.; Sastry, S., Conflict resolution for air traffic management: a study in multiagent hybrid systems, IEEE Transactions on Automatic Control, 43, 4, 509-521 (2002) · Zbl 0904.90113 |
| [45] | Yang, L. C.; Kuchar, L., Prototype conflict alerting system for free flight, AIAA Journal of Guidance, Control and Dynamics, 20, 4, 768-773 (1997) · Zbl 0875.90312 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
