PANDA

personal description

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.

The newest planners of the PANDA family, PANDAPi, is available 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.

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. This software was written almost completely in Java, with only some methods written in Scala.

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 different. We will denote the POCL-based solver as PANDApocl. The two other solvers are the following: PANDApro, mainly developed by Daniel Höller, which performs progression search in the space of states (plus partial plans) similar to the SHOP family, and PANDAsat, mainly developed by Gregor Behnke, which solves HTN problems by compiling them into propositional logic. The PANDA3 software project also contains a plan verifier. Most software components are written in Java, some in Scala, none of these projects are being maintained anymore. PANDA3 is available on GitHub.

Finally, PANDAPi contains re-implementations of PANDApro and PANDAsat, as well as a significantly improved grounding procedure plus an entirely new planner, called PANDABDD. This is the newest version of the planners, all written in C++. PANDAPi is available on GitHub.

Overview

The purpose of this page is to give an overview of the current PANDA framework, i.e., these four 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

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.

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.

Solvers

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.

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.

SAT-based Solvers

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.

Search based on BDDs

Under construction! This part will be provided soon.

Plan Verification

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:

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).

Plan Repair

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.