Planning problems are usually expressed by specifying which actions can be performed to obtain a given goal. In temporal planning problems, actions come with a time duration and can overlap in time, which noticeably increase the complexity of the reasoning process. Action-based temporal planning has been thoroughly studied from the complexity-theoretic point of view, and has been proved to be EXPSPACE-complete in its general formulation. Conversely, timeline-based planning problems are represented as a collection of variables whose time-varying behavior is governed by a set of temporal constraints, called synchronization rules. Timelines provide a unified framework to reason about planning and execution under uncertainty. Timeline-based systems are being successfully employed in real-world complex tasks, but, in contrast to action-based planning, little is known on their computational complexity and expressiveness. In particular, a comparison of the expressiveness of the action- and timeline-based formalisms is still missing. This paper contributes a first step in this direction by proving the EXPSPACE-completeness of timeline-based planning with no temporal horizon and bounded temporal relations only. The result is shown via a reduction from action-based temporal planning, thus proving that timelines are expressive enough to capture it.

Timelines Are Expressive Enough to Capture Action-Based Temporal Planning

GIGANTE, Nicola;MONTANARI, Angelo;
2016-01-01

Abstract

Planning problems are usually expressed by specifying which actions can be performed to obtain a given goal. In temporal planning problems, actions come with a time duration and can overlap in time, which noticeably increase the complexity of the reasoning process. Action-based temporal planning has been thoroughly studied from the complexity-theoretic point of view, and has been proved to be EXPSPACE-complete in its general formulation. Conversely, timeline-based planning problems are represented as a collection of variables whose time-varying behavior is governed by a set of temporal constraints, called synchronization rules. Timelines provide a unified framework to reason about planning and execution under uncertainty. Timeline-based systems are being successfully employed in real-world complex tasks, but, in contrast to action-based planning, little is known on their computational complexity and expressiveness. In particular, a comparison of the expressiveness of the action- and timeline-based formalisms is still missing. This paper contributes a first step in this direction by proving the EXPSPACE-completeness of timeline-based planning with no temporal horizon and bounded temporal relations only. The result is shown via a reduction from action-based temporal planning, thus proving that timelines are expressive enough to capture it.
File in questo prodotto:
File Dimensione Formato  
submitted.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: Non pubblico
Dimensione 197.27 kB
Formato Adobe PDF
197.27 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/11390/1099054
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 13
social impact