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) Inteligencia Artificial (Ibero-American Journal of Artificial Intelligence), 21 (62). 103-113. ISSN 1137-3601

(Document in English)

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

Official URL: https://doi.org/10.4114/intartif.vol21iss62pp103-113


Considerable improvements in the technology and performance of SAT solvers has made their use possible for the resolution of various problems in artificial intelligence, and among them that of generating plans. Recently, promising Quantified Boolean Formula (QBF) solvers have been developed and we may expect that in a near future they become as efficient as SAT solvers. So, it is interesting to use QBF language that allows us to produce more compact encodings. We present in this article a translation from STRIPS planning problems into quantified propositional formulas. We introduce two new Compact Tree Encodings: CTE-EFA based on Explanatory frame axioms, and CTE-OPEN based on causal links. Then we compare both of them to CTE-NOOP based on No-op Actions proposed in [Cashmore et al. 2012]. In terms of execution time over benchmark problems, CTE-EFA and CTE-OPEN always performed better than CTE-NOOP.

Item Type:Article
Additional Information:http://journal.iberamia.org/index.php/intartif/article/view/214
HAL Id:hal-02181997
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:11 Jun 2019 11:52

Repository Staff Only: item control page