Automatisiertes Planen und Planen, manchmal einfach als AI Planning bezeichnet, ist ein Zweig künstlicher Intelligenz, der die Umsetzung von Strategien oder Aktionssequenzen betrifft, die typischerweise von intelligenten Agenten, autonomen Robotern und unbemannten Fahrzeugen ausgeführt werden. Im Gegensatz zu klassischen Steuerungs- und Klassifizierungsproblemen sind die Lösungen komplex und müssen im mehrdimensionalen Raum entdeckt und optimiert werden. Planung ist auch mit der Entscheidungstheorie verbunden.

In bekannten Umgebungen mit verfügbaren Modellen kann die Planung offline durchgeführt werden. Lösungen können vor der Ausführung gefunden und bewertet werden. In dynamisch unbekannten Umgebungen muss die Strategie häufig online überarbeitet werden. Modelle und Richtlinien müssen angepasst werden. Lösungen greifen in der Regel auf iterative Versuchs- und Fehlerprozesse zurück, die üblicherweise in der künstlichen Intelligenz auftreten. Dazu gehören dynamische Programmierung, Verstärkungslernen und kombinatorische Optimierung. Sprachen, die zur Beschreibung von Planung und Zeitplanung verwendet werden, werden häufig Aktionssprachen genannt.

Überblick
Angesichts einer Beschreibung der möglichen Anfangszustände der Welt, einer Beschreibung der gewünschten Ziele und einer Beschreibung einer Reihe möglicher Aktionen besteht das Planungsproblem darin, einen Plan zusammenzustellen, der garantiert ist (wenn er auf einen der Anfangszustände angewendet wird). einen Zustand zu erzeugen, der die gewünschten Ziele enthält (ein solcher Zustand wird als Zielzustand bezeichnet).

Die Schwierigkeit der Planung hängt von den verwendeten vereinfachenden Annahmen ab. Abhängig von den Eigenschaften der Probleme in mehreren Dimensionen können mehrere Klassen von Planungsproblemen identifiziert werden.

Sind die Handlungen deterministisch oder nicht deterministisch? Sind für nichtdeterministische Aktionen die zugehörigen Wahrscheinlichkeiten verfügbar?
Sind die Zustandsvariablen diskret oder stetig? Wenn sie diskret sind, haben sie nur eine begrenzte Anzahl möglicher Werte?
Kann der aktuelle Zustand eindeutig beobachtet werden? Es kann vollständige Beobachtbarkeit und teilweise Beobachtbarkeit geben.
Wie viele Anfangszustände gibt es endlich oder beliebig viele?
Haben Aktionen eine Dauer?
Können mehrere Aktionen gleichzeitig ausgeführt werden oder ist jeweils nur eine Aktion möglich?
Ist das Ziel eines Plans, einen bestimmten Zielzustand zu erreichen oder eine Belohnungsfunktion zu maximieren?
Gibt es nur einen Agenten oder mehrere Agenten? Sind die Agenten kooperativ oder selbstsüchtig? Bauen alle Agenten ihre eigenen Pläne separat auf, oder werden die Pläne zentral für alle Agenten erstellt?

Das einfachste mögliche Planungsproblem, bekannt als das klassische Planungsproblem, wird bestimmt durch:

ein eindeutiger bekannter Ausgangszustand,
Dauerlose Aktionen,
deterministische Aktionen,
die jeweils nur einzeln genommen werden kann,
und ein einzelner Agent.

Da der Anfangszustand eindeutig bekannt ist und alle Handlungen deterministisch sind, kann der Zustand der Welt nach einer beliebigen Folge von Handlungen genau vorhergesagt werden, und die Frage der Beobachtbarkeit ist für die klassische Planung irrelevant.

Außerdem können Pläne als Aktionssequenzen definiert werden, da immer im Voraus bekannt ist, welche Aktionen erforderlich sind.

Bei nichtdeterministischen Aktionen oder anderen Ereignissen, die außerhalb der Kontrolle des Agenten liegen, bilden die möglichen Ausführungen eine Baumstruktur, und Pläne müssen die geeigneten Aktionen für jeden Knoten der Baumstruktur festlegen.

