Krishnendu Chatterjee and Laurent Doyen and Thomas A. Henzinger and Jean-Francois Raskin

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-89

June 26, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-89.pdf

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 B\"uchi 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.

---

BibTeX citation:

@techreport{Chatterjee:EECS-2006-89,
    Author= {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A. and Raskin, Jean-Francois},
    Title= {Algorithms for Omega-Regular Games with  Incomplete Information},
    Year= {2006},
    Month= {Jun},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-89.html},
    Number= {UCB/EECS-2006-89},
    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 B\"uchi 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.},
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu 
%A Doyen, Laurent 
%A Henzinger, Thomas A. 
%A Raskin, Jean-Francois 
%T Algorithms for Omega-Regular Games with  Incomplete Information
%I EECS Department, University of California, Berkeley
%D 2006
%8 June 26
%@ UCB/EECS-2006-89
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-89.html
%F Chatterjee:EECS-2006-89