Timeline-Based Planning over Dense Temporal Domains with Trigger-less Rules is NP-Complete

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.