*banner
 

Algorithms for Omega-Regular Games with Imperfect Information
Krishnendu Chatterjee, Tom Henzinger

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

Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess