Automatisierte Planung
Automatisierte Planung ist der Zweig der künstlichen Intelligenz, der sich mit der Berechnung von Aktionssequenzen befasst, die einen Anfangszustand der Welt in einen gewünschten Zielzustand überführen, basierend auf einer formalen Beschreibung der verfügbaren Aktionen.
Definition
Automatisierte Planung ist die Berechnung eines Plans – einer geordneten (oder teilweise geordneten) Menge von Aktionen –, der nachweislich ein Ziel aus einem Anfangszustand erreicht, basierend auf einem Modell, wie jede Aktion den Zustand der Welt verändert.
Scope
Dieser Bereich umfasst die Darstellung von Planungsproblemen (Zustände, Aktionen mit Vorbedingungen und Effekten, Ziele) und die Algorithmen, die diese lösen: klassische Planung in deterministischen, vollständig beobachtbaren Domänen, Planungsgraph- und heuristische Suchmethoden, hierarchische Aufgabennetzwerkplanung sowie die Erweiterung auf Zeit, Ressourcen und Terminplanung. Er behandelt Standardformalismen wie STRIPS und PDDL und die Komplexität der Planung. Planung unter probabilistischer Unsicherheit knüpft an das Schließen unter Unsicherheit an, und das Lernen von Aktionsmodellen oder -strategien aus Daten gehört zum Teilgebiet des maschinellen Lernens.
Sub-topics
Core questions
- Wie werden Aktionen, Zustände und Ziele kompakt genug dargestellt, um große Domänen zu beschreiben?
- Wie wird das Planungsproblem trotz eines exponentiell großen Zustandsraums effizient durchsucht?
- Wie werden zulässige und informative Heuristiken automatisch aus einer Domänenbeschreibung abgeleitet?
- Wie können Pläne hierarchisch strukturiert und Zeit- und Ressourceneinschränkungen integriert werden?
Key concepts
- Zustände, Aktionen, Ziele
- Vorbedingungen und Effekte
- STRIPS und PDDL
- Vorwärts- und Rückwärts-Zustandsraumsuche
- Planungsgraphen
- domänenunabhängige Heuristiken
- hierarchische Aufgabennetzwerke
- zeitliche Planung und Terminierung
Key theories
- STRIPS-Aktionsdarstellung
- Der STRIPS-Formalismus beschreibt Aktionen durch Vorbedingungen und Hinzufüge-/Löscheffekte über eine Menge von Propositionen, was eine kompakte, faktorisierte Darstellung bietet, die die Planung zu einer Suche durch symbolische Zustände anstatt einer Enumeration expliziter Weltzustände macht.
- Domänenunabhängige heuristische Suche für die Planung
- Moderne Planer fassen die Planung als heuristische Suche auf und leiten Heuristiken automatisch aus der Problembeschreibung ab, zum Beispiel indem sie Löscheffekte ignorieren oder kausale Strukturen nutzen, was eine starke allgemeine Leistungsfähigkeit ermöglicht.
- Planung als Hierarchie von Problemklassen
- Die Planung umfasst ein Spektrum von klassischer deterministischer Planung bis hin zu hierarchischen, zeitlichen und ressourcenbeschränkten Varianten, jede mit charakteristischen Darstellungen und Komplexität, organisiert in der Standardtheorie der automatisierten Planung.
Clinical relevance
Automatisierte Planung wird in der Robotik und autonomen Systemen, bei Raumfahrt- und Missionsoperationen, in Logistik und Lieferketten, in der Fertigung sowie bei der Generierung von Spielen und Erzählungen eingesetzt; Planer, die aus diesen Techniken abgeleitet wurden, haben reale autonome Raumfahrzeuge gesteuert und komplexe Arbeitsabläufe koordiniert.
History
Die automatisierte Planung begann um 1971 mit STRIPS für den Shakey-Roboter am SRI, wobei die Planung als Theorembeweis über Aktionsbeschreibungen formuliert wurde. Das Feld entwickelte sich über die Partial-Order-Planung, den Graphplan-Durchbruch (1995) und den Aufstieg schneller domänenunabhängiger heuristischer Suchplaner sowie den PDDL-Standard ab den späten 1990er Jahren, verfolgt durch die International Planning Competitions.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Malik Ghallab
- Dana Nau
- Paolo Traverso
- Malte Helmert
Related topics
Seminal works
- fikes1971
- ghallab2004
- helmert2006
Frequently asked questions
- Wie unterscheidet sich die automatisierte Planung von der allgemeinen Suche?
- Automatisierte Planung ist eine Form der Suche, aber sie arbeitet mit einer deklarativen, faktorisierten Beschreibung von Aktionen (Vorbedingungen und Effekte) anstatt einer undurchsichtigen Nachfolgerfunktion. Diese Struktur ermöglicht es Planern, Heuristiken automatisch abzuleiten und zu beurteilen, welche Aktionen relevant sind, was eine generische Suche nicht leisten kann.
- Was ist PDDL?
- PDDL, die Planning Domain Definition Language, ist eine Standardsprache zur Beschreibung von Planungsdomänen und -problemen – Objekten, Prädikaten, Aktionen, dem Anfangszustand und dem Ziel. Sie ermöglicht den Vergleich domänenunabhängiger Planer anhand eines gemeinsamen Benchmarks, wie bei den International Planning Competitions.