KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficient SAT Encodings for Hierarchical Planning

Schreiber, Dominik ORCID iD icon 1; Pellier, Damien; Fiorino, Humbert; Balyo, Tomáš 1
1 Karlsruher Institut für Technologie (KIT)


Hierarchical Task Networks (HTN) are one of the most expressive representations for automated planning
problems. On the other hand, in recent years, the performance of SAT solvers has been drastically improved.
To take advantage of these advances, we investigate how to encode HTN problems as SAT problems. In
this paper, we propose two new encodings: GCT (Grammar-Constrained Tasks) and SMS (Stack Machine
Simulation), which, contrary to previous encodings, address recursive task relationships in HTN problems. We
evaluate both encodings on benchmark domains from the International Planning Competition (IPC), setting a
new baseline in SAT planning on modern HTN domains.

Verlagsausgabe §
DOI: 10.5445/IR/1000097221
Veröffentlicht am 12.08.2019
DOI: 10.5220/0007343305310538
Zitationen: 4
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2019
Sprache Englisch
Identifikator ISBN: 978-989758350-6
KITopen-ID: 1000097221
Erschienen in Proceedings of the 11th International Conference on Agents and Artificial Intelligence (ICAART 2019), Prague, CZ, February 19-21, 2019. Ed.: J. van den Herik. Vol. 2
Verlag SciTePress
Seiten 531–538
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page