Database Reference
In-Depth Information
{
ON(B,A) , ON(A,C)
ONTABLE(C) , CLEAR(B)
}
UNSTACK(B,A)
{ ONTABLE(B) , ON(A,C) , ONTABLE(C)
CLEAR(A) , CLEAR(B) }
UNSTACK(A,C)
STACK(B,A)
...
{ ONTABLE(A) , ONTABLE(B) , ONTABLE(C)
CLEAR(A) , CLEAR(B) , CLEAR(C) }
...
Abbildung 11.6 Suchraum bei Vorwartssuche
11.6.3
Planen mit Vorwartssuche
Bei der Vorwartssuche geht man von der Startdatenbasis aus und erzeugt durch
Operatorenanwendungen Nachfolgedatenbasen, bis man eine Datenbasis erreicht,
die die Zielbeschreibung erfullt. Der Anfangsteil eines durch dieses Vorgehen er-
zeugten Suchraums ist in Abbildung 11.6 skizziert. Wie man sich leicht klarmachen
kann, ist in realistischen Anwendungsszenarien diese Methode nicht praktikabel,
wenn man nicht starke Heuristiken anwenden kann, die die Anzahl der anwendba-
ren Operatoren einschranken.
11.6.4
Planen mit Ruckwartssuche
Wahrend bei der Vorwartssuche das zu erreichende Ziel zunachst nicht beachtet
wird, geht die Ruckwartssuche zielorientiert vor. Man nimmt sich ein noch nicht
erfulltes Teilziel vor und sucht einen Operator, der dieses Ziel erzeugt. Dieser Prozess
wird Mittel-Ziel-Analyse ( means-ends analysis )genannt.
Bezogen auf STRIPS -Operatoren mussen wir dann noch sicherstellen, dass die
Vorbedingungen des gefundenen Operators erfullt sind. Dies geschieht dadurch, dass
diese Vorbedingungen als Unterziele aufgestellt und durch wiederum denselben Pro-
zess der Mittel-Ziel-Analyse erreicht werden.
Damit haben wir bereits ein Planungsverfahren skizziert, das den wesentlichen
Kern des STRIPS -Systems bildet. Einen entsprechenden rekursiven Algorithmus,
den wir in Abbildung 11.7 skizziert haben, nennen wir daher R-STRIPS . R-STRIPS
erwartet ein Ziel G und eine Datenbasis Start . Die lokalen Variablen P und S werden
zum leeren Plan [ ] bzw. zu Start initialisiert. Die anschließende while-Schleife
bricht erst ab, wenn alle Ziele in S erreicht sind. Zur Erinnerung: Als vereinfachende
Annahme hatten wir festgelegt, dass sowohl STRIPS -Datenbasen als auch Ziele nur
durch Mengen von Grundliteralen beschrieben werden, die jeweils konjunktiv zu
Search WWH ::




Custom Search