Optimally Resilient Strategies in Pushdown Safety Games

Neider, Daniel, Totzke, Patrick ORCID: 0000-0001-5274-8190 and Zimmermann, Martin ORCID: 0000-0002-8038-2453 Optimally Resilient Strategies in Pushdown Safety Games. [Report]

There is a more recent version of this item available.

Text
1912.04771v1.pdf - Submitted version
Download (433kB) | Preview

Abstract

Infinite-duration games with disturbances extend the classical framework of infinite-duration games, which captures the reactive synthesis problem, with a discrete measure of resilience against non-antagonistic disturbances, i.e., unmodeled situations in which the actual controller action differs from the intended one. For games played on finite arenas it is known that computing optimally resilient strategies only incurs a polynomial overhead over solving classical games. This paper studies safety games with disturbances played on infinite arenas induced by pushdown systems. We show how to compute optimally resilient strategies in triply-exponential time. For the subclass of safety games played on one-counter configuration graphs, we show that determining the degree of resilience of the initial configuration is PSPACE-complete and that optimally resilient strategies can be computed in doubly-exponential time.

Item Type:	Report
Uncontrolled Keywords:	cs.GT, cs.GT
Depositing User:	Symplectic Admin
Date Deposited:	04 Mar 2020 16:03
Last Modified:	18 Jan 2023 23:59
Related URLs:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3077736