Citation
Krishnendu Chatterjee, Laurent Doyen, Tom Henzinger, Jean-Francois Raskin. "Algorithms for Omega-Regular Games with Incomplete Information". Technical report, University of California, Berkeley, UCB/EECS-2006-89, June, 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 incomplete 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 fixpoint 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 fixpoint 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 complete information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.

Electronic downloads

• http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-89.html

• HTML

  Krishnendu Chatterjee, Laurent Doyen, Tom Henzinger,
  Jean-Francois Raskin. <a
  href="http://chess.eecs.berkeley.edu/pubs/320.html"
  ><i>Algorithms for Omega-Regular Games with
  Incomplete Information</i></a>, Technical
  report,  University of California, Berkeley,
  UCB/EECS-2006-89, June, 2006.

• Plain text

  Krishnendu Chatterjee, Laurent Doyen, Tom Henzinger,
  Jean-Francois Raskin. "Algorithms for Omega-Regular
  Games with Incomplete Information". Technical report, 
  University of California, Berkeley, UCB/EECS-2006-89, June,
  2006.

• BibTeX

  @techreport{ChatterjeeDoyenHenzingerRaskin06_AlgorithmsForOmegaRegularGamesWithIncompleteInformation,
      author = {Krishnendu Chatterjee and Laurent Doyen and Tom
                Henzinger and Jean-Francois Raskin},
      title = {Algorithms for Omega-Regular Games with Incomplete
                Information},
      institution = {University of California, Berkeley},
      number = {UCB/EECS-2006-89},
      month = {June},
      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 incomplete 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 fixpoint 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
                fixpoint 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 complete
                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/320.html}
  }
  

Posted by Christopher Brooks on 7 Jun 2007.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.