1/2018 - Decidability and Complexity of Timeline-based Planning over Dense Temporal Domains
Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron
| Titolo | Decidability and Complexity of Timeline-based Planning over Dense Temporal Domains |
|---|---|
| Numero | 1/2018 |
| Sottomesso da | Alberto Molinari |
| Sottomesso il | 2/5/2018 |
| Stato | Work in progress |
| Autori | Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron |
| Abstract | Planning is one of the most studied problems in computer science. In the timeline-based approach, the planning domain is modeled as 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, called synchronization rules. The temporal domain is assumed to be discrete, the dense case being dealt with by forcing a suitable discretization. In this paper, we address decidability and complexity issues for timeline-based planning over dense temporal domains without resorting to any form of discretization. We first prove that the general problem is undecidablehaving even when a single state variable is involved. Then, we show that decidability can be recovered by constraining the logical structure of synchronization rules. |
| File | 1-2018-Molinari.pdf |