KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Schreiber, Dominik ORCID iD icon; Pellier, Damien; Fiorino, Humbert; Balyo, Tomáš

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.


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2019
Sprache Englisch
Identifikator ISSN: 2334-0843
KITopen-ID: 1000097225
Erschienen in Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), Berkeley, CA, July 11-15, 2019, Ed.: J. Benton
Verlag AAAI Press
Seiten 382–390
Serie 29
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page