Learning preconditions for planning from plan traces and HTN structure

TitleLearning preconditions for planning from plan traces and HTN structure
Publication TypeJournal Articles
Year of Publication2005
AuthorsIlghami O, Nau DS, Muñoz-Avila H, Aha DW
JournalComputational Intelligence
Pagination388 - 413
Date Published2005///
ISBN Number1467-8640
Keywordscandidate elimination, HTN planning, learning, version spaces

A great challenge in developing planning systems for practical applications is the difficulty of acquiring the domain information needed to guide such systems. This paper describes a way to learn some of that knowledge. More specifically, the following points are discussed. (1) We introduce a theoretical basis for formally defining algorithms that learn preconditions for Hierarchical Task Network (HTN) methods. (2) We describe Candidate Elimination Method Learner (CaMeL), a supervised, eager, and incremental learning process for preconditions of HTN methods. We state and prove theorems about CaMeL's soundness, completeness, and convergence properties. (3) We present empirical results about CaMeL's convergence under various conditions. Among other things, CaMeL converges the fastest on the preconditions of the HTN methods that are needed the most often. Thus CaMeL's output can be useful even before it has fully converged.