In timeline-based planning-an approach which is more declarative than standard, action-based planning-the domain is described by a finite set of independent, but interacting, state variables. The temporal behavior of each variable is governed by a transition function, and the sequence of values it takes over time is represented by a timeline. A set of temporal constraints, called synchronization rules, impose suitable conditions on the evolution of the values of variables. The temporal domain is commonly assumed to be discrete, and the dense case is dealt with by introducing an artificial discretization. Here, we address the problem of timeline-based planning over dense temporal domains, without discretizing them. However, since the unrestricted version of the problem has been recently proved to be undecidable, we focus on the case in which all synchronization rules are trigger-less, and prove its NP-completeness.

Timeline-based planning over dense temporal domains with trigger-less rules is NP-complete

Bozzelli, Laura
;
Montanari, Angelo
;
Peron, Adriano
;
2018

Abstract

In timeline-based planning-an approach which is more declarative than standard, action-based planning-the domain is described by a finite set of independent, but interacting, state variables. The temporal behavior of each variable is governed by a transition function, and the sequence of values it takes over time is represented by a timeline. A set of temporal constraints, called synchronization rules, impose suitable conditions on the evolution of the values of variables. The temporal domain is commonly assumed to be discrete, and the dense case is dealt with by introducing an artificial discretization. Here, we address the problem of timeline-based planning over dense temporal domains, without discretizing them. However, since the unrestricted version of the problem has been recently proved to be undecidable, we focus on the case in which all synchronization rules are trigger-less, and prove its NP-completeness.
File in questo prodotto:
File Dimensione Formato  
paper11.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Documento in Post-print
Licenza: Dominio pubblico
Dimensione 710.81 kB
Formato Adobe PDF
710.81 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: http://hdl.handle.net/11588/727612
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact