Verification of discrete time stochastic hybrid systems: a stochastic reach-avoid decision problem. (English) Zbl 1371.93220
Summary: We present a dynamic programming based solution to a probabilistic reach-avoid problem for a controlled discrete time stochastic hybrid system. We address two distinct interpretations of the reach-avoid problem via stochastic optimal control. In the first case, a sum-multiplicative cost function is introduced along with a corresponding dynamic recursion which quantifies the probability of hitting a target set at some point during a finite time horizon, while avoiding an unsafe set during each time step preceding the target hitting time. In the second case, we introduce a multiplicative cost function and a dynamic recursion which quantifies the probability of hitting a target set at the terminal time, while avoiding an unsafe set during the preceding time steps. In each case, optimal reach while avoid control policies are derived as the solution to an optimal control problem via dynamic programming. Computational examples motivated by two practical problems in the management of fisheries and finance are provided.
MSC:
| 93E20 | Optimal stochastic control |
| 93C55 | Discrete-time control/observation systems |
| 90C39 | Dynamic programming |
| 91B06 | Decision theory |
Keywords:
hybrid systems; stochastic systems; reachability; safety; target hitting; optimal control; dynamic programmingSoftware:
ToolboxLSReferences:
| [1] | Abate, A.; Amin, S.; Prandini, M.; Lygeros, J.; Sastry, S., Computational approaches to reachability analysis of stochastic hybrid systems, (Bemporad, A.; Bicchi, A.; Buttazzo, G. C., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, Vol. 4416 (2007), Springer), 4-17 · Zbl 1221.93030 |
| [2] | 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 |
| [3] | Aubin, J.-P., Viability theory (1991), Birkhauser Boston Inc.: Birkhauser Boston Inc. Cambridge, MA, USA · Zbl 0755.93003 |
| [4] | Bertsekas, D. P.; Shreve, S. E., Stochastic optimal control: the discrete-time case (2007), Athena Scientific |
| [5] | Boda, K.; Filar, J. A.; Lin, Y.; Spanjers, L., Stochastic target hitting time and the problem of early retirement, IEEE Transactions on Automatic Control, 49, 3, 409-419 (2004) · Zbl 1366.91136 |
| [7] | Bujorianu, M. L.; Lygeros, J., Reachability questions in piecewise deterministic Markov processes, (Maler, O.; Pnueli, A., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, Vol. 2623 (2003), Springer), 126-140 · Zbl 1032.93074 |
| [8] | Cai, J., Discrete time risk models under rates of interest, Probability in the Engineering and Informational Sciences, 16, 3, 309-324 (2002) · Zbl 1031.91057 |
| [9] | Cai, J.; Dickson, D. C., Ruin probabilities with a Markov chain interest model, Insurance: Mathematics and Economics, 35, 3, 513-525 (2004) · Zbl 1122.91340 |
| [10] | Chae, D.-R.; Pascoe, S., Use of simple bioeconomic models to estimate optimal effort levels in the Korean coastal flounder fisheries, Aquatic Living Resources, 18, 2, 93-101 (2005) |
| [11] | Clark, C. W., Mathematical bioeconomics: the optimal management of renewable resources (1990), Wiley-Interscience · Zbl 0712.90018 |
| [12] | Conrad, J. M., The bioeconomics of marine sanctuaries, Journal of Bioeconomics, 1, 2, 205-217 (1999) |
| [13] | Costello, C.; Polasky, S., Optimal harvesting of stochastic spatial resources, Journal of Environmental Economics and Management, 56, 1, 1-18 (2008) · Zbl 1210.91092 |
| [14] | Davis, M., Markov models and optimization (1993), Chapman & Hall: Chapman & Hall London · Zbl 0780.60002 |
| [15] | de Kok, T. G., Ruin probabilities with compounding assets for discrete time finite horizon problems, independent period claim sizes and general premium structure, Insurance: Mathematics and Economics, 33, 3, 645-658 (2003) · Zbl 1103.91379 |
| [16] | Gao, Y.; Lygeros, J.; Quincampoix, M., On the reachability problem for uncertain hybrid systems, IEEE Transactions on Automatic Control, 52, 9, 1572-1586 (2007) · Zbl 1366.91021 |
| [17] | Ghosh, M. K.; Arapostathis, A.; Marcus, S. I., Ergodic control of switching diffusions, SIAM Journal on Control and Optimization, 35, 6, 1952-1988 (1997) · Zbl 0891.93081 |
| [18] | Hu, J.; Lygeros, J.; Sastry, S., Towards a theory of stochastic hybrid systems, (Lynch, N. A.; Krogh, B. H., Hybrid systems: computation and control. Hybrid systems: computation and control, Lecture notes in computer science, Vol. 1790 (2000), Springer), 160-173 · Zbl 0962.93082 |
| [20] | 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) |
| [21] | Koutsoukos, X. D.; 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 |
| [22] | Koutsoukos, X. D.; Riley, D., Computational methods for verification of stochastic hybrid systems, IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, 38, 2, 385-396 (2008) |
| [23] | Kushner, H. J.; Dupuis, P. G., Numerical methods for stochastic control problems in continuous time (1992), Springer-Verlag: Springer-Verlag London, UK · Zbl 0754.65068 |
| [24] | Lauck, T.; Clark, C. W.; Mangel, M.; Munro, G. R., Implementing the precautionary principle in fisheries management through marine reserves, Ecological Applications, 8, sp1, S72-S78 (1998) |
| [25] | Lundberg, F., Approximerad framstilling av sannolikhetsfunktionen II. Aterforsaekring av kollektivrisker (1903), Almquist & Wiksell: Almquist & Wiksell Uppsala |
| [26] | Lygeros, J., On reachability and minimum cost optimal control, Automatica, 40, 6, 917-927 (2004) · Zbl 1068.93011 |
| [27] | Mitchell, I., The flexible, extensible and efficient toolbox of level set methods, Journal of Scientific Computing, 35, 2-3, 300-329 (2008) · Zbl 1203.65295 |
| [28] | Mitchell, I.; Tomlin, C., Level set methods for computation in hybrid systems, (Hybrid systems: computation and control (2000), Springer-Verlag: Springer-Verlag London, UK), 310-323 · Zbl 0952.93006 |
| [29] | Nostbakken, L., Stochastic modelling of the north sea herring fishery under alternative management regimes, Marine Resource Economics, 23, 1 (2008) |
| [30] | Nyrhinen, H., On the ruin probabilities in a general economic environment, Stochastic Processes and their Applications, 83, 2, 319-330 (1999) · Zbl 0997.60041 |
| [31] | Paulsen, J., Ruin theory with compounding assets — a survey, Insurance: Mathematics and Economics, 22, 1, 3-16 (1998), [special issue on the interplay between insurance, finance and control] · Zbl 0909.90115 |
| [32] | Paulsen, J., Ruin models with investment income, Probability Surveys, 5, 416 (2008) · Zbl 1189.91077 |
| [33] | Pitchford, J. W.; Codling, E. A.; Psarra, D., Uncertainty and sustainability in fisheries and the benefit of marine protected areas, Ecological Modelling, 207, 2-4, 286-292 (2007) |
| [34] | Rudin, W., Real and complex analysis (1987), McGraw-Hill, Inc.: McGraw-Hill, Inc. New York, NY, USA · Zbl 0925.00005 |
| [35] | Sainsbury, K. J.; Punt, A. E.; Smith, A. D.M., Design of operational management strategies for achieving fishery ecosystem objectives, ICES Journal of Marine Science, 57, 3, 731-741 (2000) |
| [36] | Schael, M., Control of ruin probabilities by discrete-time investments, Mathematical Methods of Operations Research, 62, 1, 141-158 (2005) · Zbl 1101.93087 |
| [37] | Sethi, G.; Costello, C.; Fisher, A.; Hanemann, M.; Karp, L., Fishery management under multiple uncertainty, Journal of Environmental Economics and Management, 50, 2, 300-318 (2005) · Zbl 1090.91072 |
| [38] | Tang, Q.; Tsitsiashvili, G., Precise estimates for the ruin probability in finite horizon in a discrete-time model with heavy-tailed insurance and financial risks, Stochastic Processes and their Applications, 108, 2, 299-325 (2003) · Zbl 1075.91563 |
| [39] | Tomlin, C.; Lygeros, J.; Sastry, S., A game theoretic approach to controller design for hybrid systems, Proceedings of the IEEE, 88, 949-969 (2000) |
| [40] | Wei, X.; Hu, Y., Ruin probabilities for discrete time risk models with stochastic rates of interest, Statistics & Probability Letters, 78, 6, 707-715 (2008) · Zbl 1136.60363 |
| [41] | White, C.; Kendall, B.; Gaines, S.; Siegel, D.; Costello, C., Marine reserve effects on fishery profit, Ecology Letters, 11, 4, 370-379 (2008) |
| [42] | Yang, H.; Zhang, L., Ruin problems for a discrete time risk model with random interest rate, Mathematical Methods of Operations Research, 63, 2, 287-299 (2006) · Zbl 1115.60084 |
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.
