Game Development Reference
In-Depth Information
equilibrium points. Some existing literature about non-zero-sum stochastic
games is mentioned in Section 5.2. The current knowledge is still limited.
Games with time. The modelling power of continuous-time stochastic
models such as continuous-time (semi)Markov chains (see, e.g., Norris
[1998], Ross [1996]) or the real-time probabilistic processes of Alur et al.
[1991] can be naturally extended by the element of choice. Thus, we obtain
various types of continuous-time stochastic games. Stochastic games and
MDPs over continuous-time Markov chains were studied by Baier et al.
[2005], Neuhaußer et al. [2009], Brazdil et al. [2009b] and Rabe and
Schewe [2010]. In this context, it makes sense to consider various types
of strategies that measure or ignore the elapsed time, and study specific
types of objectives that can be expressed by, e.g., the timed automata of
Alur and Dill [1994].
The above discussed concepts are to a large extent orthogonal and can be
combined almost arbitrarily. Thus, one can model very complex systems of
time, chance, and choice. Many of the fundamental results are still waiting
to be discovered.
Acknowledgements: I thank Vaclav Brozek and Tomas Brazdil for reading a
preliminary draft of this chapter. The work has been supported by the Czech
Science Foundation, grant No. P202/10/1469.
P. Abdulla, N. Henda, L. de Alfaro, R. Mayr, and S. Sandberg. Stochastic games
with lossy channels. In Proceedings of FoSSaCS 2008 , volume 4962 of Lecture
Notes in Computer Science , pages 35-49. Springer, 2005.
R. Alur and D. Dill. A theory of timed automata. Theoretical Computer Science ,
126(2):183-235, 1994. Fundamental Study.
R. Alur, C. Courcoubetis, and D. Dill. Model-checking for probabilistic real-time
systems. In Proceedings of ICALP'91 , volume 510 of Lecture Notes in Computer
Science , pages 115-136. Springer, 1991.
C. Baier, M. Großer, M. Leucker, B. Bollig, and F. Ciesinski. Controller synthesis
for probabilistic systems. In Proceedings of IFIP TCS'2004 , pages 493-506.
Kluwer, 2004.
C. Baier, H. Hermanns, J.-P. Katoen, and B. Haverkort. E cient computation of
time-bounded reachability probabilities in uniform continuous-time Markov
decision processes. Theoretical Computer Science , 345:2-26, 2005.
C. Baier, N. Bertrand, and P. Schnoebelen. On computing fixpoints in well-structured
regular model checking, with applications to lossy channel systems. In Pro-
ceedings of LPAR 2006 , volume 4246 of Lecture Notes in Computer Science ,
pages 347-361. Springer, 2006.
Search Nedrilad ::

Custom Search