Equivalence of games with probabilistic uncertainty and partial observation games
K. Chatterjee, M. Chmelik, R. Majumdar, in:, Springer, 2012, pp. 385–399.
http://arxiv.org/abs/1202.4140
Chatterjee, KrishnenduIST Austria ; Chmelik, MartinIST Austria; Majumdar, Ritankar
Modern Graph Algorithmic Techniques in Formal Verification
Quantitative Graph Games: Theory and Applications
Microsoft Research Faculty Fellowship
We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems.
The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.
ATVA: Automated Technology for Verification and Analysis
Thiruvananthapuram, India
Chatterjee K, Chmelik M, Majumdar R. Equivalence of games with probabilistic uncertainty and partial observation games. In: Vol 7561. Springer; 2012:385-399. doi:10.1007/978-3-642-33386-6_30
Chatterjee, K., Chmelik, M., & Majumdar, R. (2012). Equivalence of games with probabilistic uncertainty and partial observation games (Vol. 7561, pp. 385–399). Presented at the ATVA: Automated Technology for Verification and Analysis, Thiruvananthapuram, India: Springer. https://doi.org/10.1007/978-3-642-33386-6_30
Chatterjee, Krishnendu, Martin Chmelik, and Ritankar Majumdar. "Equivalence of Games with Probabilistic Uncertainty and Partial Observation Games," 7561:385–99. Springer, 2012. https://doi.org/10.1007/978-3-642-33386-6_30.
K. Chatterjee, M. Chmelik, and R. Majumdar, "Equivalence of games with probabilistic uncertainty and partial observation games," presented at the ATVA: Automated Technology for Verification and Analysis, Thiruvananthapuram, India, 2012, vol. 7561, pp. 385–399.
Chatterjee K, Chmelik M, Majumdar R. 2012. Equivalence of games with probabilistic uncertainty and partial observation games. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 7561, 385–399.
Chatterjee, Krishnendu, et al. Equivalence of Games with Probabilistic Uncertainty and Partial Observation Games. Vol. 7561, Springer, 2012, pp. 385–99, doi:10.1007/978-3-642-33386-6_30.