Learning hierarchical task network domains from partially observed plan traces

Hierarchical Task Network (HTN) planning is an effective yet knowledge intensive problem-solving technique. It requires humans to encode knowledge in the form of methods and action models. Methods describe how to decompose tasks into subtasks and the preconditions under which those methods are appli...

Full description

Saved in:
Bibliographic Details
Published in:Artificial intelligence 2014-07, Vol.212, p.134-157
Main Authors: Zhuo, Hankz Hankui, Muñoz-Avila, Héctor, Yang, Qiang
Format: Article
Language:English
Subjects:
Action model learning
Algorithmics. Computability. Computer arithmetics
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Exact sciences and technology
HTN planning
Learning and adaptive systems
Learning HTNs
Theoretical computing
Weighted MAX-SAT
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Hierarchical Task Network (HTN) planning is an effective yet knowledge intensive problem-solving technique. It requires humans to encode knowledge in the form of methods and action models. Methods describe how to decompose tasks into subtasks and the preconditions under which those methods are applicable whereas action models describe how actions change the world. Encoding such knowledge is a difficult and time-consuming process, even for domain experts. In this paper, we propose a new learning algorithm, called HTNLearn, to help acquire HTN methods and action models. HTNLearn receives as input a collection of plan traces with partially annotated intermediate state information, and a set of annotated tasks that specify the conditions before and after the tasks' completion. In addition, plan traces are annotated with potentially empty partial decomposition trees that record the processes of decomposing tasks to subtasks. HTNLearn outputs are a collection of methods and action models. HTNLearn first encodes constraints about the methods and action models as a constraint satisfaction problem, and then solves the problem using a weighted MAX-SAT solver. HTNLearn can learn methods and action models simultaneously from partially observed plan traces (i.e., plan traces where the intermediate states are partially observable). We test HTNLearn in several HTN domains. The experimental results show that our algorithm HTNLearn is both effective and efficient.
ISSN:0004-3702
1872-7921
DOI:10.1016/j.artint.2014.04.003