OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Compact Tree Encodings for Planning as QBF

Gasquet, Olivier and Longin, Dominique and Maris, Frédéric and Régnier, Pierre and Valais, Maël Compact Tree Encodings for Planning as QBF. (2018) In: 13th Workshop on Constraint Satisfaction Techniques for Planningand Scheduling, in 28th International Conference on Automated Planning and Scheduling (COPLAS@ICAPS 2018), 25 June 2018 - 25 June 2018 (Delft, Netherlands).

(Document in English)

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


Considerable improvements in the technology and per-formance of SAT solvers has made their use possiblefor the resolution of various problems in artificial intel-ligence, and among them that of generating plans. Re-cently, promising Quantified Boolean Formula (QBF)solvers have been developed and we may expect that ina near future they become as efficient as SAT solvers.So, it is interesting to use QBF language that allows usto produce more compact encodings. We present in thisarticle a translation from STRIPS planning problemsinto quantified propositional formulas. We introducetwo new Compact Tree Encodings: CTE-EFA based onExplanatory frame axioms, and CTE-OPEN based oncausal links. Then we compare both of them to CTE-NOOP based on No-op Actions proposed in (Cashmore,Fox, and Giunchiglia 2012). In terms of execution timeover benchmark problems, CTE-EFA and CTE-OPENalways performed better than CTE-NOOP.

Item Type:Conference or Workshop Item (Paper)
HAL Id:hal-02279383
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:24 Jun 2019 14:00

Repository Staff Only: item control page