Planungsdomänendefinitionssprache – Wikipedia

Das Planen der Domain-Definitionssprache ((PDDL) ist ein Versuch, Planungssprachen für künstliche Intelligenz (KI) zu standardisieren. Es wurde erstmals 1998 von Drew McDermott und seinen Kollegen entwickelt (ua von STRIPS und ADL inspiriert), hauptsächlich für die Herstellung des 1998/2000 Internationaler Planungswettbewerb (IPC) möglich und entwickelte sich dann mit jedem Wettbewerb. “Die Annahme eines gemeinsamen Formalismus zur Beschreibung von Planungsbereichen fördert eine weitaus stärkere Wiederverwendung von Forschung und ermöglicht einen direkteren Vergleich von Systemen und Ansätzen und unterstützt daher schnellere Fortschritte auf diesem Gebiet. Ein gemeinsamer Formalismus ist ein Kompromiss zwischen Ausdruckskraft (in der sich Entwicklung befindet) stark getrieben von potenziellen Anwendungen) und dem Fortschritt der Grundlagenforschung (die die Entwicklung von gut verstandenen Grundlagen fördert). Die Rolle eines gemeinsamen Formalismus als Kommunikationsmedium für den Austausch erfordert eine klare Semantik. “^[1]

De facto offizielle Versionen von PDDL[edit]

PDDL1.2[edit]

Dies war die offizielle Sprache des 1. und 2 .. IPC 1998 bzw. 2000.^[2]

Es trennte das Modell des Planungsproblems in zwei Hauptteile: (1) Domainbeschreibung und (2) die verwandten Problembeschreibung. Eine solche Aufteilung des Modells ermöglicht eine intuitive Trennung der Elemente, die es sind (1) vorhanden in jedem spezifischen Problem der Problemdomäne (diese Elemente sind in der Domänenbeschreibung enthalten) und in jenen Elementen, die (2) Bestimmen Sie das spezifische Planungsproblem (diese Elemente sind in der Problembeschreibung enthalten). So können mehrere Problembeschreibungen mit derselben Domänenbeschreibung verbunden sein (so wie beispielsweise mehrere Instanzen einer Klasse in OOP (Object Oriented Programming) oder OWL (Web Ontology Language) existieren können). Somit bilden eine Domäne und eine Verbindungsproblembeschreibung das PDDL-Modell eines Planungsproblems, und schließlich ist dies das Eingang einer Planer-Software (normalerweise domänenunabhängiger AI-Planer), die darauf abzielt, das gegebene Planungsproblem über einen geeigneten Planungsalgorithmus zu lösen. Das Ausgabe des Planers wird nicht von PDDL angegeben, aber es handelt sich normalerweise um einen vollständig oder teilweise geordneten Plan (eine Folge von Aktionen, von denen einige manchmal sogar parallel ausgeführt werden können). Schauen wir uns nun den Inhalt einer PDDL1.2-Domäne und die Problembeschreibung im Allgemeinen an …
(1) Die Domainbeschreibung bestand aus a Domain-Name Definition, Definition von Anforderungen (um diese Modellelemente dem Planer zu deklarieren, den das PDDL-Modell tatsächlich verwendet), Definition von Objekttyp-Hierarchie (genau wie eine Klassenhierarchie in OOP), Definition von konstante Objekte (die in jedem Problem in der Domäne vorhanden sind), Definition von Prädikate (Vorlagen für logische Fakten) und auch die Definition von möglich Aktionen (Operator-Schemata mit Parametern, die während der Ausführung geerdet / instanziiert werden sollten). Aktionen hatten Parameter (Variablen, die mit Objekten instanziiert werden können), Voraussetzungen und Auswirkungen. Die Auswirkungen von Aktionen könnten auch sein bedingt (Wann-Effekte).
(2) Die Problembeschreibung bestand aus a Problemname Definition, die Definition des verwandten Domain-Name, die Definition aller möglichen Objekte (Atome im logischen Universum), Anfangsbedingungen (der Ausgangszustand der Planungsumgebung, eine Verbindung von wahren / falschen Tatsachen) und die Definition von Zielzustände (Ein logischer Ausdruck über Fakten, die in einem Zielzustand der Planungsumgebung wahr / falsch sein sollten). So hat PDDL1.2 schließlich die “Physik” einer deterministischen diskreten, vollständig zugänglichen Planungsumgebung mit einem einzelnen Agenten erfasst.

PDDL2.1[edit]

Dies war die offizielle Sprache der 3 .. IPC im Jahr 2002.^[3]

Es wurde eingeführt numerische Fließmittel (zB um nicht-binäre Ressourcen wie Kraftstoffstand, Zeit, Energie, Entfernung, Gewicht, … zu modellieren), Plan-Metriken (um eine quantitative Bewertung von Plänen zu ermöglichen und nicht nur eine zielgerichtete, sondern auch eine nutzungsorientierte Planung, dh Optimierung, Metrikminimierung / -maximierung) und dauerhafte / kontinuierliche Aktionen (die variable, nicht diskrete Länge, Bedingungen und Effekte haben können). Schließlich ermöglichte PDDL2.1 die Darstellung und Lösung von viel mehr realen Problemen als die Originalversion der Sprache.

PDDL2.2[edit]

Dies war die offizielle Sprache der deterministischen Spur der 4 .. IPC im Jahr 2004.^[4]

Es wurde eingeführt abgeleitete Prädikate (um die Abhängigkeit gegebener Tatsachen von anderen Tatsachen zu modellieren, z. B. wenn A von B aus erreichbar ist und B von C aus erreichbar ist, ist A von C aus erreichbar (Transitivität)) und zeitgesteuerte Anfangsliterale (um exogene Ereignisse zu modellieren, die zu einem bestimmten Zeitpunkt unabhängig von der Ausführung des Plans auftreten). Schließlich erweiterte PDDL2.2 die Sprache um einige wichtige Elemente, war jedoch keine radikale Entwicklung im Vergleich zu PDDL2.1 nach PDDL1.2.

PDDL3.0[edit]

Dies war die offizielle Sprache der deterministischen Spur der 5 .. IPC im Jahr 2006.^[5][6][7]

Es wurde eingeführt Zustands-Trajektorien-Einschränkungen (harte Einschränkungen in Form von modal-logischen Ausdrücken, die für die während der Ausführung eines Plans erzeugte Zustandsbahn gelten sollten, die eine Lösung des gegebenen Planungsproblems darstellt) und Vorlieben (weiche Einschränkungen in Form von logischen Ausdrücken, ähnlich wie harte Einschränkungen, aber ihre Zufriedenheit war nicht erforderlich, obwohl sie in die Planmetrik aufgenommen werden könnten, z. B. um die Anzahl der erfüllten Präferenzen zu maximieren oder nur die Qualität von zu messen einen Plan), um eine präferenzbasierte Planung zu ermöglichen. Schließlich aktualisierte PDDL3.0 die Ausdruckskraft der Sprache, um mit den jüngsten, wichtigen Entwicklungen in der Planung fertig zu werden.

PDDL3.1[edit]

Dies war die offizielle Sprache der deterministischen Spur der 6 .. und 7 .. IPC in 2008 bzw. 2011.^[8][9]

Es wurde eingeführt Objekt fließend (dh der Funktionsbereich kann jetzt nicht nur numerisch (ganzzahlig oder reell) sein, sondern auch ein beliebiger Objekttyp). So passte PDDL3.1 die Sprache mit einer syntaktisch scheinbar kleinen, aber semantisch recht signifikanten Änderung der Ausdruckskraft noch stärker an die modernen Erwartungen an.

Momentane Situation[edit]

Die neueste Version der Sprache ist PDDL3.1. Die BNF-Syntaxdefinition (Backus-Naur-Form) von PDDL3.1 befindet sich unter den Ressourcen des IPC-2011 Homepage oder der IPC-2014 Homepage.

Nachfolger / Varianten / Erweiterungen von PDDL[edit]

PDDL +[edit]

Diese Erweiterung von PDDL2.1 von etwa 2002 bis 2006 bietet ein flexibleres Modell für den kontinuierlichen Wandel durch den Einsatz von Autonomie Prozesse und Veranstaltungen.^[1][11]

