Equivalence of Games with Probabilistic Uncertainty and Partial-observation Games

Details Equivalence of Games with Probabilistic Uncertainty and Partial-observation Games Equivalence of Games with Probabilistic Uncertainty and Partial-observation Games

2012-02-19

arxiv.org/abs/1202.4140v1

Computer Science

Computer Science and Game Theory

Scientific paper

We introduce games with probabilistic uncertainty, a natural model for controller synthesis in which the controller observes the state of the system through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and for most of the decidable problems establish optimal complexity results.

Affiliated with

Also associated with

No associations

Rating

Equivalence of Games with Probabilistic Uncertainty and Partial-observation Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Equivalence of Games with Probabilistic Uncertainty and Partial-observation Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equivalence of Games with Probabilistic Uncertainty and Partial-observation Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-419395