Diskrete Markov-Entscheidungsprozesse (MDP) sind Planungsprobleme mit:

Dauerlose Aktionen,
nichtdeterministische Aktionen mit Wahrscheinlichkeiten
volle Beobachtbarkeit,
Maximierung einer Belohnungsfunktion
und ein einzelner Agent.

Wenn vollständige Beobachtbarkeit durch partielle Beobachtbarkeit ersetzt wird, entspricht die Planung dem partiell beobachtbaren Markov-Entscheidungsprozess (POMDP).

Wenn es mehr als einen Agenten gibt, haben wir eine Planung für mehrere Agenten, die eng mit der Spieltheorie zusammenhängt.

Domänenunabhängige Planung
In der AI-Planung geben Planer normalerweise ein Domänenmodell (eine Beschreibung einer Reihe möglicher Aktionen zur Modellierung der Domäne) sowie das durch den Ausgangszustand und das Ziel festgelegte spezifische Problem ein, im Gegensatz zu denen, bei denen es keine gibt Eingabedomäne angegeben. Solche Planer werden als „domänenunabhängig“ bezeichnet, um die Tatsache hervorzuheben, dass sie Planungsprobleme aus einer Vielzahl von Domänen lösen können. Typische Beispiele für Domänen sind Blockstapelung, Logistik, Workflow-Management und Roboteraufgabenplanung. Daher kann ein einziger domänenunabhängiger Planer verwendet werden, um Planungsprobleme in all diesen verschiedenen Domänen zu lösen. Ein Routenplaner ist dagegen typisch für einen domänenspezifischen Planer.

Planen von Domänenmodellierungssprachen
Die am häufigsten verwendeten Sprachen zur Darstellung von Planungsdomänen und bestimmten Planungsproblemen, wie z. B. STRIPS und PDDL für die klassische Planung, basieren auf Statusvariablen. Jeder mögliche Zustand der Welt ist eine Zuweisung von Werten zu den Zustandsvariablen, und Aktionen bestimmen, wie sich die Werte der Zustandsvariablen ändern, wenn diese Aktion ausgeführt wird. Da eine Reihe von Zustandsvariablen einen Zustandsraum induziert, der eine Größe aufweist, die im Satz exponentiell ist, leidet die Planung ähnlich wie bei vielen anderen Berechnungsproblemen unter dem Fluch der Dimensionalität und der kombinatorischen Explosion.

Eine alternative Sprache zum Beschreiben von Planungsproblemen sind hierarchische Tasknetzwerke, in denen eine Gruppe von Aufgaben angegeben wird und jede Aufgabe entweder durch eine primitive Aktion ausgeführt oder in eine Gruppe anderer Aufgaben zerlegt werden kann. Dies beinhaltet nicht unbedingt Zustandsvariablen, obwohl in realistischeren Anwendungen Zustandsvariablen die Beschreibung von Task-Netzwerken vereinfachen.

Algorithmen für die Planung
Klassische Planung
Vorwärtsverkettungszustandsraumsuche, möglicherweise erweitert mit Heuristiken
Rückwärtsverkettungssuche, möglicherweise verbessert durch Verwendung von Statuseinschränkungen (siehe STRIPS, graphplan)
Teilauftragsplanung

Klassische Planung
Die traditionelle Planung basiert auf zwei Annahmen:

der Determinismus der Handlungen. Beispielsweise ist die Aktion „Würfel auf den Tisch legen“ deterministisch. Wenn wir es ausführen, bewegen wir uns von einem Zustand in einen anderen. Im Gegenteil, „Würfeln“ ist nicht deterministisch, da es mögliche Werte gibt. Die Aktion „Würfeln“ fällt nicht in den Rahmen der herkömmlichen Planung.
die perfekte Beobachtung. Der Agent (der Roboter, das Programm usw.) kennt den Zustand der Welt vollständig.

Bei der klassischen Planung geht es darum, nach einer Abfolge von Aktionen zu suchen (z. B. „Nehmen Sie eine Pfanne“, „Wasser einlegen“, „Nudeln legen“, „Ein Feuer anzünden“, „Greifen“, „Auslassen“) Feuer“). Der A * -Algorithmus ist ein typisches Beispiel für einen klassischen Planungsalgorithmus, der aus Gründen der Einfachheit häufig in Einführungskursen verwendet wird. Hier sind einige algorithmische Techniken, die in klassischen Planern verwendet werden:

die Vorwärtssuche in einem Zustandsraum: heuristischer Suchplanungsalgorithmus (HSP), Fast-Forward-Algorithmus (FF),
die Rückwärtssuche in einem Zustandsraum,
die suche vorher in einem raum von plänen, graphplan
Lockerung eines Planungsproblems: Berechnung eines entspannten Problems, bei dem es einfacher ist zu wissen, ob es einen Plan gibt, der zur Lösung des ursprünglichen Problems beiträgt
die Transformation einer Formel der Aussagenlogik zu einem Erfüllbarkeitsproblem.

Bylander hat 1994 gezeigt, dass die herkömmliche Planung PSPACE-vollständig ist.

Reduktion auf andere Probleme
Reduktion auf das propositionale Erfüllungsproblem (Satplan).
Reduktion auf die Modellprüfung – beide sind im Wesentlichen Probleme beim Durchqueren von Zustandsräumen, und das klassische Planungsproblem entspricht einer Unterklasse von Modellprüfungsproblemen.

Zeitplanung
Die zeitliche Planung kann mit Methoden ähnlich der klassischen Planung gelöst werden. Der Hauptunterschied besteht darin, dass es möglich ist, dass mehrere zeitlich überlappende Aktionen gleichzeitig ausgeführt werden, dass die Definition eines Zustands Informationen über die aktuelle absolute Zeit und das Ausmaß der Ausführung jeder aktiven Aktion enthalten muss. Bei der Planung mit rationaler oder Echtzeit kann der Zustandsraum im Gegensatz zu klassischer Planung oder Planung mit ganzzahliger Zeit unendlich sein. Zeitplanung ist eng mit Planungsproblemen verbunden. Zeitplanung kann auch als zeitgesteuerte Automaten verstanden werden.

Probabilistische Planung
Die probabilistische Planung kann mit iterativen Methoden wie Werterationen und Richtlinieniterationen gelöst werden, wenn der Zustandsraum ausreichend klein ist. Bei der partiellen Beobachtbarkeit wird die probabilistische Planung auf ähnliche Weise mit iterativen Methoden gelöst, jedoch unter Verwendung einer Repräsentation der für den Raum der Überzeugungen definierten Wertefunktionen anstelle von Zuständen.

Präferenzbasierte Planung
Bei der präferenzbasierten Planung besteht das Ziel nicht nur darin, einen Plan zu erstellen, sondern auch die vom Benutzer festgelegten Präferenzen zu erfüllen. Anders als bei der üblichen belohnungsbasierten Planung, die beispielsweise MDPs entspricht, haben Präferenzen nicht notwendigerweise einen genauen numerischen Wert.

Bedingte Planung
Die deterministische Planung wurde mit dem STRIPS-Planungssystem eingeführt, einem hierarchischen Planer. Aktionsnamen sind in einer Reihenfolge angeordnet und dies ist ein Plan für den Roboter. Die hierarchische Planung kann mit einem automatisch generierten Verhaltensbaum verglichen werden. Der Nachteil ist, dass ein normaler Verhaltensbaum nicht so ausdrucksstark ist wie ein Computerprogramm. Das heißt, die Notation eines Verhaltensdiagramms enthält Aktionsbefehle, jedoch keine Schleifen oder Wenn-Dann-Anweisungen. Bedingte Planung überwindet den Engpass und führt eine ausgefeilte Notation ein, die einem Kontrollfluss ähnelt, der aus anderen Programmiersprachen wie Pascal bekannt ist. Es ist der Programmsynthese sehr ähnlich, dh ein Planer generiert Quellcode, der von einem Interpreter ausgeführt werden kann.

