Planning in Answer Set Programming Using Ordered Task Decomposition

TitlePlanning in Answer Set Programming Using Ordered Task Decomposition
Publication TypeBook Chapters
Year of Publication2003
AuthorsDix J, Kuter U, Nau DS
EditorGünter A, Kruse R, Neumann B
Book TitleKI 2003: Advances in Artificial Intelligence
Series TitleLecture Notes in Computer Science
Pagination490 - 504
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-20059-8
KeywordsComputer science

In this paper we introduce a formalism for solving Hierarchical Task Network ( HTN ) Planning using Answer Set Programming ( ASP ). We consider the formulation of HTN planning as described in the SHOP planning system and define a systematic translation method from SHOP ’s representation of the planning problem into logic programs with negation. We show that our translation is sound and complete : answer sets of the logic program obtained by our translation correspond exactly to the solutions of the planning problem. We compare our method to (1) similar approaches based on non- HTN planning and (2) SHOP , a dedicated planning system. We show that our approach outperforms non- HTN methods and that its performance is better with ASP systems that allow for nonground programs than with ASP systems that require ground programs.