OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Monotone Temporal Planning : tractability, extensions and applications (Extended abstract)

Cooper, Martin C. and Maris, Frédéric and Régnier, Pierre Monotone Temporal Planning : tractability, extensions and applications (Extended abstract). (2014) In: 20th International Conference on Principles and Practice of Constraint Programming (CP), 8 September 2014 - 12 September 2014 (Lyon, France).

(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.1007/978-3-319-10428-7_69


We describe a polynomially-solvable class of temporal planning problems. Polynomiality follows from two assumptions. Firstly, by supposing that each fluent (fact) can be established by at most one action, we can quickly determine which actions are necessary in any plan. Secondly, the monotonicity of fluents allows us to express planning as an instance of STP ≠  (Simple Temporal Problem with difference constraints). This class includes temporally-expressive problems requiring the concurrent execution of actions, with potential applications in the chemical, pharmaceutical and construction industries. Any (temporal) planning problem has a monotone relaxation, which can lead to the polynomial-time detection of its unsolvability in certain cases. Indeed our relaxation is orthogonal to the relaxation based on ignoring deletes used in classical planning since it preserves deletes and can also exploit temporal information.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in Volume 8656 Lecture Notes in Computer Science ISSN : 0302-9743. ISBN : 978-3319104270 The original PDF is available at: http://link.springer.com/chapter/10.1007%2F978-3-319-10428-7_69
HAL Id:hal-01153605
Audience (conference):International conference proceedings
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:20 May 2015 08:07

Repository Staff Only: item control page