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.TIME.2020.16
URN: urn:nbn:de:0030-drops-129847
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12984/
Go to the corresponding LIPIcs Volume Portal

Della Monica, Dario ; Gigante, Nicola ; La Torre, Salvatore ; Montanari, Angelo

Complexity of Qualitative Timeline-Based Planning

pdf-format:
LIPIcs-TIME-2020-16.pdf (0.5 MB)

Abstract

The timeline-based approach to automated planning was originally developed in the context of space missions. In this approach, problem domains are expressed as systems consisting of independent but interacting components whose behaviors over time, the timelines, are governed by a set of temporal constraints, called synchronization rules. Although timeline-based system descriptions have been successfully used in practice for decades, the research on the theoretical aspects only started recently. In the last few years, some interesting results have been shown concerning both its expressive power and the computational complexity of the related planning problem. In particular, the general problem has been proved to be EXPSPACE-complete. Given the applicability of the approach in many practical scenarios, it is thus natural to ask whether computationally simpler but still expressive fragments can be identified. In this paper, we study the timeline-based planning problem with the restriction that only qualitative synchronization rules, i.e., rules without explicit time bounds in the constraints, are allowed. We show that the problem becomes PSPACE-complete.

BibTeX - Entry

@InProceedings{dellamonica_et_al:LIPIcs:2020:12984,
  author =	{Dario Della Monica and Nicola Gigante and Salvatore La Torre and Angelo Montanari},
  title =	{{Complexity of Qualitative Timeline-Based Planning}},
  booktitle =	{27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-167-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{178},
  editor =	{Emilio Mu{\~n}oz-Velasco and Ana Ozaki and Martin Theobald},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12984},
  URN =		{urn:nbn:de:0030-drops-129847},
  doi =		{10.4230/LIPIcs.TIME.2020.16},
  annote =	{Keywords: Timeline-based planning, qualitative temporal constraints, complexity}
}

Keywords: Timeline-based planning, qualitative temporal constraints, complexity
Collection: 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)
Issue Date: 2020
Date of publication: 15.09.2020

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