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.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.