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, Benjamin; DE GIACOMO, Giuseppe; Lomuscio, Alessio; Murano, Aniello; Rubin, Sasha. - (2021), pp. 42-51. (Intervento presentato al convegno 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, November 3-12, 2021 tenutosi a Hanoi Vietnam (online)).

Synthesizing Best-effort Strategies under Multiple Environment Specifications

Giuseppe De Giacomo
;
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
18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, November 3-12, 2021
Artificial Intelligence; Knowledge Representation; Reasoning about Actions
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Synthesizing Best-effort Strategies under Multiple Environment Specifications / Aminof, Benjamin; DE GIACOMO, Giuseppe; Lomuscio, Alessio; Murano, Aniello; Rubin, Sasha. - (2021), pp. 42-51. (Intervento presentato al convegno 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, November 3-12, 2021 tenutosi a Hanoi Vietnam (online)).
File allegati a questo prodotto
File Dimensione Formato  
Aminof_Synthesizing-Best-effort_2021.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 200.14 kB
Formato Adobe PDF
200.14 kB Adobe PDF

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/11573/1627713
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact