Planning for stochastic games with Co-safe objectives

Song, L; Feng, Y; Zhang, L

Planning for stochastic games with Co-safe objectives

Song, L Feng, Y

Zhang, L

Permalink

Publication Type:: Conference Proceeding
Citation:: IJCAI International Joint Conference on Artificial Intelligence, 2015, 2015-January pp. 1682 - 1688
Issue Date:: 2015-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (288.94 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Song, L	en_US
dc.contributor.author	Feng, Y https://orcid.org/0000-0002-3097-3896	en_US
dc.contributor.author	Zhang, L	en_US
dc.date.issued	2015-01-01	en_US
dc.identifier.citation	IJCAI International Joint Conference on Artificial Intelligence, 2015, 2015-January pp. 1682 - 1688	en_US
dc.identifier.isbn	9781577357384	en_US
dc.identifier.issn	1045-0823	en_US
dc.identifier.uri	http://hdl.handle.net/10453/41863
dc.description.abstract	We consider planning problems for stochastic games with 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.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP130102764
dc.relation.ispartof	IJCAI International Joint Conference on Artificial Intelligence	en_US
dc.title	Planning for stochastic games with Co-safe objectives	en_US
dc.type	Conference Proceeding
utslib.citation.volume	2015-January	en_US
utslib.for	080203 Computational Logic and Formal Languages	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	2015-January	en_US

Abstract:

We consider planning problems for stochastic games with 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/41863