University of Maryland DRUM  
University of Maryland Digital Repository at the University of Maryland

Digital Repository at the University of Maryland (DRUM) >
College of Computer, Mathematical & Natural Sciences >
Computer Science >
Computer Science Research Works >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1903/10978

Title: HTN Planning in Answer Set Programming
Authors: Dix, Jürgen
Kuter, Ugur
Nau, Dana
Type: Technical Report
Keywords: Artificial Intelligence
Automated Planning
Logic Programming
Issue Date: 22-May-2002
Publisher: UMIACS, University of Maryland
Citation: Jürgen Dix, Ugur Kuter, and Dana Nau. HTN Planning in Answer Set Programming. Tech. Report CS-TR-4336, Dept. of Computer Science, University of Maryland, 2002.
Series/Report no.: Dept. of Computer Science;CS-TR-4336
UMIACS;UMIACS-TR-2002-18
Abstract: 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 the 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 planning 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)
URI: http://hdl.handle.net/1903/1182
http://hdl.handle.net/1903/10978
Appears in Collections:Computer Science Research Works

Files in This Item:

File Description SizeFormatNo. of Downloads
dix02.pdf487.18 kBAdobe PDF248View/Open

All items in DRUM are protected by copyright, with all rights reserved.

 

DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments