OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Monotone Temporal Planning: Tractability, Extensions and Applications

Cooper, Martin C. and Maris, Frédéric and Régnier, Pierre Monotone Temporal Planning: Tractability, Extensions and Applications. (2014) Journal of Artificial Intelligence Research, 50. 447-485. ISSN 1076-9757

(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.1613/jair.4358


This paper describes a polynomially-solvable class of temporal planning problems. Polynomiality follows from two assumptions. Firstly, by supposing that each sub-goal fluent can be established by at most one action, we can quickly determine which actions are necessary in any plan. Secondly, the monotonicity of sub-goal 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. We also show that any (temporal) planning problem has a monotone relaxation which can lead to the polynomial-time detection of its unsolvability in certain cases. Indeed we show that our relaxation is orthogonal to relaxations based on the ignore-deletes approach used in classical planning since it preserves deletes and can also exploit temporal information.

Item Type:Article
Additional Information:Thanks to AAAI editor. The definitive version is available at https://www.jair.org/ The original PDF of the article can be found at https://www.jair.org/papers/paper4358.html
HAL Id:hal-01118794
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:20 Feb 2015 08:23

Repository Staff Only: item control page