The present work focuses on timeline-based planning over dense temporal domains. In automated planning, the temporal domain is commonly assumed to be discrete, the dense case being dealt with by resorting to some form of discretization. In the last years, the planning problem over dense temporal domains has been finally addressed both in the timeline-based setting and, very recently, in the action-based one. Dense timeline-based planning, in its full generality, has been shown to be undecidable. Decidability has been recovered by imposing suitable syntactic and/or semantic restrictions (the complexity of decidable fragments varies a lot, spanning from non-primitive recursive hardness to NP-completeness, passing through EXPSPACE- and PSPACE-completeness). In this paper, we proved that restricting to the future fragment is not enough to get decidability.

Undecidability of future timeline-based planning over dense temporal domains / Bozzelli, L.; Molinari, A.; Montanari, A.; Peron, A.. - 2756:(2020), pp. 155-166. (Intervento presentato al convegno 21st Italian Conference on Theoretical Computer Science, ICTCS 2020 tenutosi a Ischia, Italia nel September 14-16, 2020).

Undecidability of future timeline-based planning over dense temporal domains

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

Abstract

The present work focuses on timeline-based planning over dense temporal domains. In automated planning, the temporal domain is commonly assumed to be discrete, the dense case being dealt with by resorting to some form of discretization. In the last years, the planning problem over dense temporal domains has been finally addressed both in the timeline-based setting and, very recently, in the action-based one. Dense timeline-based planning, in its full generality, has been shown to be undecidable. Decidability has been recovered by imposing suitable syntactic and/or semantic restrictions (the complexity of decidable fragments varies a lot, spanning from non-primitive recursive hardness to NP-completeness, passing through EXPSPACE- and PSPACE-completeness). In this paper, we proved that restricting to the future fragment is not enough to get decidability.
2020
Undecidability of future timeline-based planning over dense temporal domains / Bozzelli, L.; Molinari, A.; Montanari, A.; Peron, A.. - 2756:(2020), pp. 155-166. (Intervento presentato al convegno 21st Italian Conference on Theoretical Computer Science, ICTCS 2020 tenutosi a Ischia, Italia nel September 14-16, 2020).
File in questo prodotto:
File Dimensione Formato  
paper_15(1).pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Dominio pubblico
Dimensione 608.59 kB
Formato Adobe PDF
608.59 kB Adobe PDF Visualizza/Apri

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