Ein frühes Beispiel für einen bedingten Planer ist „Warplan-C“, der Mitte der 70er Jahre eingeführt wurde. Bisher wurde die Frage nicht beantwortet, worin der Unterschied zwischen einer normalen Sequenz und einem komplizierten Plan besteht, der If-Then-Anweisungen enthält. Es hat mit der Ungewissheit zur Laufzeit eines Plans zu tun. Die Idee ist, dass ein Plan auf Sensorsignale reagieren kann, die dem Planer nicht bekannt sind. Der Planer erstellt im Voraus zwei Auswahlmöglichkeiten. Wenn beispielsweise ein Objekt erkannt wurde, wird Aktion A ausgeführt. Wenn ein Objekt fehlt, wird Aktion B ausgeführt. Ein wesentlicher Vorteil der bedingten Planung ist die Möglichkeit, Teilpläne abzuwickeln. Ein Agent ist nicht gezwungen, alles vom Anfang bis zum Ende zu planen, kann das Problem jedoch in Brocken unterteilen. Dies hilft, den Zustandsraum zu reduzieren und komplexere Probleme zu lösen.

Bereitstellung von Planungssystemen
Das Hubble-Weltraumteleskop verwendet ein Kurzzeitsystem namens SPSS und ein Langzeitplanungssystem namens Spike.

Andere Arten der Planung
In der Praxis werden nur selten Annahmen klassischer Planung geprüft. Daher sind viele Erweiterungen entstanden.

Planungskonform
Wir sprechen von einer konformen Planung (konformem Zeitplan), bei der sich das System in einem unsicheren Zustand befindet, jedoch keine Beobachtung möglich ist. Der Agent glaubt dann an die reale Welt. Diese Probleme werden durch Techniken gelöst, die denen der traditionellen Planung ähneln, bei denen jedoch der Zustandsraum aufgrund der Unsicherheit hinsichtlich des aktuellen Status exponentiell ist. Eine Lösung für ein Problem der Einhaltung des Zeitplans ist eine Folge von Aktionen.

Notfallplanung
Notfallplanung (Kontingentplanung), bei der die Umgebung mit Hilfe von Sensoren beobachtbar ist, die fehlerhaft sein können. Bei einem Problem der bedingten Planung ist ein Plan nicht mehr eine Folge von Aktionen, sondern ein Entscheidungsbaum, da jede Phase des Plans durch eine Menge von Zuständen dargestellt wird, und nicht wie in der klassischen Planung ein einzelner, vollständig beobachtbarer Zustand.

Rintanen hat im Jahr 2004 gezeigt, dass durch das Hinzufügen von Verzweigungen (bedingte Planung) das Planungsproblem EXPTIME-abgeschlossen wird. Ein besonderer Fall der zusammenhängenden Planung stellen die Probleme FOND dar – für „vollständig beobachtbar und nicht deterministisch“. Wenn das Ziel in LTLf (lineare zeitliche Logik über finite trace) angegeben ist, ist das Problem immer EXPTIME-complete 16 und 2EXPTIME-complete für eine Zweckspezifikation in LDLf.

Wenn man darüber hinaus der traditionellen Planung (dh konforme Planung) Unsicherheit hinzufügt, wird sie EXPSPACE-vollständig. Wenn wir sowohl Verzweigungen als auch Unsicherheiten hinzufügen (Planung sowohl konform als auch bedingt), wird dies 2EXPTIME-vollständig.

Probabilistische Planung
Kushmerick et al. probabilistische Planung eingeführt. In ihrer Arbeit wird die Wirkung von Handlungen mit Probabilisten beschrieben. Er gibt das Beispiel der Aktion „Der Roboter nimmt einen Block“, die auf folgende Weise beschrieben wird: Wenn der Greifer des Roboters trocken ist, hält der Roboter den Block mit einer Wahrscheinlichkeit von 0,95; Wenn die Klemme nass ist, hält der Roboter den Block mit einer Wahrscheinlichkeit von 0,5.

Dies führt zu dem Problem der Generierung von Richtlinien (oder Strategien) für einen Markov-Entscheidungsprozess (MDP) oder (im allgemeinen Fall) eines partiell beobachtbaren Markov-Entscheidungsprozesses (POMDP).

Nichtlineare Planung
Die klassische Planung löst Unterziele in einer bestimmten Reihenfolge auf. Das Problem ist, dass es manchmal zum Zerstören des bereits Errichteten führt. Dieses Phänomen ist als Sussman-Anomalie bekannt.

Angenommen, ein einzelner Barfuß sollte sich in demselben Zustand befinden, in dem er seinen rechten Schuh, seinen linken Schuh, seine rechte Socke und seine linke Socke trägt. Wenn er die Ziele in der Reihenfolge der Äußerung erreichen will, wird er scheitern.

Um diese Art von Problem zu lösen, können Sie zu teilweise geordneten Plänen wechseln, in denen die Reihenfolge zwischen den Aktionen nur festgelegt wird, wenn es notwendig ist (spätestens Zusage oder Mindestbeteiligungsplanung).

Im vorherigen Beispiel sollten Sie den linken Schuh nach dem Setzen der Socke ablegen. Gleiches für das Recht. Auf der anderen Seite ist die Ausführung des Plans für die Linke unabhängig von der Ausführung für die Rechte. Der Gesamtplan ist daher teilweise geordnet.

Planer, die mit dieser Problemkategorie umgehen können, werden als Teilauftrag bezeichnet (POP, NOAH usw.).

Hierarchische Planung
Im Allgemeinen kann man bei der Planung hierarchische Informationen zu den Aktionen haben, dh eine Beschreibung, wie komplexe Aktionen zerlegt werden. Zum Beispiel kann eine komplexe Aktion wie „Kaffee servieren“ in die Abfolge von zwei komplexen Aktionen „Kaffee kochen“ und „Kaffee bringen“ unterteilt werden. So gibt es Planer wie ABSTRIPS, die neben der Beschreibung der Aktionen die hierarchische Beschreibung der Aktionen als Eingabe übernehmen. Man kann zum Beispiel mit dem Planen auf hohem Niveau beginnen und bei Bedarf im Detail nach unten gehen (wie beispielsweise ABSTRIPS). Das Ziel wird dann mit einem hierarchischen Task-Netzwerk (HTN) beschrieben.

Zeitplanung
Mit der Zeitplanung können Sie Aktionszeiten, Bedingungen zu Beginn, Ende und während der Aktion sowie Effekte zu Beginn und am Ende der Aktionen ausdrücken. PDDL 2.1 beinhaltet Zeitplanung. Die Methode TLP-GP 1 erstellt einen Graphen und löst dann zeitliche Einschränkungen mit einem SMT-Solver. Eine Rückverfolgung bei Inkonsistenz. Rintanen hat gezeigt, dass gleichzeitige Zeitplanung (mehrere Instanzen derselben parallelen Aktion sind möglich) EXPSPACE-vollständig ist. Wenn wir dagegen diese Bedingungen lockern, können wir uns auf die herkömmliche Planung reduzieren, und daher wird die zeitliche Planung mit diesen Einschränkungen PSPACE-vollständig.

Allgemeine Planung
Die allgemeine Planung besteht aus der Erstellung eines Plans, der für mehrere Startumgebungen geeignet ist.

Multiagent-Planung
Bei der Planung mehrerer Agenten wird der Abschluss einer Aufgabe durch mehrere Agenten, z. B. mehrere Roboter, untersucht. Die Erstellung des Plans und seine Ausführung wird dann häufig verteilt / dezentralisiert. Ein wichtiger Aspekt der Pläne ist die Zusammenarbeit zwischen den Agenten. Es gibt auch einen zentralisierten Scheduling-Algorithmus, der auf einer Verallgemeinerung von STRIPS auf das Multi-Agent-Framework beruht, MA-STRIPS genannt. Der Algorithmus wurde dann verteilt, wobei ein Solver-CSP zur Verwaltung der Koordination zwischen Agenten verwendet wurde. Die Autoren Nissim, Brafman und Domshlak haben experimentell bestätigt, dass ihr Algorithmus besser ist als eine zentralisierte Planung, wenn die Agenten wenig miteinander interagieren.

