Database Reference
In-Depth Information
(
STRIPS
assumption
) behandelt, die der Operatordefinition und -ausfuhrung impli-
zit zugrunde liegt:
Alle Elemente einer
STRIPS
-Datenbasis, die nicht in der Nachbedingung
eines Operators aufgefuhrt sind, bleiben bei der Anwendung des Opera-
tors unverandert.
Die Reprasentation von Operatoren und die Beschreibung ihrer Effekte unter
Berucksichtigung der
STRIPS
-Annahme kann man als den Hauptbeitrag von
STRIPS
zum Planungsbereich bezeichnen. Allerdings lasst sich die
STRIPS
-Annahme nicht
in der Pradikatenlogik 1. Stufe ausdrucken. Lange Zeit war sogar die Semantik
von
STRIPS
-Operatoren lediglich durch heuristische Suchverfahren wie
R-STRIPS
definiert; die ersten Ansatze fur eine logische Semantik von
STRIPS
sind in [138]
und [177, 178] zu finden.
Selbsttestaufgabe 11.5 (Turme von Hanoi)
Es sei n eine beliebige, aber fest
gewahlte Zahl ≥ 3. Es gibt n Scheiben D
1
,...,D
n
mit jeweils unterschiedlichem
Durchmesser: D
1
ist kleiner als D
2
, D
2
ist kleiner als D
3
,...,D
n−1
ist kleiner als
D
n
. Die Scheiben haben in der Mitte ein Loch, so dass sie auf einem Stab gestapelt
werden konnen. Es gibt drei solche Stabe, die mit A, B und C bezeichnet werden.
In der Ausgangssituation (hier fur n = 4) befinden sich alle Scheiben der Große
nach sortiert auf dem ersten Stab A,wobeidiegroßte Scheibe zuunterst liegt:
A
B
C
Ziel ist es, eine Folge von Zugen durchzufuhren, so dass schließlich alle Scheiben auf
dem Stab C sind. Dabei sind folgende Bedingungen zu beachten:
•
Bei jedem Zug wird die oberste Scheibe von einem Stab entfernt und als neue
oberste Scheibe auf einen anderen Stab gelegt.
Zu keinem Zeitpunkt darf eine großere Scheibe auf einer kleineren liegen.
Beschreiben Sie dieses Planungsproblem mit einem
STRIPS
-Ansatz:
1. Bestimmen Sie Pradikate zum Aufbau einer geeigneten
STRIPS
-Datenbasis.
2. Geben Sie die initiale
STRIPS
-Datenbasis sowie die Zielbeschreibung unter Ver-
wendung der gewahlten Pradikate an.
3. Definieren Sie einen oder mehrere
STRIPS
-Operatoren, die jeweils einen einzel-
nen Spielzug realisieren.
4. Es sei nun n = 3, d.h. es gibt drei Scheiben D
1
,D
2
,D
3
. Wenden Sie den
R-STRIPS
-Algorithmus auf die dazugehorige initiale
STRIPS
-Datenbasis und die
entsprechende Zielbeschreibung an. Welches Ergebnis erhalten Sie?
•
