Advertisement
Published in:
2006 | OriginalPaper | Chapter
Strategy Improvement for Stochastic Rabin and Streett Games
Authors : Krishnendu Chatterjee, Thomas A. Henzinger
Published in: CONCUR 2006 – Concurrency Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with
ω
-regular winning conditions specified as Rabin or Streett objectives. These games are NP-complete and coNP-complete, respectively. The
value
of the game for a player at a state
s
given an objective Φ is the maximal probability with which the player can guarantee the satisfaction of Φ from
s
. We present a strategy-improvement algorithm to compute values in stochastic Rabin games, where an improvement step involves solving Markov decision processes (MDPs) and nonstochastic Rabin games. The algorithm also computes values for stochastic Streett games but does not directly yield an optimal strategy for Streett objectives. We then show how to obtain an optimal strategy for Streett objectives by solving certain nonstochastic Streett games.