We formally introduce and solve the synthesis problem for LTL goals in the case of multiple, even contradicting, assumptions about the environment. Our solution concept is based on “best-effort strategies” which are agent plans that, for each of the environment specifications individually, achieve the agent goal against a maximal set of environments satisfying that specification. By means of a novel automata theoretic characterization we demonstrate that this best-effort synthesis for multiple environments is 2EXPTIME-complete, i.e., no harder than plain LTL synthesis. We study an important case in which the environment specifications are increasingly indeterminate, and show that as in the case of a single environment, best-effort strategies always exist for this setting. Moreover, we show that in this setting the set of solutions are exactly the strategies formed as follows: amongst the best-effort agent strategies for ϕ under the environment specification E1, find those that do a best-effort for ϕ under (the more indeterminate) environment specification E2, and amongst those find those that do a best-effort for ϕ under the environment specification E3, etc.

Synthesizing Best-effort Strategies under Multiple Environment Specifications / Aminof, B.; De Giacomo, G.; Lomuscio, A.; Murano, A.; Rubin, S.. - (2021), pp. 42-51. (Intervento presentato al convegno 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021 nel 2021) [10.24963/kr.2021/5].

Synthesizing Best-effort Strategies under Multiple Environment Specifications

Murano A.
;
Rubin S.
2021

Abstract

We formally introduce and solve the synthesis problem for LTL goals in the case of multiple, even contradicting, assumptions about the environment. Our solution concept is based on “best-effort strategies” which are agent plans that, for each of the environment specifications individually, achieve the agent goal against a maximal set of environments satisfying that specification. By means of a novel automata theoretic characterization we demonstrate that this best-effort synthesis for multiple environments is 2EXPTIME-complete, i.e., no harder than plain LTL synthesis. We study an important case in which the environment specifications are increasingly indeterminate, and show that as in the case of a single environment, best-effort strategies always exist for this setting. Moreover, we show that in this setting the set of solutions are exactly the strategies formed as follows: amongst the best-effort agent strategies for ϕ under the environment specification E1, find those that do a best-effort for ϕ under (the more indeterminate) environment specification E2, and amongst those find those that do a best-effort for ϕ under the environment specification E3, etc.
2021
978-1-956792-99-7
Synthesizing Best-effort Strategies under Multiple Environment Specifications / Aminof, B.; De Giacomo, G.; Lomuscio, A.; Murano, A.; Rubin, S.. - (2021), pp. 42-51. (Intervento presentato al convegno 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021 nel 2021) [10.24963/kr.2021/5].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/880480
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact