PANDA-Planungssystem

Das PANDA-Planungssystem erlaubt es, verschiedene Arten von Planungsproblemen zu lösen. Der Planungsalgorithmus für all diese Probleme ist ein hybrider Planungsansatz, der hierarchisches Planen mit kausalem Schließen verbindet. PANDA kann Planungsprobleme der folgenden Art lösen:

  • klassische, z.B. in PDDL spezifizierte, und Partial-Order Causal-Link-Planungsprobleme (POCL-Planungsprobleme),
  • Hierarchical-Task-Network-Probleme (HTN-Planungsprobleme)  und
  • hybride Planungsprobleme.

Wir sind gerade dabei, das Planungssystem als Open-Source-Projekt zur Verfügung zu stellen. Sobald es soweit ist, geben wir dies hier bekannt.

Literaturempfehlungen betreffend des PANDA-Planungssystems:

From Abstract Crisis to Concrete Relief (A Preliminary Report on Combining State Abstraction and HTN Planning) von Biundo und Schattenberg (ECP 2001) enthält:

  • Eine Formalisierung hybrider Planungsprobleme basierend auf Prädikatenlogik
  • Eine Formalisierung (basierend auf Prädikatenlogik) der Legalität von Dekompositionsmethoden: Wann ist eine Methode eine korrekte Implementierung eines abstrakten Tasks?

Hybrid Planning Heuristics Based on Task Decomposition Graphs von Bercher et al. (SoCS 2014) enthält:

  • Wie sehen hybride Planungsmodelle und -probleme aus?
  • Was sind die Lösungskriterien für hybride Planungsprobleme?
  • Planungsalgorithmus: wie funktioniert die Suche?
  • Die Heuristik MME, welche speziell für hybrides Planen entwickelt wurde und die Anzahl der Modifikationen zu einem Ziel schätzt - basierend auf dem Task-Dekompositions-Graphen, d.h. die Hierarchie hinter abstrakten Aktionen wird berücksichtigt.

More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks von Bercher et al. (ECAI 2016) enthält:

  • Komplexitätsbetrachtungen für hybrides Planen: Wie schwierig ist es, hybride Planungsprobleme zu lösen? Wie schwierig ist es, festzustellen, ob eine potentielle Lösung tatsächlich eine Lösung ist?
  • Ein Überblick über weitere Formalisierungen von hybridem Planen: Ansätze aus der Literatur, die ebenfalls hierarchisches Planen mit POCL-Planen fusioniert haben.
  • Ein Überblick über Legalitätskriterien aus der Literatur: Wann ist eine Methode eine korrekte Implementierung eines abstrakten Tasks?

An Admissible HTN Planning Heuristic von Bercher et al. (IJCAI 2017) enthält:

  • Eine zulässige (kostensensitive) Heuristik für hierarchisches und hybrides Planen. Sie erlaubt damit das Finden optimaler Pläne. Diese Heuristik berücksichtigt auf dieselbe Art und Weise wie die MME-Heuristik (siehe oben) die Hierarchie hinter abstrakten Aktionen.