×

Reachability for partially observable discrete time stochastic hybrid systems. (English) Zbl 1297.93030

Summary: When designing optimal controllers for any system, it is often the case that the true state of the system is unknown to the controller. Imperfect state information must be taken into account in the controller’s design in order to preserve its optimality. The same is true when performing reachability calculations. To estimate the probability that the state of a stochastic system reaches, or stays within, some set of interest in a given time horizon, it is necessary to find a controller that drives the system to that set with maximum probability, given the controller’s knowledge of the true state of the system. To date, little work has been done on stochastic reachability calculations with partially observable states. The work that has been done relies on converting the reachability optimization problem to one with an additive cost function, for which theoretical results are well known. Our approach is to preserve the multiplicative cost structure when deriving a sufficient statistic that reduces the problem to one of perfect state information. Our transformation includes a change of measure that simplifies the distribution of the sufficient statistic conditioned on its previous value. We develop a dynamic programming recursion for the solution of the equivalent perfect information problem, proving that the recursion is valid, an optimal solution exists, and results in the same solution as to the original problem. We also show that our results are equivalent to those for the reformulated additive cost problem, and so such a reformulation is not required.

MSC:

93B03 Attainable sets, reachability
93E03 Stochastic systems in control theory (general)
93C30 Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems)
93E20 Optimal stochastic control
90C39 Dynamic programming

Software:

ToolboxLS

References:

[1] 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
[2] Aoki, M., Optimization of stochastic systems: topics in discrete-time dynamics (1989), Academic Press, Inc · Zbl 0699.93098
[3] Bai, H.; Hsu, D.; Lee, W.; Ngo, V. A., Monte Carlo value iteration for continuous-state POMDPs, (Algorithmic foundations of robotics IX, Vol. 68 (2011)), 175-191 · Zbl 1220.68089
[4] Bertsekas, D. P.; Shreve, S. E., Stochastic optimal control: the discrete-time case (1996), Athena Scientific
[5] Brunskill, E.; Kaelbling, L.; Lozano-Perez, T.; Roy, N., Planning in partially-observable switching-mode continuous domains, Annals of Mathematics and Artificial Intelligence, 58, 185-216 (2010) · Zbl 1207.90095
[7] Caldwell, T.; Murphy, T., Switching mode generation and optimal estimation with application to skid-steering, Automatica, 47, 50-64 (2011) · Zbl 1209.93074
[9] Ding, J.; Kamgarpour, M.; Summers, S.; Abate, A.; Lygeros, J.; Tomlin, C., A stochastic games framework for verification and control of discrete time stochastic hybrid systems, Automatica, 49, 9, 2665-2674 (2013) · Zbl 1364.93857
[10] Elliot, R. J., A general recursive discrete-time filter, Journal of Applied Probability, 30, 3, 575-588 (1993) · Zbl 0787.93093
[12] Fernandez-Gaucherand, E.; Marcus, S. I., Risk-sensitive optimal control of hidden Markov models: Structural results, IEEE Transactions on Automatic Control, 42, 10, 1418-1422 (1997) · Zbl 0891.93087
[13] Hofbaur, M. W.; Williams, B. C., Hybrid estimation of complex systems, IEEE Transactions on Systems, Man, and Cybernetics, 34, 5, 2178-2191 (2004)
[14] Hu, J.; Lygeros, J.; Sastry, S., Towards a theory of stochastic hybrid systems, (Hybrid systems: computation and control (2000)), 160-173 · Zbl 0962.93082
[15] James, M. R.; Baras, J. S.; Elliot, R. J., Risk-sensitive control and dynamic games for partially observed discrete-time nonlinear systems, IEEE Transactions on Automatic Control, 39, 4, 780-792 (1994) · Zbl 0807.93067
[17] Koutsoukos, X.; Kurien, J.; Zhao, F., Estimation of distributed hybrid systems using particle filtering methods, (Hybrid Systems: Computation and Control (2003)), 298-313 · Zbl 1032.68509
[19] Mitchell, I., The flexible, extensible and efficient toolbox of level set methods, Journal of Scientific Computing, 35, 300-329 (2008) · Zbl 1203.65295
[20] Porta, J. M.; Vlassis, N.; Spain, M. T.; Poupart, P., Point-based value iteration for continuous POMDPs, Journal of Machine Learning Research, 7, 2329-2367 (2006) · Zbl 1222.90078
[21] Prandini, M.; Hu, J., (Stochastic reachability: theoretical foundations and numerical approximation. Stochastic reachability: theoretical foundations and numerical approximation, Lecture notes in control and information sciences (2006), Springer Verlag), 107-139 · Zbl 1130.93050
[22] Sanjeev Arulampalam, M.; Simon Maskell, N. G.; Clapp, T., A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking, IEEE Transactions on Signal Processing, 50, 2 (2002)
[23] Shiryaev, A., On Markov sufficient statistics in nonadditive Bayes problems of sequential analysis, Theory of Probability and its Applications, 9, 4, 604-618 (1964)
[24] Soudjani, S.; Abate, A., Adaptive and sequential gridding procedures for the abstraction and verification of stochastic processes, SIAM Journal on Applied Dynamical Systems, 12, 2, 921-956 (2013) · Zbl 1278.93243
[25] Stein, E.; Shakarchi, R., (Real analysis: measure theory, integration, and Hilbert spaces. Real analysis: measure theory, integration, and Hilbert spaces, Princeton lectures in analysis (2005), Princeton University Press) · Zbl 1081.28001
[26] 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
[27] Tkachev, I.; Katoen, J. P.; Mereacre, A.; Abate, A., Quantitative automata-based controller synthesis for non-autonomous stochastic hybrid systems, (Hybrid systems: computation and control (2013)), 293-302 · Zbl 1362.68189
[28] Tomlin, C.; Mitchell, I.; Bayen, A.; Oishi, M., Computational techniques for the verification and control of hybrid systems, Proceedings of the IEEE, 91, 986-1001 (2003)
[29] Verma, R.; del Vecchio, D., Safety control of hidden mode hybrid systems, IEEE Transactions on Automatic Control, 57, 62-77 (2012) · Zbl 1369.93391
[30] Vrakopoulou, M.; Margellos, K.; Lygeros, J.; Andersson, G., Probabilistic guarantees for the n-1 security of systems with wind power generation, (Reliability and risk evaluation of wind integrated power systems (2013), Springer, India), 59-73
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.