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 775kB |
Official URL: http://dx.doi.org/10.1613/jair.4358
Abstract
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: | |
Funders: | ANR-10-BLAN-0210 |
Statistics: | download |
Deposited On: | 20 Feb 2015 08:23 |
Repository Staff Only: item control page