3/2018 - Timeline-based planning over dense temporal domains

Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron, Gerhard Woeginger
Titolo Timeline-based planning over dense temporal domains
Numero 3/2018
Sottomesso da Alberto Molinari
Sottomesso il 4/12/2018
Stato Work in progress
Autori Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron, Gerhard Woeginger
Abstract Planning is one of the most studied problems in computer science.
In this paper, we consider the timeline-based approach,
where the planning domain is modeled by a set of independent, but interacting, components, each one represented by a number of state variables, whose behavior over time (timelines) is governed by a set of temporal constraints (synchronization rules).
Whereas the temporal domain is usually assumed to be discrete, here we address decidability and complexity issues for timeline-based planning (TP) over dense temporal domains.

First, dense TP is proved to be undecidable in the general case; then we show that decidability can be recovered by admitting synchronization rules with a suitable future semantics. More tractable results can be obtained by additionally constraining the form of intervals used in rules: EXPSPACE-completeness is obtained by avoiding singular intervals, PSPACE-completeness by admitting only intervals having the forms [0,a] and [b,+∞[. Additionally, NP-completeness can be proved for TP with only purely existential rules.

Finally, we show how systems can be described by timelines, and then model checked against property specifications given by formulas of Metric Interval Temporal Logic (MITL), a well-known timed extension of LTL.
File 3-2018-Molinari.pdf