2026-08-15T11:11:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12984 2024-03-06T10:51:30Z ddc:004 open_access

Complexity of Qualitative Timeline-Based Planning Della Monica, Dario Gigante, Nicola La Torre, Salvatore Montanari, Angelo Timeline-based planning qualitative temporal constraints complexity The timeline-based approach to automated planning was originally developed in the context of space missions. In this approach, problem domains are expressed as systems consisting of independent but interacting components whose behaviors over time, the timelines, are governed by a set of temporal constraints, called synchronization rules. Although timeline-based system descriptions have been successfully used in practice for decades, the research on the theoretical aspects only started recently. In the last few years, some interesting results have been shown concerning both its expressive power and the computational complexity of the related planning problem. In particular, the general problem has been proved to be EXPSPACE-complete. Given the applicability of the approach in many practical scenarios, it is thus natural to ask whether computationally simpler but still expressive fragments can be identified. In this paper, we study the timeline-based planning problem with the restriction that only qualitative synchronization rules, i.e., rules without explicit time bounds in the constraints, are allowed. We show that the problem becomes PSPACE-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dario Della Monica and Nicola Gigante and Salvatore La Torre and Angelo Montanari 2020 Is Part Of LIPIcs, Volume 178, 27th International Symposium on Temporal Representation and Reasoning (TIME 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2020.16 urn:nbn:de:0030-drops-129847 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2020.16 eng https://creativecommons.org/licenses/by/3.0/legalcode