Eine Hauptschwierigkeit bei der Planung mehrerer Agenten ist die kombinatorische Explosion aller Aktionen, die in Bezug auf die Anzahl der Agenten exponentiell ist. Jonsson und Rovatsos bieten 2011 eine Lösung an, um diesem Problem entgegenzuwirken und die klassische Einzelagentenplanung zu reduzieren. Es gibt auch erneuerte Parallelisierungsverfahren für die Planung von zu skalierenden Algorithmen.

Epistemische Planung
Das epistemische Planungsproblem besteht darin, bei der Beschreibung der Zustände und Handlungen das Wissen der Agenten zu berücksichtigen. Typischerweise ist das Ziel eine Formel der epistemischen Modalogik, z. B. „Der Agent weiß, dass der Agent b, dass sich der Block C im Block A befindet“ und die Aktionen werden mit Modellen von Aktionen der dynamischen dynamischen Epistemie dargestellt. Das Planungsproblem ist in all seiner Allgemeinheit unentscheidbar.

Zielsetzung :

Oben (A, B) Λ oben (B, C)
Ausgangszustand :

[Oben (A, Tabelle) Λ Oben (B, Tabelle) Λ Oben (C, A) Λ Sperre (A) Λ Sperre (B) Λ Sperre (C) Λ Offenlegung (B) Λ Offenlegung (C)]
Mögliche Aktionen:

Bewegen (b, x, y)
VORAUSSETZUNGEN: Oben (b, x) Λ Ungedeckt (b) Λ Ungedeckt (y) Λ Block (b) Λ Block (y) (b Λ x) (b Λ y) Λ (x ≠ y)
ZUSÄTZLICH: oben (b, y) Λ entdeckt (x)
STORNIERUNGEN: oben (b, x) Λ entdeckt (y)
Move_tool (b, x)
VORAUSSETZUNGEN: Oben (b, x) Λ Ungedeckt (b) Λ Ungedeckt (y) Λ Block (b) Λ (b ≠ x)
ZUSÄTZLICH: oben (b, Tabelle) Λ entdeckt (x)
STORNIERUNGEN: oben (b, x)

Beispiel

Informelles Planungsbeispiel.

Ziel
habe etwas Obst und Gemüse im Kühlschrank

Ausgangszustand
[leerer Kühlschrank zu Hause in Hausschuhen]

Verfügbare Aktionen (ungeordnete Liste)
nach Hause gehen,
trage Schuhe,
Autoschlüssel nehmen,
den Laden mit dem Auto erreichen,
den Laden zu Fuß erreichen,
wieder nach Hause gehen,
Einkäufe in den Kühlschrank legen,
betritt den Laden
nimm Obst
nimm gemüse,
bezahlen.

Mögliche Lösung (geordnete Liste)
[1- Schuhe anziehen, 2- Autoschlüssel nehmen, 3- aus dem Haus gehen, 4- zum Laden mit dem Auto fahren, 5- zum Laden gehen, 6- Obst nehmen, 7- Gemüse nehmen, 8- bezahlen, 9- geht zurück zum Haus, 10- Einkäufe im Kühlschrank]

Eine andere mögliche Lösung (geordnete Liste):
[1- Schuhe tragen, 2- gehen, 3- gehen Sie zu Fuß in den Laden, 4- gehen in den Laden, 5- nehmen Sie Gemüse, 6- nehmen Sie Obst, 7- Pay, 8- gehen Sie nach Hause, kaufen Sie 9-Platz im Kühlschrank]

Schlussfolgerungen
Aus dem Beispiel können wir sehen, wie:

Die Lösungen können mehrere sein,
kann vorhanden sein, Handlungen, die zwangsläufig nach anderen ausgeführt werden müssen (ich kann den Laden nicht mit dem Auto erreichen, wenn ich vorher die Schlüssel nicht genommen habe),
Es kann reversible Aktionen geben (Obst und Gemüse nehmen),
Es ist nicht erforderlich, dass der endgültige Plan alle Aktionen enthält, wenn mehrere Aktionen oder Sequenzen austauschbarer Aktionen ausgeführt werden (das Geschäft zu Fuß oder mit dem Auto erreichen).