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 ﬁrst 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 deﬁned 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 reﬁned ﬁrst. An initial set of abstract tasks is transformed into a primitive executable plan by stepwise reﬁnement of the abstract tasks. There are also diﬀerent hierarchical planning approaches, where the hierarchy is deﬁned 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 predeﬁned guidance of the plan generation process and the ability to represent complex problem solving and behavior patterns to the option of having diﬀerent abstraction layers when communicating with a human user or when planning cooperatively. Hierarchies induce fundamental diﬀerences from classical, non-hierarchical planning, creating distinct computational properties and requiring separate algorithms for plan generation, plan veriﬁcation, 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 ﬁnally 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 diﬀerent 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 ﬁeld. The ﬁrst 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 coﬀee 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 ﬁeld. 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 modiﬁcations 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 ﬁnding 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 classiﬁer. 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 deﬁned their own input language. To make problem deﬁnitions 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 deﬁned 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 speciﬁcation of preconditions and eﬀects 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 eﬃciently solving HTN planning problems. Another work aimed at ﬁnding 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 veriﬁer based on grammar parsing. The approach can further be used for plan recognition, which can be regarded as generalization of veriﬁcation. 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 modiﬁcation 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 Artiﬁcial 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 Hoﬀmann in January 2020. Before that he was at the Institute of Artiﬁcial 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 Artiﬁcial 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 eﬃciently using SAT solving techniques.
Susanne Biundo is a Professor of Computer Science and the director of the Institute of Artiﬁcial 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.