DROPS

Document

DOI: 10.4230/LIPIcs.TIME.2022.15

Giving Instructions in Linear Temporal Logic

Authors: Julian Gutierrez, Sarit Kraus, Giuseppe Perelli, and Michael Wooldridge

Published in: LIPIcs, Volume 247, 29th International Symposium on Temporal Representation and Reasoning (TIME 2022)

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.

Cite as

Julian Gutierrez, Sarit Kraus, Giuseppe Perelli, and Michael Wooldridge. Giving Instructions in Linear Temporal Logic. In 29th International Symposium on Temporal Representation and Reasoning (TIME 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 247, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gutierrez_et_al:LIPIcs.TIME.2022.15,
  author =	{Gutierrez, Julian and Kraus, Sarit and Perelli, Giuseppe and Wooldridge, Michael},
  title =	{{Giving Instructions in Linear Temporal Logic}},
  booktitle =	{29th International Symposium on Temporal Representation and Reasoning (TIME 2022)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-262-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{247},
  editor =	{Artikis, Alexander and Posenato, Roberto and Tonetta, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2022.15},
  URN =		{urn:nbn:de:0030-drops-172622},
  doi =		{10.4230/LIPIcs.TIME.2022.15},
  annote =	{Keywords: Linear Temporal Logic, Synthesis, Game theory, Multi-Agent Systems}
}

Document

DOI: 10.4230/OASIcs.CMN.2013.238

Social Narrative Adaptation using Crowdsourcing

Authors: Sigal Sina, Avi Rosenfeld, and Sarit Kraus

Published in: OASIcs, Volume 32, 2013 Workshop on Computational Models of Narrative

Abstract

In this paper we present SNACS, a novel method for creating Social Narratives that can be Adapted using information from Crowdsourcing. Previous methods for automatic narrative generation require that the primary author explicitly detail nearly all parts of the story, including details about the narrative. This is also the case for narratives within computer games, educational tools and Embodied Conversational Agents (ECA). While such narratives are well written, they clearly require significant time and cost overheads. SNACS is a hybrid narrative generation method that merges partially formed preexisting narratives with new input from crowdsourcing techniques. We compared the automatically generated narratives with those that were created solely by people, and with those that were generated semi-automatically by a state-of-the-art narrative planner. We empirically found that SNACS was effective as people found narratives generated by SNACS to be as realistic and consistent as those manually created by the people or the narrative planner. Yet, the automatically generated narratives were created with much lower time overheads and were significantly more diversified, making them more suitable for many applications.

Cite as

Sigal Sina, Avi Rosenfeld, and Sarit Kraus. Social Narrative Adaptation using Crowdsourcing. In 2013 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 32, pp. 238-256, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{sina_et_al:OASIcs.CMN.2013.238,
  author =	{Sina, Sigal and Rosenfeld, Avi and Kraus, Sarit},
  title =	{{Social Narrative Adaptation using Crowdsourcing}},
  booktitle =	{2013 Workshop on Computational Models of Narrative},
  pages =	{238--256},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-57-6},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{32},
  editor =	{Finlayson, Mark A. and Fisseni, Bernhard and L\"{o}we, Benedikt and Meister, Jan Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2013.238},
  URN =		{urn:nbn:de:0030-drops-41434},
  doi =		{10.4230/OASIcs.CMN.2013.238},
  annote =	{Keywords: Natural language interfaces, Narratives and story generation, Human computer interaction}
}

Search Results

Documents authored by Kraus, Sarit

Giving Instructions in Linear Temporal Logic

Abstract

Cite as

Social Narrative Adaptation using Crowdsourcing

Abstract

Cite as

Thanks for your feedback!

Could not send message