Robustness-by-Construction Synthesis: Adapting to the Environment at Runtime



Nayak, Satya Prakash, Neider, Daniel and Zimmermann, Martin ORCID: 0000-0002-8038-2453
(2022) Robustness-by-Construction Synthesis: Adapting to the Environment at Runtime. .

Access the full-text of this item by clicking on the Open Access link.

Abstract

While most of the current synthesis algorithms only focus on correctness-by-construction, ensuring robustness has remained a challenge. Hence, in this paper, we address the robust-by-construction synthesis problem by considering the specifications to be expressed by a robust version of Linear Temporal Logic (LTL ), called robust LTL (rLTL ). rLTL has a many-valued semantics to capture different degrees of satisfaction of a specification, i.e., satisfaction is a quantitative notion. We argue that the current algorithms for rLTL synthesis do not compute optimal strategies in a non-antagonistic setting. So, a natural question is whether there is a way of satisfying the specification “better” if the environment is indeed not antagonistic. We address this question by developing two new notions of strategies. The first notion is that of adaptive strategies, which, in response to the opponent’s non-antagonistic moves, maximize the degree of satisfaction. The idea is to monitor non-optimal moves of the opponent at runtime using multiple parity automata and adaptively change the system strategy to ensure optimality. The second notion is that of strongly adaptive strategies, which is a further refinement of the first notion. These strategies also maximize the opportunities for the opponent to make non-optimal moves. We show that computing such strategies for rLTL specifications is not harder than the standard synthesis problem, e.g., computing strategies with LTL specifications, and takes doubly-exponential time.

Item Type: Conference or Workshop Item (Unspecified)
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 03 Mar 2023 09:33
Last Modified: 03 Mar 2023 09:33
DOI: 10.1007/978-3-031-19849-6_10
Open Access URL: https://doi.org/10.48550/arXiv.2204.10912
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3168719