License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.34
URN: urn:nbn:de:0030-drops-115963
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11596/
Go to the corresponding LIPIcs Volume Portal

Bozzelli, Laura ; Montanari, Angelo ; Peron, Adriano

Taming the Complexity of Timeline-Based Planning over Dense Temporal Domains

pdf-format:
LIPIcs-FSTTCS-2019-34.pdf (0.6 MB)

Abstract

The problem of timeline-based planning (TP) over dense temporal domains is known to be undecidable. In this paper, we introduce two semantic variants of TP, called strong minimal and weak minimal semantics, which allow to express meaningful properties. Both semantics are based on the minimality in the time distances of the existentially-quantified time events from the universally-quantified reference event, but the weak minimal variant distinguishes minimality in the past from minimality in the future. Surprisingly, we show that, despite the (apparently) small difference in the two semantics, for the strong minimal one, the TP problem is still undecidable, while for the weak minimal one, the TP problem is just PSPACE-complete. Membership in PSPACE is determined by exploiting a strictly more expressive extension (ECA^+) of the well-known robust class of Event-Clock Automata (ECA) that allows to encode the weak minimal TP problem and to reduce it to non-emptiness of Timed Automata (TA). Finally, an extension of ECA^+ (ECA^{++}) is considered, proving that its non-emptiness problem is undecidable. We believe that the two extensions of ECA (ECA^+ and ECA^{++}), introduced for technical reasons, are actually valuable per sé in the field of TA.

BibTeX - Entry

@InProceedings{bozzelli_et_al:LIPIcs:2019:11596,
  author =	{Laura Bozzelli and Angelo Montanari and Adriano Peron},
  title =	{{Taming the Complexity of Timeline-Based Planning over Dense Temporal Domains}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11596},
  URN =		{urn:nbn:de:0030-drops-115963},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.34},
  annote =	{Keywords: Timeline-based planning, timed automata, event-clock automata}
}

Keywords: Timeline-based planning, timed automata, event-clock automata
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI