Planning Systems

Hierarchical Planning Systems

There are several systems in the literature concerned with hierarchical planning. These systems might differ from each other in technology (i.e., how the problem is being solved) as well as in the problems they can solve.

We provide a bit of information per system but refer to the literature for more details. We'd like to not provide recommendations for scientific papers since we would introduce a bias towards paper selection. We furthermore might have extend the respective selections, which would cause too much overhead. You can do the research by yourself or contact the respective authors.

Note that different planners are likely to require different output formats. However, there's a chance that the planner either natively supports HDDL (a format extending PDDL by task hierarchy, see a AAAI paper from 2020), or that there's a translation from HDDL to the planner's input format. For the latter, check out the website of the IPC 2020.

Planners are ordered alphabetically. Note that not listing scientific papers as well as even not listing authors has been done on purpose. This is basically a 'private webpage', so it should remain as neutral as possible. Listing papers might introduce a bias or be incomplete, and listing authors might be very hard as software projects usually contain many contributors; and some might "only" have contributed to theory, but not to the code base (so just the decision process on whom to add might be very hard). So instead we believe that it's the systems' authors' responsibility to provide all that information on their webpages.

CHIMP:
- URL: https://github.com/sebastianstock/chimp
- Problem class: HTN planning with task merging and time
- Input format: Uses its own format (doesn't have a name)
- Solving approach: Constraint Solving
- Further info: That planner has been applied in the context of robotics.
FAPE:
- URL: https://github.com/laas/fape
- Problem class: HTN problems with time
- Input format: ANML
- Solving approach: Search in the space of POCL plans & Constraint Solving
- Further info: PANDA-3 (not to be confused with the most-recent version PANDA-Pi, see the PANDA website for clarification) offers a translation from HDDL to ANML. However, it's likely not to work out of the box. If you'd like to use that translation, please contact Gregor Behnke.
HTN2PDDL:
- URL: http://github.com/ronwalf/HTN-Translation
- Problem class: HTN planning (and also specifically total-order HTN planning)
- Input format: HPDDL
- Solving approach: Translation into a sequence of classical planning problems.
- Further info: There exists a translation from HDDL into HPDDL, see the IPC 2020 webpage.
HyperTensioN:
- URL: https://github.com/Maumagnaguagno/HyperTensioN
- Problem class: HTN problems
- Input format: HDDL and (J)SHOP2
- Solving approach: Domain-rewriting plus blind and lifted depth-first search
- Further info: This planner participated in the IPC 2020. You can thus download the participating planner as a convenient singularity file from the IPC 2020 webpage.
I-X/I-Plan:
- URL: http://www.aiai.ed.ac.uk/project/ix/
- Problem class: HTN planning and execution/replanning support for multiple agents.
- Input format: TF (Task Formalism, see manual)
- Solving approach: Issue handling, partial-plan search space, constraint management and plan repair.
- Further info: I-X/I-Plan (2000-2012) is the successor to O-Plan and generalized the approach and terminology. It simplified the plan/task/activity constraint-based representation found in O-Plan to the more general <I-N-C-A> ontology (Issues, Nodes (activities), Constraints, Annotations).
Nonlin:
- URL:
  - Nonlin: http://www.aiai.ed.ac.uk/project/nonlin/
  - UM Nonlin: http://www.cs.umd.edu/projects/plus/Nonlin/
- Problem class: HTN planning
- Input format: TF (Task Formalism, see manual)
- Solving approach: Heuristic search through a space of partial plans.
- Further info: This early planner (1975-77 and 1982-83, Nonlin) used plans with actions represented hierarchically and partially ordered along with the maintenance of plan teleology (goal structure) to detect and find corrections for goal interactions. The second planner, UM Nonlin, is a Common Lisp (re-)implementation from 1992.
O-Plan:
- URL: http://www.aiai.ed.ac.uk/project/oplan/
- Problem class: HTN planning in a variety of practical applications
- Input format: TF (Task Formalism, see manual)
- Solving approach: Mixture of AI search, constraint management, and Operations Research numerical techniques
- Further info: This early planner (1983-1999) is quite influential and more than a simple planning system that was used on a range of domains and provided a web planning service.
PANDA-3:
- URL: panda3.hierarchical-task.net
- Problem class: HTN problems (and some variants specifically total-order HTNs)
- Input format: HDDL and some outdated XML format
- Solving approach: Various, depending on the specific solver:
  - search in the space of POCL plans (the "traditional" PANDA planning approach),
  - progression search in the space of task networks and updated state,
  - encoding into ASP,
  - encoding into SAT with different encodings/sub planners for HTNs and total-order HTNs
- Further info: Note that PANDA-3 is no longer maintained and all its planners except the POCL-based one and the encoding to ASP have been ported to its official successor Panda-Pi. Please check out the PANDA website for an explanation of all existing planners, approaches, and their history. (That webpage also positions the predecessors PANDA-1 and PANDA-2.)
PANDA-Pi:
- URL: panda.hierarchical-task.net
- Problem class: HTN problems (and some variants specifically total-order HTNs)
- Input format: HDDL
- Solving approach: Various, depending on the specific solver:
  - progression search in the space of task networks and updated state,
  - encoding into SAT with different encodings/sub planners for HTNs and total-order HTNs (chosen automatically), and
  - encoding into BDDs for total-order HTNs (only in PANDA-Pi).
- Further info: Please check out the PANDA website, which explains both the history of all these planners and provides links to the various sub software systems and earlier versions. In a very nutshell, PANDA-pi is the most recent version and still under development.
PDDL4J:
- URL: https://github.com/pellierd/pddl4j
- Problem class: HTN problems
- Input format: HDDL and and their own extension of PDDL (still called PDDL)
- Solving approach: Progression search in the space of task networks (plus updated state)
- Further info: This planner participated in the IPC 2020. You can thus download the participating planner as a convenient singularity file from the IPC 2020 webpage. Regarding the input language, note that only the ipc2020 branch supports HDDL, the others use their own extension of PDDL (which is still called PDDL).
pyHiPOP:
- URL: not published by the authors, but see further info
- Problem class: HTN problems
- Input format: HDDL
- Solving approach: Search in the space of POCL plans.
- Further info: This planner participated in the IPC 2020. You can thus download the participating planner as a convenient singularity file from the IPC 2020 webpage.
RAE and UPOM:
- URL: https://github.com/patras91/rae_release
- Problem class: Integration of Acting and Planning
- Input format: Task-oriented hierarchical operational models written in simple python code
- Solving approach: Monte Carlo rollouts over the space of hierarchical operational models
- Further info: That planner has been applied in the context of defense on Software-defined networks, and is currently in the process of being integrated with robotics applications.
SHOP:
- URL:
  - Overview website: https://www.cs.umd.edu/projects/shop/
  - Code overview: https://sourceforge.net/projects/shop/files/
  - Pyhop: https://bitbucket.org/dananau/pyhop
  - GTPyhop: https://github.com/dananau/GTPyhop
  - JSHOP1: https://github.com/mas-group/jshop2
  - SHOP2: https://github.com/calyau/shop2
  - JSHOP2: https://github.com/mas-group/jshop2
  - SHOP3: https://github.com/shop-planner/shop3, with manual: https://shop-planner.github.io
  - MCTS-JSHOP1: https://github.com/minecraft-saar/MCTS-JSHOP
- Problem class: HTN problems with domain-specific advice
- Input format: model as python program, or some of the SHOP-formats, depending on the planner
- Solving approach: Progression search in the space of task networks (plus updated state)
- Further info:
  - SHOP is one of the most influential HTN planning systems. It is normally regarded a domain-configurable approach because its search does not base on domain-independent heuristics, but instead the model contains domain-specific advice. Its standard search procedure performs depth-first search, where the priority of method application is provided in the model (though other search procedures exist as well). There exist approximately ten different SHOP versions (more than the ones listed above). Please see both the overview website as well as the code overview page.
  - The last listed planner, MCTS-JSHOP1 performs Monte Carlo Tree Search based on JSHOP1 and is thus distinct from all other SHOP versions listed.
  - All SHOP1 derivatives only support total-order HTN problems, whereas all SHOP2 and SHOP3 derivatives also support partial-order domains.
  - Please note that the code overview page hosts several of the above-linked planners on sourceforge, i.e., some planners are hosted on multiple services. Please check which one is the newest or best-fitting version.
  - Finally, note that there exist translations from HDDL into the various SHOP standards, see the IPC 2020 webpage.
SIADEX:
- URL: not published by the authors, but see further info
- Problem class: HTN problems with time
- Input format: HPDL
- Solving approach: Uninformed lifted depth-first search.
- Further info: This planner participated in the IPC 2020. You can thus download the participating planner as a convenient singularity file from the IPC 2020 webpage. Note see the IPC 2020 webpage offers a translator from HPDL to HDDL.
SIPE-2:
- URL: http://www.ai.sri.com/~sipe/
- Problem class: HTN problems
- Input format: Uses its own format (doesn't have a name)
- Solving approach: search in the space of POCL plans
- Further info: SIPE-2 is the successor of the earlier SIPE hierarchical partial-order planner developed in 1984. SIPE-2 features plan generation and execution, as well as mixed-initiative planning. There's a video describing the system.
Toad:
- URL: http://toad.hierarchical-task.net
- Problem class: totally-ordered HTN problems
- Input format: HDDL
- Solving approach: Translation into a sequence of classical planning problems.
- Further info: In contrast to the approach by Alford et al., TOAD overapproximates the solution set and thus requires a verifier to ensure that found plans are actual solutions.
Tree-REX/Lilotane:
- URL:
  - Tree-REX: https://gitlab.com/domschrei/htn-sat
  - Lilotane: https://github.com/domschrei/lilotane
- Problem class: total-order HTN problems
- Input format: HDDL
- Solving approach: encoding into SAT
- Further info: Lilotane is the successor of Tree-REX, and it participated in the IPC 2020. You can thus download the participating planner as a convenient singularity file from the IPC 2020 webpage. Note that Tree-REX only supports the (hierarchical) PDDL format by PDDL4J, and its successor Lilotane only supports HDDL.