OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Managing temporal cycles in planning problems requiring concurrency

Cooper, Martin C. and Maris, Frédéric and Régnier, Pierre Managing temporal cycles in planning problems requiring concurrency. (2013) Computational Intelligence, 29 (1). 111-128. ISSN 0824-7935

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1111/j.1467-8640.2012.00430.x


To correctly model certain real-world planning problems, it is essential to take into account time. This is the case for problems requiring the concurrent execution of actions (known as temporally expressive problems). In this paper, we define and study the notion of temporally cyclic problems, that is problems involving sets of cyclically dependent actions. We characterize those temporal planning languages, which can express temporally cyclic problems. We also present a polynomial-time algorithm, which transforms a temporally cyclic problem into an equivalent acyclic problem. Applying our transformation allows any temporal planner to solve temporally cyclic problems without explicitly managing cyclicity. We first present our results for temporal PDDL (Planning Domain Description Language) 2.1 and then extend them to a language that allows conditions over arbitrary intervals and effects at arbitrary instants.

Item Type:Article
Additional Information:Thanks to Wiley editor. The definitive version is available at http://onlinelibrary.wiley.com The original PDF of the article can be found at Wiley Online Library website : http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.2012.00430.x/pdf
HAL Id:hal-03521582
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Deposited On:22 Jan 2015 14:03

Repository Staff Only: item control page