Kapitel 5 - Planen
Nennen sie die vier grundlegenden Repräsentationen eines suchorientierten
Problemlösers!
Repräsentation von Aktionen
Aktionen werden dargestellt durch Programme. Sie erzeugen Beschreibungen der
Folgezustände.
Repräsentation von Zuständen
Gegeben ist ein vollständiger Anfangszustand. Da Aktionen vollständige
Zustandsbeschreibungen erzeugen sind alle Zustände vollständig. Ein Zustand ist
meistens eine einfache Datenstruktur.
Repräsentation von Zielen
Die einzige verfügbare Information über Ziel ist das
Zielprädikat und heuristische Funktion. Die
Informationen werden auf die Zustände angewandt, um deren
Wünschbarkeit zu bestimmen.
Repräsentation von Plänen
Eine Lösung ist eine Folge von Aktionen. Eine Suche
betrachtet nur zusammenhängende ununterbrochene Folgen von Aktionen, die beim
Anfangszustand beginnen.
Beschreiben Sie die drei Schlüsselideen, die dem Planen zu Grunde liegen!
"Öffne" die Repräsentation der Zustände, Ziele und Aktionen
- durch Verwendung geeigneter Repräsentationsformen, wie z.B. die Logik erster
Ordnung
- Zustände und Ziele sind darin Sätze
- Aktionen sind logische Beschreibungen von Vorbedingungen und Wirkungen
- So werden Zustände und Aktionen miteinander verbunden
Der Planer kann stets Aktionen zum Plan hinzufügen
- Nicht nur am Anfang, auch mitten in der Planung
- Somit müssen Planung und Ausführung nicht streng getrennt werden
- Durch Verschieben von nicht notwendigen Aktionen nach "hinten" wird dadurch
der Verzweigungsfaktor stark reduziert
Meist herrscht Unabhängigkeit von Teilmengen einer Welt
- Deshalb kann oft ein Ziel aus Konjunktion mehrerer unabhängiger Teilziele
formuliert werden
- Divide-and-Conquer dafür prädestiniert
Beschreiben sie Zustände, Ziele und Aktionen in der STRIPS-Sprache?
Zustände
Sind Konjunktionen funktionsfreier Grundliterale, bestehend aus Prädikaten
angewandt auf Konstanten. Zustandsbeschreibungen müssen nicht vollständig sein, da
in einer unzugänglichen Welt der Zustand so gut wie nie vollständig ist.
Ziele
Ziele sind Konjunktionen funktionsfreier Literale (Variablen zugelassen).
Aktionen
- Aktionsbeschreibung (Beschreibung dessen was Agent an Umgebung ausgibt, um zu
handeln)
- Vorbedingung (Konjunktion vom Atomen, die spezifiziert was vor Ausführung
gelten muss)
- Wirkung (Konjunktion von Literalen, die beschreibt, wie sich Situation nach
Aktion verändert)
- OP(Action(GeheZu(dorthin), Precond(An(hier) and Pfad(hier, dort),
Effect(An(dort) and not an (hier))
- Beim Planen sind nur Aktionen enthalten und KEINE Zustände
Was macht ein Situationsraum-Planer?
Er betrachtet Zustände. Ein Situationsraum-Planer ist ein
Algorithmus, der im Raum der Situationen oder Zustände einen Pfad von einem
Anfangs- zu einem Zielzustand durch Anwendung von der verfügbaren Operationen
bestimmt. Dabei gibt es Vorwärts- und Rückwärtsplaner.
Rückswärtsplaner
- Zustände im Allgemeinen nur partiell bestimmt
- Information reicht aber aus, um auf Vorhängerzustände zu schließen
- Nachteil der Rückwärtsplanung ist die Konjunktion der Literale, von denen
jedes ein zu erfüllendes Teilziel darstellt
Was verstehen Sie unter einem Planraum?
Ein Planraum betrachtet nicht die Zustände, sondern die
Aktionen. Ein Planraum ist eine Menge partieller Pläne mit den
dazugehörigen Operationen, die solche Pläne in ebensolche überführen können.
Bei Erstellung eines Plans für ein Problem beginnt man mit einem einfachen
unvollständigen Plan und modifiziert diesen mit den Operatoren solange, bis er
vollständig ist.
Solche Operatoren sind Hinzufügen eines Schrittes, das
Ordnen von Schritten und das Instanziieren von
Variablen.
- Verfeinerungsoperatoren, beschränken die Menge der vollständigen Pläne durch
Bedingungen (Constraints)
- Alle restlichen Operatoren sind Modifikationsoperatoren
Kausale Kanten im Planraum beschreiben den
Zweck von Schritten in einem Plan.
Was sind kausale Kanten?
Sie Beschreiben den Zweck von Schritten in einem Plan, d.h. welche
Vorbedingungen für einen Situationswechsel gelten müssen. Ein Planungsalgorithmus
schützt kausale Kanten, so dass zwischen zwei Aktionen die durch eine kausale Kante
verbunden sind, keine Aktion eingeschoben werden kann, welche die Vorbedingung
aufheben würde.
Muß eine Aktion eingefügt werden, kann der Planungsalgorithmus sie entweder vor der
kausalen Kante (Demotion) oder nach ihr
(Promotion) einfügen.
Planen mit partiell instanziierten Operatoren
Wie kann man mögliche Bedrohungen kausaler Kanten entdecken und behandeln?
Eine Vorbedingung c stellt eine mögliche Bedrohung einer
Vorbedingung c' dar, wenn es einen Unifikator gibt, so dass
UNIFY( c ) = ! UNIFY( c' )
ist. Es gibt drei Wege mögliche Bedrohungen zu behandeln:
Auflösung sofort mit einem Gleichheitsconstraint
Alle möglichen Bedrohungen werden sofort aufgelöst. Dabei wird eine Variable
mit einem Wert so vorbelegt, dass ein Widerspruch zu einer anderen Vorbedingung
nicht entstehen kann (Gleichheitsconstraint).
Auflösung sofort mit einem Ungleichheitsconstraint
Wie oben, nur dass eine bestimmte Belegung von Variablen
ausgeschlossen wird, aber alle anderen erlaubt werden. Ist nur
schwer zu implementieren.
Auflösung später
Alle Bedrohungen werden solange ignoriert, bis sie notwendige Bedrohungen
werden, d.h. ein expliziter Widerspruch vorliegt. Dann wird durch
Demotion oder Promotion aufgelöst. Vorteil ist,
dass schwache Festlegungen getroffen werden können. Nachteil ist, dass es schwer zu
entscheiden ist, ob ein Plan auch eine Lösung darstellt.
|
|
|
Merkblatt