Der Schlüssel, den diese Erweiterung bietet, ist die Möglichkeit, die Interaktion zwischen dem Verhalten des Agenten und Änderungen zu modellieren, die von der Umgebung des Agenten initiiert werden. Prozesse laufen über die Zeit und wirken sich kontinuierlich auf numerische Werte aus. Sie werden entweder durch die direkte Aktion des Agenten oder durch in der Umgebung ausgelöste Ereignisse initiiert und beendet. Diese dreiteilige Struktur wird als bezeichnet Start-Prozess-Stopp-Modell. Es wird zwischen logischen und numerischen Zuständen unterschieden: Übergänge zwischen logischen Zuständen werden als augenblicklich angenommen, während die Besetzung eines bestimmten logischen Zustands im Laufe der Zeit andauern kann. Daher dürfen in PDDL + fortlaufende Aktualisierungsausdrücke nur in Prozesseffekten auftreten. Sofortige Aktionen und Ereignisse beschränken sich auf den Ausdruck diskreter Änderungen. Dies führt die zuvor erwähnte dreiteilige Modellierung von Perioden kontinuierlichen Wandels ein: (1) Eine Aktion oder ein Ereignis beginnt eine Periode kontinuierlicher Änderung einer numerischen Variablen, die mittels eines Prozesses ausgedrückt wird. (2) der Prozess realisiert die kontinuierliche Änderung der numerischen Variablen; (3) Eine Aktion oder ein Ereignis stoppt schließlich die Ausführung des Prozesses und beendet seine Auswirkung auf die numerische Variable. Kommentar: Die Ziele des Plans können erreicht werden, bevor ein aktiver Prozess gestoppt wird.

NDDL[edit]

NDDL ((N.ew D.omain D.Efinition L.Sprache) ist die Antwort der NASA auf PDDL aus der Zeit um 2002.^[12][13]

Seine Darstellung unterscheidet sich von PDDL in mehreren Punkten: 1) es verwendet a Variablen- / Wertdarstellung (Zeitpläne / Aktivitäten) eher als eine Satz- / Logik erster Ordnung, und 2) es gibt kein Konzept von Zuständen oder Handlungen, nur von Intervalle (Aktivitäten) und Einschränkungen zwischen diesen Aktivitäten. In dieser Hinsicht ähneln Modelle in NDDL eher Schemata für SAT-Codierungen von Planungsproblemen als PDDL-Modelle. Aufgrund der erwähnten Unterschiede kann die Planung und Ausführung von Plänen (z. B. während kritischer Weltraummissionen) bei Verwendung von NDDL robuster sein, aber die Entsprechung zu anderen Standarddarstellungen von Planungsproblemen als PDDL ist möglicherweise viel weniger intuitiv als bei PDDL.

MAPL[edit]

