Citation
Krishnendu Chatterjee, Tom Henzinger. "Algorithms for Omega-Regular Games with Imperfect Information". CSL 06, September, 2006.

Abstract
We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buchi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.

Electronic downloads

• csl06_paper28.ps · application/postscript · 451 kbytes

• HTML

  Krishnendu Chatterjee, Tom Henzinger. <a
  href="http://chess.eecs.berkeley.edu/pubs/237.html"
  >Algorithms for Omega-Regular Games with Imperfect
  Information</a>, CSL 06, September, 2006.

• Plain text

  Krishnendu Chatterjee, Tom Henzinger. "Algorithms for
  Omega-Regular Games with Imperfect Information". CSL
  06, September, 2006.

• BibTeX

  @inproceedings{ChatterjeeHenzinger06_AlgorithmsForOmegaRegularGamesWithImperfectInformation,
      author = {Krishnendu Chatterjee and Tom Henzinger},
      title = {Algorithms for Omega-Regular Games with Imperfect
                Information},
      booktitle = {CSL 06},
      month = {September},
      year = {2006},
      abstract = {We study observation-based strategies for
                two-player turn-based games on graphs with
                omega-regular objectives. An observation-based
                strategy relies on imperfect information about the
                history of a play, namely, on the past sequence of
                observations. Such games occur in the synthesis of
                a controller that does not see the private state
                of the plant. Our main results are twofold. First,
                we give a fixed-point algorithm for computing the
                set of states from which a player can win with a
                deterministic observation-based strategy for any
                omega-regular objective. The fixed point is
                computed in the lattice of antichains of state
                sets. This algorithm has the advantages of being
                directed by the objective and of avoiding an
                explicit subset construction on the game graph.
                Second, we give an algorithm for computing the set
                of states from which a player can win with
                probability 1 with a randomized observation-based
                strategy for a Buchi objective. This set is of
                interest because in the absence of perfect
                information, randomized strategies are more
                powerful than deterministic ones. We show that our
                algorithms are optimal by proving matching lower
                bounds. },
      URL = {http://chess.eecs.berkeley.edu/pubs/237.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 13 May 2007.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.