Transcript
Problemseminar Planen und Handlungsmodellierung
Planraum-Planen (Plan-Space Planning)
Marius Kubilius 1
Inhalt 1. Einführung 2. Suchraum von partiellen Plänen 3. Lösungs-Plan (solution plan) 4. Algorithmus für Planraum-Planen 5. Planraum- vs. Zustandsraum-Planen
2
1. Einführung Zustandsraum-Planen - Suchraum direkt durch gegeben - Knoten sind Zustände aus der Domäne - Kanten sind Transitionen oder Aktionen zwischen den Zuständen - der Plan ist die Folge von Aktionen, die dem Pfad von - Anfangszustand bis Endzustand entspricht Planraum-Planen - der Suchraum ist nicht - der Suchraum ist der Raum, wo die Knoten den partiellen Plänen entsprechen - Knoten sind Aktionen - Kanten sind Verfeinerungs-Operationen 3
2. Suchraum von partiellen Plänen Def. (unformal) generell ist der Plan eine Menge von Aktionen, die in einer Struktur (Sequenz) angeordnet sind. Der partielle Plan könnte als eine Untermenge von Aktionen aufgefasst werden, die einige Strukturteile enthalten. z.B. die Subsequenz für den Zustandsraum Planen.
4
5
6
Hinzufügen von: Aktionen - move(r1,l,l1) Ordnen von Schritten - bestimmt die Reihenfolge von Aktionen - least commitment principle Kausale Links - gibt an, dass der Effect von einer Aktion precondition für eine andere Aktion ist. - Provider-Consumer Relation Instanziieren von Variablen - bindet Variablen von Planungsoperators - least commitment principle 7
3. Lösungs-Plan
8
Planen im Planraum heisst “suchen” eines Pfades im Graph beginnend mit einem initialen partiellen Plan 0 zum Knoten der als Lösungs-Plan gilt. Partielle Pläne enthalten nur Aktionen.
9
10
11
12
13
14
4. Algorithmus für Planraum-Planen ist ein Lösungs-Plan solange, er kein Defekt enthällt; daher Hauptprinzip beim Verfeinern ist: - Finde und beseitige alle Defekte (flows)
Operationen zum Verfeinern von : - finde Defekte, d.h. Zwischenziele und Bedrohungen - entnehme einen Defekt - finde die Lösung, wie das aufzulösen ist - wähle den Auflöser (resolver) - verfeinere in Hinsicht auf den gewählten Auflöser
15
Plan-Space Planing Procedure
16
Prozeduren im Einzelnen: OpenGoals( ) - findet alle Zwischenziele in . Das sind preconditions ohne kausalen Links. Threats( ) - findet jede Aktion, die Bedrohung für kausalen Link enthält
17
Resolve( , ) - findet mögliche Lösungen für den Defekt - falls ein Zwischenziel für precondition p von einer Aktion a j ist - Falls eine Aktion a' im gibt, mit Effekt p, dann soll ein kausaler Link zugefügt werden - Eine Aktion a soll zugefügt werden die p als Effekt besitzt. pa a falls eine Bedrohung für kausalen Link i j als Aktion a k ist und a k den Effekt ¬q hat der mit p unifizierbar ist - ordne a k bevor kausalen Link - ordne a k nach dem kausalen Link - Instanziierungs Beschränkung (binding constrain), so das p und q nicht unifizierbar sind. 18
Refine( , ) verfeinert den partiellen Plan - ordering constraints - binding constraints - kausale Links - neue Aktionen
19
20
5. Planraum vs. Zustandsraum Planen - der Zustandsraum ist endlich, während der Planraum unendlich ist - Im Zustandsraum-Planen sind Folgezustände explizit, während es im Raumplan-Planen keine expliziten Zustände gibt. - der parzielle Plan trennt das Auswählen von Aktionen, die durchgeführt werden sollen und Ordnen von Aktionen im Plan. - Planstruktur und Begründungen für Plankomponenten sind explizit im Plan. - die Knoten des Suchraumes sind komplexer im Planraum als im Zustandsraum. Verfeinerungsoperationen brauchen viel mehr Rechenzeit als Operationen bei Transitionssystemen. 21
