Tree-REX: SAT-Based Tree Exploration for Efficient and High-Quality HTN Planning

Dominik Schreiber 1 Damien Pellier 2 Humbert Fiorino 3 Tomáš Balyo 1
1 KIT - Karlsruher Institut für Technologie
2 LIG Laboratoire d'Informatique de Grenoble - Marvin
LIG - Laboratoire d'Informatique de Grenoble
3 MAGMA
LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper, we propose a novel SAT-based planning approach to solve totally ordered hierarchical planning problems. Our approach called "Tree-like Reduction Exploration" (Tree-REX) makes two contributions: (1) it allows to rapidly solve hierarchical planning problems by making effective use of incremental SAT solving, and (2) it implements an anytime approach that gradually improves plan quality (makespan) as time resources are allotted. Incremental SAT solving is important as it reduces the encoding volume of planning problems , it builds on information obtained from previous search iterations and speeds up the search for plans. We show that Tree-REX outperforms state-of-the-art SAT-based HTN planning with respect to run times and plan quality on most of the considered IPC domains.
Document type :
Conference papers
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download
https://hal.archives-ouvertes.fr/hal-02183036
Contributor : Damien Pellier <>
Submitted on : Sunday, July 14, 2019 - 7:22:00 PM
Last modification on : Friday, October 25, 2019 - 1:29:10 AM

File

pellier19c.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-02183036, version 1

Collections

LIG | CNRS | LIG_SIC_MARVIN | UGA

Citation

Dominik Schreiber, Damien Pellier, Humbert Fiorino, Tomáš Balyo. Tree-REX: SAT-Based Tree Exploration for Efficient and High-Quality HTN Planning. International Conference on Automated Planning and Scheduling, Jul 2019, Berkeley, United States. pp.382-390. ⟨hal-02183036⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

48

Files downloads

16

Contact

CCSD