HTN Planning in Answer Set Programming

TitleHTN Planning in Answer Set Programming
Publication TypeReports
Year of Publication2002
AuthorsDix J, Kuter U, Nau DS
Date Published2002/05/22/
InstitutionInstititue for Advanced Computer Studies, Univ of Maryland, College Park
KeywordsTechnical Report

In this paper we introduce a formalism for solving Hierarchical Task NEtwork(HTN)
Planning using Answer Set Programming (ASP). The ASP paradigm evolved out of
stable semantics for logic programs in recent years and is strongly related
to nonmonotonic
logics. We consider the formulation of HTM planning as described in the SHOP
system and define a systematic translation method from SHOP's representation
of the planning
problems into logic programs with negation. We show that our translation is
sound and complete:
answer sets of the logic programs obtained by our translation correspond exactly to the solutions
of the planning problems.
Our approach does not rly on a particular system for computing answer sets.
It can therefore
serve as a means to evaluate ASP systems by using well-established
benchmarks from the planning community. We tested our method on various such
benchmarks and used smodels and DLV for computing answer sets.
We compared 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 closer to that of SHOP, when we are using ASP
systems which allow
for nonground programs.
(Also UMIACS-TR-2002-18)