The online interactive magazine of the Association for the Advancement of Artificial Intelligence
Interactive AI Magazine

Report on the First and Second ICAPS Workshops on Hierarchical Planning

Aug 27, 2020 | Workshop Reports | 0 comments

Pascal Bercher, Australian National University
Daniel Holler, Saarland University
Gregor Behnke, University of Freiburg
Susanne Biundo, Ulm University
Vikas Shivashankar, Amazon Robotics
Ron Alford, MITRE Corporation

Hierarchical planning has attracted renewed interest in the last couple of years. As a consequence, the time was right to establish a workshop devoted entirely to hierarchical planning – an insight shared by many supporters. In this paper we report on the first ICAPS workshop on Hierarchical Planning held in Delft, The Netherlands, in 2018 as well as on the second workshop held in Berkeley, CA, USA, in 2019.

Hierarchical planning approaches incorporate hierarchies in the domain model. In the most common form, the hierarchy is defined among tasks, leading to the distinction between primitive and abstract tasks. Primitive tasks can be applied directly to world states, whereas abstract (also called compound) tasks need to be refined first. An initial set of abstract tasks is transformed into a primitive executable plan by stepwise refinement of the abstract tasks. There are also different hierarchical planning approaches, where the hierarchy is defined among goals, i.e., the facts encoding (desired) states of the world. The motivation for using hierarchical formalisms is manifold: It ranges from an explicit and predefined guidance of the plan generation process and the ability to represent complex problem solving and behavior patterns to the option of having different abstraction layers when communicating with a human user or when planning cooperatively. Hierarchies induce fundamental differences from classical, non-hierarchical planning, creating distinct computational properties and requiring separate algorithms for plan generation, plan verification, plan repair, and practical applications.

Hierarchical planning has attracted noticeably more interest in recent years, so time was right to establish a workshop at the International Conference on Automated Planning and Scheduling (ICAPS). That thought was shared by many researchers that we contacted to support our application, as can be seen from some of the most encouraging responses:

• “I applaud this initiative and would be delighted both to be listed as a potential attendee at your workshop and to be listed as an expert/someone interested in HTN.”
• “I am glad to see that after 40 years or so of hierarchical planning there will finally be a workshop dedicated to it –that is really a great idea, which we should have had 25 years or so earlier.”
• “This is a great initiative, I have asked to myself for many years why ICAPS has never organized a workshop on this topic, so I am for sure very interested in the workshop.”
• “I do wish you well with your suggested workshop proposal though as I think the time has come for HTN methods to be used in hybrid systems as one element of the AI toolkit for intelligent and autonomous systems.”

We again would like to thank our supporters for these encouraging words.

 

The First and Second Workshops on Hierarchical Planning

We founded the ICAPS workshop on hierarchical planning to bring together scientists working on different aspects of hierarchical planning to exchange ideas and foster cooperation.

In 2018, the workshop was held in Delft, The Netherlands. Prior to the half-day workshop, Pascal Bercher and Daniel H¨oller held a half-day tutorial on Hierarchical Task Network (HTN) planning. The workshop had roughly 15 participants. To spark interest in the workshop, we had two invited talks by well-known researchers from the field. The first was given by Susanne Biundo, who reported on hybrid planning, a hierarchical planning approach developed by her and her research group, and its successful (ongoing) use for user-centered planning. David Smith reported on the use and challenges when using hierarchical planning for piloting an aircraft. Abstracts of the talks are available on the workshop webpage. Since the workshop was scheduled for only half a day, we decided to have only short oral presentations for most of the long papers. Short papers were presented as posters in the coffee break. The 2019 edition of the workshop took place in Berkeley, CA, USA. That year we had a full day available for the workshop leaving more room for presentations and discussions. Dana Nau gave an invited talk about a generalization of HTN planning that includes control structures. An abstract and slides of his talk are available on the workshop’s webpage. The workshop was very well attended; we counted 29 participants and some even had to stand as the room was too crowded, which we consider rather remarkable.

Content-wise the workshops covered a lot of ground and showed the diversity of the field. One third of all papers were motivated by real-world problems: Two of them applied existing standard HTN planners to their application at hand. In one of them, the authors planned experiments in the domain of synthetic biology. They applied HTN planning to generate detailed experiment plans with the objective of optimizing costs and time spent. They further described preliminary work on how to optimize the information gained from the experiments. Another paper used HTN planning to generate construction plans for the computer game Minecraft, i.e., a description on how to assemble a given structure like a house. For the long-run, the aim was to use techniques from hierarchical planning to optimize natural-language generation. While these contributions focused on solving problems in the given domains using standard solvers, there were also papers about modifications of the actual planning systems to tailor them to a problem at hand. One was concerned with directing a movie, which gets encoded in the task hierarchy. In this domain, a certain ratio of plan depth (with regard to the task hierarchy) and plan length (with regard to the number of actions) was required, so the paper investigated heuristics for finding such preferred plans. Another application dealt with air operation plans, where a number of aircraft needed to achieve a set of objectives under various (e.g., schedule and resource) constraints. To handle these problems well, the authors proposed a multi-agent HTN planning framework that allows for decentralized planning.

