COMPLEXITY RESULTS FOR HTN PLANNING

Authors
EROL K HENDLER J NAU DS
Citation
K. Erol et al., COMPLEXITY RESULTS FOR HTN PLANNING, Annals of mathematics and artificial intelligence, 18(1), 1996, pp. 69-93
Citations number
15
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Artificial Intelligence
Journal title
Annals of mathematics and artificial intelligence → ACNP
ISSN journal
10122443
Volume
18
Issue
1
Year of publication
1996
Pages
69 - 93
Database
ISI
SICI code
1012-2443(1996)18:1<69:CRFHP>2.0.ZU;2-Q
Abstract
Most practical work on AI planning systems during the last fifteen yea rs has been based on Hierarchical Task Network (HTN) decomposition, bu t until now, there has been very little analytical work on the propert ies of HTN planners. This paper describes how the complexity of HTN pl anning varies with various conditions on the task networks, and how it compares to STRIPS-style planning.