MAPL ((M.ulti-EINMann P.lanning L.Sprache, ausgesprochen “Ahorn”) ist eine Erweiterung von PDDL2.1 aus der Zeit um 2003.^[14]

Es ist eine ziemlich ernsthafte Modifikation der Originalsprache. Es wird vorgestellt nicht aussagekräftige Zustandsvariablen (was n-ary sein kann: wahr, falsch, unbekannt oder irgendetwas anderes). Es wird ein zeitliches Modell eingeführt, das mit gegeben ist Modaloperatoren (vorher, nachher usw.). In PDDL3.0 wurde jedoch ein gründlicheres zeitliches Modell angegeben, das auch mit der ursprünglichen PDDL-Syntax kompatibel ist (und nur eine optionale Ergänzung darstellt). MAPL stellt auch vor Aktionen, deren Dauer zur Laufzeit festgelegt wird und explizite Plansynchronisation Dies wird durch sprachaktbasierte Kommunikation zwischen Agenten realisiert. Diese Annahme kann künstlich sein, da Agenten, die gleichzeitige Pläne ausführen, nicht unbedingt kommunizieren sollten, um in einer Umgebung mit mehreren Agenten funktionieren zu können. Schließlich stellt MAPL vor Ereignisse (endogen und exogen) um die Parallelität von Aktionen zu handhaben. Somit werden Ereignisse explizit Teil von Plänen und werden Agenten von a zugewiesen Steuerfunktion, was auch Teil des Plans ist.

OPT[edit]

OPT ((Öntologie mit P.olymorph T.ypes) war eine tiefgreifende Erweiterung von PDDL2.1 durch Drew McDermott zwischen 2003 und 2005 (mit einigen Ähnlichkeiten zu PDDL +).^[15]

Es war ein Versuch, eine Allzwecknotation zum Erstellen zu erstellen Ontologien, definiert als formalisierte konzeptionelle Rahmenbedingungen für Planungsbereiche, über die Planungsanwendungen begründen sollen. Die Syntax basierte auf PDDL, aber es gab noch viel mehr ausgefeiltes Typensystem, wodurch Benutzer Konstrukte höherer Ordnung wie explizite verwenden konnten λ-Ausdrücke Ermöglichen einer effizienten Typinferenz (dh nicht nur Domänenobjekte hatten Typen (Level 0 Typen), aber auch die oben definierten Funktionen / Fließgewichte hatten Typen in Form von willkürlichen Abbildungen (Level 1 Typen), die generisch sein könnten, so dass ihre Parameter (die Domäne und der Bereich der generischen Zuordnung) mit Variablen definiert werden könnten, die einen noch höheren Typ haben könnten (Level 2 Typ) ganz zu schweigen davon, dass die Zuordnungen beliebig sein könnten, dh die Domäne oder der Bereich einer Funktion (z. B. Prädikat, numerisch fließend) könnte ein beliebiger Typ der Stufe 0/1/2 sein. Zum Beispiel könnten Funktionen von beliebigen Funktionen auf beliebige Funktionen abgebildet werden …). OPT sollte grundsätzlich (fast) aufwärtskompatibel mit PDDL2.1 sein. Die Notation für Prozesse und dauerhafte Aktionen wurde hauptsächlich von PDDL + und PDDL2.1 ausgeliehen, aber darüber hinaus bot OPT viele andere bedeutende Erweiterungen (z Datenstrukturen, nicht-boolesche Flüssigkeiten, Rückgabewerte für Aktionen, Links zwischen Aktionen, hierarchische Aktionserweiterung, Hierarchie der Domänendefinitionen, die Verwendung von Namespaces zur Kompatibilität mit dem Semantic Web).

PPDDL[edit]

PPDDL ((P.robabilistisch PDDL) 1.0 war die offizielle Sprache der probabilistischen Spur der 4 .. und 5 .. IPC in 2004 bzw. 2006.^[16]

Es erweiterte PDDL2.1 mit probabilistische Effekte (diskrete, allgemeine Wahrscheinlichkeitsverteilungen über mögliche Auswirkungen einer Aktion), Belohnungsflüssigkeiten (zum Erhöhen oder Verringern der Gesamtbelohnung eines Plans in Bezug auf die Auswirkungen der Aktionen), Zielbelohnungen (für die Belohnung eines Zustandsverlaufs, der mindestens einen Zielzustand enthält) und Ziel erreicht fließend (was wahr war, wenn die Zustandsbahn mindestens einen Zielzustand enthielt). Letztendlich ermöglichten diese Änderungen PPDDL1.0 die Realisierung der Markov Decision Process (MDP) -Planung, bei der möglicherweise Unsicherheiten bei den Zustandsübergängen bestehen, die Umgebung jedoch für den Planer / Agenten vollständig beobachtbar ist.

APPL[edit]

APPL ((EINbstract P.lan P.Wiedergutmachung L.anguage) ist eine neuere Variante von NDDL aus dem Jahr 2006, die abstrakter ist als die meisten vorhandenen Planungssprachen wie PDDL oder NDDL.^[17]

Ziel dieser Sprache war es, die formale Analyse und Spezifikation von Planungsproblemen zu vereinfachen, die für sicherheitskritische Anwendungen wie Energieverwaltung oder automatisiertes Rendezvous in zukünftigen bemannten Raumfahrzeugen vorgesehen sind. APPL verwendete die gleichen Konzepte wie NDDL mit dem Erweiterung der Aktionenund auch einige andere Konzepte, aber dennoch ist seine Ausdruckskraft viel geringer als die von PDDL (in der Hoffnung, robust und formal überprüfbar zu bleiben).

RDDL[edit]

RDDL ((R.elational D.ynamischer Einfluss D.iagram L.Sprache) war die offizielle Sprache der Unsicherheitsspur der 7 .. IPC im Jahr 2011.^[18]

Konzeptionell basiert es auf PPDDL1.0 und PDDL3.0, aber praktisch ist es sowohl syntaktisch als auch semantisch eine völlig andere Sprache. Die Einführung von teilweise Beobachtbarkeit ist eine der wichtigsten Änderungen in RDDL im Vergleich zu PPDDL1.0. Es ermöglicht eine effiziente Beschreibung von Markov-Entscheidungsprozessen (MDPs) und teilweise beobachtbaren Markov-Entscheidungsprozessen (POMDPs), indem alles (Zustandsflüsse, Beobachtungen, Aktionen, …) mit Variablen dargestellt wird. Auf diese Weise weicht RDDL erheblich von PDDL ab. Grounded RDDL entspricht Dynamic Bayesian Networks (DBNs) ähnlich wie PPDDL1.0, aber RDDL ist aussagekräftiger als PPDDL1.0.

MA-PDDL[edit]

MA-PDDL ((M.ulti EINMann PDDL) ist eine minimalistische, modulare Erweiterung von PDDL3.1, die 2012 eingeführt wurde (dh eine neue :multi-agent Anforderung), die erlaubt Planung von und für mehrere Agenten.^[19] Der Zusatz ist mit allen Funktionen von PDDL3.1 kompatibel und behebt die meisten Probleme von MAPL. Es fügt die Möglichkeit hinzu, zwischen dem Möglichen zu unterscheiden verschiedene Aktionen von verschiedenen Agenten (dh verschiedene Fähigkeiten). Ähnlich unterschiedliche Wirkstoffe können haben verschiedene Ziele und / oder Metriken. Die Voraussetzungen für Aktionen können sich jetzt direkt auf gleichzeitige Aktionen (z. B. die Aktionen anderer Agenten) und damit beziehen Aktionen mit interagierenden Effekten kann allgemein und flexibel dargestellt werden (z. B. wird angenommen, dass mindestens 2 Agenten erforderlich sind, um a auszuführen lift Aktion, um einen schweren Tisch in die Luft zu heben, oder der Tisch würde auf dem Boden bleiben (dies ist ein Beispiel für konstruktive Synergie, aber destruktive Synergie kann auch in MA-PDDL leicht dargestellt werden). Darüber hinaus ist als syntaktischer Zucker ein einfacher Mechanismus für die Vererbung und Polymorphismus von Aktionen, Zielen und Metriken wurde auch in MA-PDDL eingeführt (vorausgesetzt :typing wird deklariert). Da PDDL3.1 davon ausgeht, dass die Umgebung deterministisch und vollständig beobachtbar ist, gilt dies auch für MA-PDDL, dh jeder Agent kann zu jedem Zeitpunkt auf den Wert jedes fließenden Zustands zugreifen und jede zuvor ausgeführte Aktion jedes Agenten beobachten Die gleichzeitigen Aktionen von Agenten bestimmen eindeutig den nächsten Zustand der Umgebung. Dies wurde später durch die Hinzufügung von Teilbeobachtbarkeits- und Wahrscheinlichkeitseffekten verbessert (wiederum in Form von zwei neuen modularen Anforderungen, :partial-observability und :probabilistic-effectsLetztere sind von PPDDL1.0 inspiriert und beide sind mit allen vorherigen Funktionen der Sprache kompatibel, einschließlich :multi-agent).^[20]

Beispiel[edit]

Dies ist die Domänendefinition einer STRIPS-Instanz für die automatisierte Planung eines Roboters mit zwei Greifarmen.^[21]

(define (domain gripper-strips)
  (:predicates (room ?r) (ball ?b) (gripper ?g) (at-robby ?r)
               (at ?b ?r) (free ?g) (carry ?o ?g))
  (:action move
   :parameters (?from ?to)
   :precondition (and (room ?from)
                      (room ?to)
                      (at-robby ?from))
   :effect (and (at-robby ?to)
                (not (at-robby ?from))))
  (:action pick
   :parameters (?obj ?room ?gripper)
   :precondition (and (ball ?obj)
                      (room ?room)
                      (gripper ?gripper)
                      (at ?obj ?room)
                      (at-robby ?room)
                      (free ?gripper))
   :effect (and (carry ?obj ?gripper)
                (not (at ?obj ?room))
                (not (free ?gripper))))
  (:action drop
   :parameters (?obj ?room ?gripper)
   :precondition (and (ball ?obj)
                      (room ?room)
                      (gripper ?gripper)
                      (carry ?obj ?gripper)
                      (at-robby ?room))
   :effect (and (at ?obj ?room)
                (free ?gripper)
                (not (carry ?obj ?gripper)))))

Und dies ist die Problemdefinition, die die vorherige Domänendefinition mit einer konkreten Umgebung mit zwei Räumen und zwei Bällen instanziiert.

(define (problem strips-gripper2)
    (:domain gripper-strips)
    (:objects rooma roomb ball1 ball2 left right)
    (:init (room rooma)
           (room roomb)
           (ball ball1)
           (ball ball2)
           (gripper left)
           (gripper right)
           (at-robby rooma)
           (free left)
           (free right)
           (at ball1 rooma)
           (at ball2 rooma))
    (:goal (at ball1 roomb)))

Verweise[edit]