Apart from these application-driven papers, most if not all standard topics from planning were addressed: Two papers proposed an extension of the typical HTN formalism. One proposed “semantic attachments” to represent numerical values set by external routines evaluated when they are accessed during the planning process. The other introduced “oracle tasks”, which were motivated by training a machine learning classifier. Oracle tasks lead to a sequence of actions in the plan that are not added by the planning system, but by some external routine. Due to the large variation in hierarchical planning formalisms, most planners defined their own input language. To make problem definitions more compatible across systems and research groups, one paper proposed a novel standard language for expressing the most common representative, HTN planning, called HDDL (Hierarchical Domain Description Language). Such input languages are usually defined in a lifted fashion, whereas many planners internally rely on a ground representation where all variables have been assigned to some constant. One work proposed a grounding procedure to create such ground models from a lifted presentation. 8 of the 14 papers accepted for the workshops directly based upon HTN planning as their hierarchical planning formalism of choice. On top, 4 further papers extended the HTN formalism for their respective purpose (or used well-known extensions from the literature, such as the specification of preconditions and effects of abstract tasks). Interestingly, only one paper was concerned with techniques for solving problems quickly. It proposed a solution-preserving SAT encoding for depth-limited HTN planning. Further extensions of this work remain state of the art with regard to efficiently solving HTN planning problems. Another work aimed at finding high-level plans, which are not yet primitive solutions. The respective procedure can thus be used as an anytime algorithm where approximations to solutions may be accepted. For the case where it has to be checked whether a plan is actually a solution for a given HTN planning problem (for example in the context of a planning competition), one paper presented a plan verifier based on grammar parsing. The approach can further be used for plan recognition, which can be regarded as generalization of verification. For the case where the execution of a plan fails, one paper proposed an approach to plan repair via model transformation. It does not require any modification to the respective planning algorithm as the repair problem is translated into an updated standard planning problem. Last but not least, two approaches to learning domain models have been presented, one for standard HTN planning, and one for hierarchical goal network (HGN) planning under uncertainty. In the latter formalism, there is no task hierarchy, but instead a hierarchy among goals.

Pascal Bercher is a Lecturer at the College of Engineering and Computer Science at the Australian National University (ANU) since 2019. He obtained his Ph.D. in 2017, which he pursued under the supervision of Susanne Biundo. He remained a post-doc at the Institute of Artificial Intelligence of Ulm University, Germany until he joined ANU. His research spans over several areas of planning, most notably complexity investigations and heuristic search in both hierarchical and non-hierarchical planning.

Daniel Holler joined the Foundations of AI Group at Saarland University headed by J¨org Hoffmann in January 2020. Before that he was at the Institute of Artificial Intelligence at Ulm University. His work is concerned with the expressivity of hierarchical and non-hierarchical planning formalisms and with solving techniques and problem compilations in HTN planning.

Gregor Behnke is a post-doctoral researcher at the Group on Foundations of Artificial Intelligence, Institute of Computer Science at University of Freiburg, Germany. He obtained his Ph.D. in 2019 under the supervision of Susanne Biundo. His research focuses on complexity investigations of HTN planning problems as well as solving them efficiently using SAT solving techniques.

Susanne Biundo is a Professor of Computer Science and the director of the Institute of Artificial Intelligence at Ulm University, Germany. Her research interests include AI Planning, Automated Reasoning, Knowledge Modeling, and Cognitive Systems. Currently, she is working on particular challenges imposed by real-world applications of planning, most notably in the context of human-technology interaction.

Vikas Shivashankar is a Research Scientist at Amazon Robotics. He received his M.S. and Ph.D. in Computer Science from the University of Maryland, and his B.Tech in Computer Science from IIT Madras. His research interests include Automated Planning and Optimization, with an emphasis on applying these techniques to robotics applications.

Ron Alford received his Ph.D. from the University of Maryland in 2014, followed by a two-year postdoc at the U.S. Naval Research Laboratory. Focusing on HTN planning as a heuristic search problem, he established a range of theoretical and practical results for HTN planning. He is now a researcher at the MITRE Corporation, working on applications of AI and robotics research.