The PANDA Planning Framework
PANDA is a framework that combines different techniques related to Hierarchical Task Network (HTN) planning. PANDA is an acronym for Planning and Acting in a Network Decomposition Architecture. PANDA has been developed at the Institute of Artificial Intelligence at Ulm University headed by Susanne Biundo.
We are currently in the process of making all components of PANDA available here on GitHub under an open source license. When the one you are interested in is not available (yet), please contact the respective authors for an executable or the code, if required.
A (Short) History
The PANDA framework has a long development history, and the first systems worth mentioning are PANDA1 (a plan space-based planning system based on POCL planning) developed by Bernd Schattenberg and colleagues, and a domain editor tool called PANDA Editor that was a graphical editor for the XML-based input language of PANDA1, based on the Eclipse framework (also developed by Bernd Schattenberg). The development of both programs has been terminated; the software is not available anymore. Loosely based on some of the ideas implemented in PANDA1, but with significant differences already at the level of pseudo code, Bastian Seegebarth and Pascal Bercher developed PANDA2. Finally, PANDA3 includes an exact re-implementation of PANDA2, which differs mainly in the programming paradigm and design choices, but not on the level of pseudo code. It was mainly implemented by Gregor Behnke, with some help of Pascal Bercher and Daniel Höller.
On top of this "traditional" POCL-based search, PANDA3 also includes two new HTN planning systems, which work completely differently. We will denote the POCL-based solver as PANDApocl. The two other solvers are the following: PANDApro, mainly developed by Daniel Höller, performs progression search in the space of states (plus partial plans) similar to the SHOP family. PANDAsat, mainly developed by Gregor Behnke, solves HTN problems by compiling them into propositional logic.
The purpose of this page is to give an overview of the current PANDA framework, i.e., these three planners plus additional systems for plan repair, plan recognition, plan verification, and other related planning tasks – which are all based somehow on one or several of these systems.
We now describe the following components:
- Problem Definition
- Preprocessing and Grounding
- Plan Verification
- Plan and Goal Recognition
- Plan Repair
For a long time, there was no widely-used input language for hierarchical planning problems. In preparation of the International Planning Competition (IPC) 2020, we surveyed the input languages of recent systems and proposed the Hierarchical Domain Definition Language (HDDL) as standard input language for the competition. The following paper gives a discussion of the related languages and a definition of HDDL.
- D. Höller, G. Behnke, P. Bercher, S. Biundo, H. Fiorino, D. Pellier, and R. Alford. HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2020, pp. 9883–9891. (PDF)
After the results of the IPC have been published the IPC benchmark set (all in HDDL) will be made publicly available.
Preprocessing and Grounding
Like other input languages for planning problems (e.g., like PDDL for classical planning), HDDL is based on a first order input language allowing for variables in the model to enable a(n exponentially more) compact model definition.
Though the plan space search of the current system comes with some support for solving HTN planning problems in a lifted manner, the most recent developments, (especially PANDApro and PANDAsat) rely on a fully grounded (i.e. propositional) input model. To make the grounded model as small as possible, these systems come with a hierarchical and a state-based reachability analysis to prune parts of the model that cannot be part of any solution. However, creating the whole model and pruning it afterwards is not feasible. Instead, it is created in a way that avoids the creation of unreachable parts in the first place. The process is described in the following paper.
- G. Behnke, D. Höller, A. Schmid, P. Bercher, and S. Biundo. On Succinct Groundings of HTN Planning Problems. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2020, pp. 9775–9784. (PDF)
PANDA comes with three distinct approaches to solve HTN planning problems. Two are based on search, the third one on a translation to propositional logic. The most recent heuristics are only implemented for progression search. Therefore, when using PANDA in your project, either PANDApro or PANDAsat might be a good choice.
Plan Space Search
The (historically) first PANDA solvers are based on search in plan space (using Partial Order Causal Link (POCL) techniques), i.e., search nodes are partial plans that are refined until a solution to the planning problem is found. In the following, we will call it PANDApocl. Its pseudo code is described in the SoCS-14 paper. This search can be guided by heuristics. The most recent heuristics available in the current system are admissible estimates of the number of missing actions or modifications, based on a data structure called Task Decomposition Graph (TDG), all described in the IJCAI-17 paper.
- P. Bercher, G. Behnke, D. Höller, and S. Biundo. An Admissible HTN Planning Heuristic. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI organization, 2017, pp. 480–488. (PDF)
- P. Bercher, S. Keen, and S. Biundo. Hybrid Planning Heuristics Based on Task Decomposition Graphs. In: Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS). AAAI Press, 2014.
State Space Search
The second search-based solver uses Progression Search (see JAIR-20 for the algorithm). This search builds solutions in a forward manner, which enables a used heuristic to base its calculation on a fully specified and continuously updated state. We have integrated three main lines of progression heuristics. The Relaxed Composition (RC) heuristics relax the HTN model to a classical planning model and uses classical heuristics calculated on this translation to guide the HTN search (see JAIR-20, IJCAI-19, and ICAPS-18). Recently, we integrated a heuristic based on a relaxed problem class called Delete- and Ordering-free HTN planning (see IJCAI-20) computed via (I)LPs; and a heuristic based on a novel landmark generation method (see HPlan-20). When applying the system, the RC heuristics might be a good choice.
- D. Höller and P. Bercher. Landmark Extraction in HTN Planning. In: Proceedings of the 3rd ICAPS Workshop on Hierarchical Planning (HPlan). 2020.
- D. Höller, P. Bercher, and G. Behnke. Delete- and Ordering-Relaxation Heuristics for HTN Planning. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI organization, 2020, pp. 4076–4083. (PDF, BibTeX)
- D. Höller, P. Bercher, G. Behnke, and S. Biundo. HTN Planning as Heuristic Progression Search. Journal of Artificial Intelligence Research 67: pp. 835–880 (2020). (PDF)
- D. Höller, P. Bercher, G. Behnke, and S. Biundo. On Guiding Search in HTN Planning with Classical Planning Heuristics. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI organization, 2019, pp. 6171–6175. (PDF)
- D. Höller, P. Bercher, G. Behnke, and S. Biundo. A Generic Method to Guide HTN Progression Search with Classical Heuristics. In: Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS), Best Student Paper Award. AAAI Press, 2018, pp. 114–122. (PDF)
We have developed a translation from HTN planning problems to propositional logic that allows the usage of SAT solvers to find a solution for the planning problem. We thereby first bound the decomposition depth of the problem to enable the translation (of the potentially undecidable HTN problem) to the decidable SAT problem. Then we encode the problem into a propositional formula that has a solution if and only if the (bounded) planning problem has one.
There have mainly been two distinct encodings, one for totally ordered HTN planning problems (see AAAI-18), and one for partially ordered HTN planning problems (see AAAI-19 and IJCAI-19). This planner might be the currently strongest solver in the PANDA framework.
- G. Behnke, D. Höller, and S. Biundo. Bringing Order to Chaos – A Compact Representation of Partial Order in SAT-based HTN Planning. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2019, pp. 7520–7529. (PDF)
- G. Behnke, D. Höller, and S. Biundo. Finding Optimal Solutions in HTN Planning – A SAT-based Approach. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI organization, 2019, pp. 5500–5508.
- G. Behnke, D. Höller, and S. Biundo. totSAT – Totally-Ordered Hierarchical Planning through SAT. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2018, pp. 6110–6118. (PDF)
There has been some recent work on deciding whether a given sequence of actions is a solution for an HTN planning problem. This problem becomes a computationally hard problem when the decomposition leading from the initial tasks given in the problem to the potential plan is not given.
We have two distinct components in PANDA:
- For the IPC 2020 we developed a verifier that gets the produced plan and the applied sequence of decomposition methods, represented as a tree (see an example in code and graphically), as input and decides based on it.
- For cases where the decomposition sequence/tree is not available (e.g., when post-processing or guessing solutions) we developed a SAT-based verifier (see ICAPS-17).
- G. Behnke, D. Höller, and S. Biundo. This is a solution! (... but is it though?) – Verifying solutions of hierarchical planning problems. In: Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS). 2017, pp. 20–28. (PDF)
Plan and Goal Recognition
In classical planning, there has been some work on using techniques from planning to solve the task of Plan and Goal Recognition (PGR). In that spirit, we developed a translation from PGR to HTN planning problems. The transformation is based on the lifted model and the resulting problem can be solved by any planning system (see ICTAI-18).
- D. Höller, G. Behnke, P. Bercher, and S. Biundo. Plan and Goal Recognition as HTN Planning. In: Proceedings of the 30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Best Paper Award. IEEE Computer Society, 2018, pp. 466–473. (PDF)
A translation similar to the one used for PGR can also be used to repair plans when the execution of a plan fails. It is described in KI-20.