An Overview of Hierarchical Task Network Planning
  Hierarchies are the most common structure used to understand the world
better. In galaxies, for instance, multiple-star systems are organised in a
hierarchical system. Then, governmental and company organisations are
structured using a hierarchy, while the Internet, which is used on a daily
basis, has a space of domain names arranged hierarchically. Since Artificial
Intelligence (AI) planning portrays information about the world and reasons to
solve some of world's problems, Hierarchical Task Network (HTN) planning has
been introduced almost 40 years ago to represent and deal with hierarchies. Its
requirement for rich domain knowledge to characterise the world enables HTN
planning to be very useful, but also to perform well. However, the history of
almost 40 years obfuscates the current understanding of HTN planning in terms
of accomplishments, planning models, similarities and differences among
hierarchical planners, and its current and objective image. On top of these
issues, attention attracts the ability of hierarchical planning to truly cope
with the requirements of applications from the real world. We propose a
framework-based approach to remedy this situation. First, we provide a basis
for defining different formal models of hierarchical planning, and define two
models that comprise a large portion of HTN planners. Second, we provide a set
of concepts that helps to interpret HTN planners from the aspect of their
search space. Then, we analyse and compare the planners based on a variety of
properties organised in five segments, namely domain authoring, expressiveness,
competence, performance and applicability. Furthermore, we select Web service
composition as a real-world and current application, and classify and compare
the approaches that employ HTN planning to solve the problem of service
composition. Finally, we conclude with our findings and present directions for
future work.
