Giving instructions in Linear Temporal Logic

Julian Gutierrez, Sarit Kraus, Giuseppe Perelli, Michael Wooldridge

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Our aim is to develop a formal semantics for giving instructions to taskable agents, to investigate the complexity of decision problems relating to these semantics, and to explore the issues that these semantics raise. In the setting we consider, agents are given instructions in the form of Linear Temporal Logic (LTL) formulae; the intuitive interpretation of such an instruction is that the agent should act in such a way as to ensure the formula is satisfied. At the same time, agents are assumed to have inviolable and immutable background safety requirements, also specified as LTL formulae. Finally, the actions performed by an agent are assumed to have costs, and agents must act within a limited budget. For this setting, we present a range of interpretations of an instruction to achieve an LTL task Υ, intuitively ranging from “try to do this but only if you can do so with everything else remaining unchanged” up to “drop everything and get this done.” For each case we present a formal pre-/post-condition semantics, and investigate the computational issues that they raise.

Original languageEnglish
Title of host publication29th International Symposium on Temporal Representation and Reasoning
EditorsAlexander Artikis, Roberto Posenato, Stefano Tonetta
Place of PublicationSaarbrücken/Wadern Germany
PublisherSchloss Dagstuhl
Number of pages14
ISBN (Electronic)9783959772624
DOIs
Publication statusPublished - Nov 2022
EventInternational Symposium on Temporal Representation and Reasoning 2022 - Online, Germany
Duration: 7 Nov 20229 Nov 2022
Conference number: 29th
https://time22.time-symposium.org/ (Website)
https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16261 (Proceedings)

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl
Volume247
ISSN (Print)1868-8969

Conference

ConferenceInternational Symposium on Temporal Representation and Reasoning 2022
Abbreviated titleTIME 2022
Country/TerritoryGermany
Period7/11/229/11/22
Internet address

Keywords

  • Game theory
  • Linear Temporal Logic
  • Multi-Agent Systems
  • Synthesis

Cite this