[SongFZ15a] Planning for Stochastic Games with Co-safe Objectives Song, L.; Feng, Y. and Zhang, L. In International Joint Conference on Artificial Intelligence (IJCAI), pages 1682-1688, AAAI Press, 2015.
Downloads: pdf, bibURL: http://ijcai.org/papers15/Abstracts/IJCAI15-240.html Abstract. We consider planning problems for stochastic gameswith objectives specified by a branching-time logic,called probabilistic computation tree logic (PCTL).This problem has been shown to be undecidable if strategies with perfect recall, i.e., history-dependent,are considered. In this paper, we show that, if restricted to co-safe properties, a subset of PCTL properties capable to specify a wide range of properties in practice including reachability ones, the problem turns to be decidable, even when the class of general strategies is considered. We also give an algorithm for solving robust stochastic planning, where a winning strategy is tolerant to some perturbations of probabilities in the model. Our result indicates that satisfiability of co-safe PCTL is decidable as well