Planning is one of the most studied problems in computer science. In this paper, we focus on the timeline-based approach, where the domain is modeled by a set of independent, but interacting, components, each one represented by a number of state variables, whose behavior over time (timelines) is governed by a set of temporal constraints (transition functions and synchronization rules). Whereas the time domain is usually assumed to be discrete, here we address decidability and complexity issues for timeline-based planning (TP) over dense time. We first prove that dense TP is undecidable in the general case; then, we show that decidability can be recovered by restricting to synchronization rules with a suitable future semantics. More “tractable” settings can be obtained by additionally constraining the form of intervals used in rules: EXPSPACE-completeness is obtained by avoiding singular intervals, and PSPACE-completeness by admitting only intervals of the forms [0,a] and [b,+∞[. Finally, NP-completeness can be proved for dense TP with purely existential rules only.

Timeline-based planning over dense temporal domains / Bozzelli, L.; Molinari, A.; Montanari, A.; Peron, A.; Woeginger, G.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 813:(2020), pp. 305-326. [10.1016/j.tcs.2019.12.030]

Timeline-based planning over dense temporal domains

Bozzelli L.;Montanari A.;Peron A.;
2020

Abstract

Planning is one of the most studied problems in computer science. In this paper, we focus on the timeline-based approach, where the domain is modeled by a set of independent, but interacting, components, each one represented by a number of state variables, whose behavior over time (timelines) is governed by a set of temporal constraints (transition functions and synchronization rules). Whereas the time domain is usually assumed to be discrete, here we address decidability and complexity issues for timeline-based planning (TP) over dense time. We first prove that dense TP is undecidable in the general case; then, we show that decidability can be recovered by restricting to synchronization rules with a suitable future semantics. More “tractable” settings can be obtained by additionally constraining the form of intervals used in rules: EXPSPACE-completeness is obtained by avoiding singular intervals, and PSPACE-completeness by admitting only intervals of the forms [0,a] and [b,+∞[. Finally, NP-completeness can be proved for dense TP with purely existential rules only.
2020
Timeline-based planning over dense temporal domains / Bozzelli, L.; Molinari, A.; Montanari, A.; Peron, A.; Woeginger, G.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 813:(2020), pp. 305-326. [10.1016/j.tcs.2019.12.030]
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397519308126-main.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Documento in Post-print
Licenza: Accesso privato/ristretto
Dimensione 824.31 kB
Formato Adobe PDF
824.31 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11588/828907
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact