OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Relaxation of Temporal Planning Problems

Cooper, Martin C. and Maris, Frédéric and Régnier, Pierre Relaxation of Temporal Planning Problems. (2013) In: International Symposium on Temporal Representation and Reasoning - TIME 2013, 26 September 2013 - 28 September 2013 (Pensacola, United States).

(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.1109/TIME.2013.28


Relaxation is ubiquitous in the practical resolution of combinatorial problems. If a valid relaxation of an instance has no solution then the original instance has no solution. A tractable relaxation can be built and solved in polynomial time. The most obvious application is the efficient detection of certain unsolvable instances. We review existing relaxation techniques in temporal planning and propose an alternative relaxation inspired by a tractable class of temporal planning problems. Our approach is orthogonal to relaxations based on the ignore-all-deletes approach used in non-temporal planning. We show that our relaxation can even be applied to non-temporal problems, and can also be used to extend a tractable class of temporal planning problems.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to IEEE editor. The definitive version is available at http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6786794
HAL Id:hal-01147301
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:
Agence nationale de la recherche (FRANCE)
Deposited On:13 Apr 2015 11:47

Repository Staff Only: item control page