Database Reference
In-Depth Information
R-STRIPS
(
G
,
Start
)
Eingabe:
G
Ziel (Menge von Grundliteralen)
Start
Datenbasis (Menge von Grundliteralen)
Ausgabe:
P
Plan (Liste von Operatoren)
1.
P
:= [
]
% leerer Plan als Initialisierung
2.
S
:=
Start
3.
while
G
⊆
S
do
4.
g
:= ein Element aus
G
,dasnichtin
S
enthalten ist
5.
Op
:= eine Grundinstanz
(C,D,A)
einer Regel
R
,sodass
g
∈
A
6.
P
C
:=
R-STRIPS(
C
,S)
7.
S
:=
Op(P
C
(S)
)
8.
P
:=
P
+
P
C
+[
Op
]
end while
9.
return
(
P
)
Abbildung 11.7
Rekursiver
STRIPS
-Algorithmus
verknupfen sind. Daher reduziert sich der Test, ob alle Ziele aus
G
in
S
erfullt sind,
auf die Mengeninklusion
G
⊆
S
(Zeile (3.)).
In der Zeile (4.) von
R-STRIPS
findet eine Auswahl statt. Fuhrt die getroffene
Wahl von
g
nicht zum Erfolg, so muss hierher zuruckgesetzt werden, um auch die
anderen Wahlmoglichkeiten fur
g
zu berucksichtigen. Zeile (5.) stellt ebenfalls einen
Rucksetzpunkt dar, da es verschiedene Regeln
R
und fur jedes solche
R
auch ver-
schiedene Operatoren
Op
(Grundinstanzen von
R
)mit
(C, D, A)
geben kann, die
g
in der
A
-Liste haben. Da
Op
das Ziel
g
erzeugt, kann es als “Mittel fur den Zweck”
g
verwendet werden. In (6.) wird durch rekursiven Aufruf von
R-STRIPS
ein Plan
P
C
- von der augenblicklichen Datenbasis
S
ausgehend - erzeugt, der die Vorbedingun-
gen
C
von
Op
generiert. Auf
S
konnen wir dann zunachst
P
C
und anschließend
Op
anwenden (7.). Der bisher erzeugte Plan
P
wird entsprechend zunachst um
P
C
und
dann um [
Op
] erweitert (8.). Anschließend wird in der Abfrage der while-Schleife
wieder uberpruft, ob nun alle Ziele in der erreichten Datenbasis
S
gelten. Ist dies
der Fall, wird der so erzeugte Plan
P
zuruckgegeben.
Die Arbeitsweise von
R-STRIPS
wollen wir an einem Beispiel erlautern. Dazu
erweitern wir unsere Blockwelt um eine zusatzliche Operation
MOVE(x,y,z)
,die
Block
x
von Block
y
herunternimmt und auf Block
z
setzt (und damit der Sequenz
[
UNSTACK(x,y)
,
STACK(x,z)
] entspricht). Die entsprechende
STRIPS
-Regel fur
MOVE
ist:
MOVE(x,y,z)
:
C:
ON(x,y)
,
CLEAR(x)
,
CLEAR(z)
D:
ON(x,y)
,
CLEAR(z)
A:
ON(x,z)
,
CLEAR(y)
Gegeben seien Ausgangsdatenbasis
Start
und Ziel
G
wie in Abbildung 11.8
dargestellt. Wenn wir nun annehmen, dass
R-STRIPS
als erstes Teilziel
ON(A,B)
