Klassische Planung und STRIPS

Klassische Planung befasst sich mit dem Problem, eine Abfolge von Aktionen zu finden, um ein Ziel in einer deterministischen, vollständig beobachtbaren, statischen Umgebung zu erreichen, wobei die faktorisierte STRIPS-artige Darstellung von Aktionen durch Vorbedingungen und Effekte verwendet wird.

Definition

Klassische Planung sucht eine Abfolge deterministischer Aktionen, die einen vollständig bekannten Ausgangszustand in einen Zustand überführt, der das Ziel erfüllt, wobei jede Aktion durch die Bedingungen beschrieben wird, die für ihre Anwendung erfüllt sein müssen, und die Änderungen, die sie bewirkt.

Scope

Dieses Thema behandelt das klassische Planungsmodell und seine Annahmen (deterministische Aktionen, vollständige Beobachtbarkeit, ein einzelner Agent, atomare Zeit), die STRIPS- und ADL/PDDL-Darstellungen von Zuständen und Aktionen, die grundlegenden Lösungsmethoden der Vorwärts- (Progression) und Rückwärts- (Regression) Zustandsraumsuche und der Partial-Order-Planung sowie die rechnerische Komplexität der propositionalen Planung. Heuristische Führung und Planungsdiagramme werden im verwandten Thema behandelt, und nicht-deterministische oder probabilistische Varianten sind nicht Gegenstand dieses Themas.

Core questions

• Welche Annahmen definieren das klassische Planungsmodell, und wann sind sie angemessen?
• Wie faktorisiert die STRIPS-Darstellung einen Zustand in Propositionen und eine Aktion in Präkonditionen sowie Add-/Delete-Effekte?
• Wie unterscheiden sich Progression- und Regression-Suche als Planungsstrategien?
• Wie rechnerisch aufwendig ist klassische Planung im Allgemeinen?

Key concepts

• deterministisches, vollständig beobachtbares Modell
• STRIPS-Präkonditionen und -Effekte
• Add- und Delete-Listen
• PDDL und ADL
• Progression (Vorwärtssuche)
• Regression (Rückwärtssuche)
• Partial-Order-Planung
• Komplexität der Planexistenz

Key theories

STRIPS-Darstellung

STRIPS beschreibt die Welt als eine Menge wahrer Propositionen und jede Aktion durch eine Präkonditionsliste plus Add- und Delete-Listen, sodass die Anwendung einer Aktion einfach Propositionen hinzufügt und entfernt; dieses faktorisierte Modell ist die Grundlage nahezu aller klassischen Planer.

Progression- und Regression-Suche

Klassische Pläne können gefunden werden, indem man vom Ausgangszustand aus anwendbare Aktionen vorwärts sucht (Progression) oder vom Ziel aus rückwärts regredierte Unterziele berechnet (Regression), wobei die Partial-Order-Planung die Festlegung auf eine totale Aktionsreihenfolge lockert.

Komplexität der Planung

Die Entscheidung, ob ein propositionaler STRIPS-Plan existiert, ist im Allgemeinen PSPACE-vollständig, was formal erklärt, warum Planung schwierig ist und heuristische und strukturelle Methoden motiviert, um sie praktikabel zu machen.

Clinical relevance

Klassische Planungsdarstellungen sind die gängige Schnittstelle für die Roboteraufgabenplanung, die automatisierte Montage und Logistik sowie jede Anwendung, bei der deterministische Aktionen sequenziert werden müssen, um ein Ziel zu erreichen; PDDL-basierte klassische Planer sind die Arbeitspferde des Feldes und der International Planning Competitions.

History

STRIPS wurde um 1971 am SRI entwickelt, um den Shakey-Roboter zu steuern, und führte das Präkonditions-/Effekt-Aktionsmodell ein, das die klassische Planung definiert. Die Partial-Order-Planung reifte in den 1970er-80er Jahren, Bylander etablierte 1994 die PSPACE-Vollständigkeit der propositionalen Planung, und der PDDL-Standard vereinheitlichte später die Benchmarks des Feldes.

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

Was sind die Annahmen der klassischen Planung?

Klassische Planung geht von einem einzelnen Agenten aus, der in einer deterministischen, vollständig beobachtbaren und statischen Umgebung agiert, wobei Aktionen eine Zeiteinheit in Anspruch nehmen und der Ausgangszustand vollständig bekannt ist. Eine Lockerung dieser Annahmen, zum Beispiel die Zulassung von Unsicherheit oder Parallelität, führt zu reichhaltigeren Planungsproblemen jenseits des klassischen Modells.

Was bedeuten die STRIPS Add-Liste und Delete-Liste?

Wenn eine STRIPS-Aktion angewendet wird, werden die Propositionen in ihrer Add-Liste wahr und die in ihrer Delete-Liste falsch; alle anderen Propositionen bleiben unverändert. Diese einfache Aktualisierungsregel macht STRIPS zu einer kompakten und rechnerisch bequemen Darstellung, wie Aktionen die Welt verändern.