Aktionen und Planen - Methoden Wissensbasierter Systeme - page 371

Selbsttestaufgabe 11.6 (Sokoban) Bei dem Spiel Sokoban sollen mit Hilfe einer
Spielfigur ( ” Lagerarbeiter“) Kisten in Zielfelder gebracht werden (vgl. Abbildung
11.11). Gekreuzte Felder sind die Zielfelder, d. h., ein Zielzustand ist erreicht, wenn
alle Kisten auf diesen Feldern stehen. Die Kisten durfen von der Figur nur geschoben
werden: Liegen die Felder 1, 2 und 3 in einer Linie neben- oder untereinander, steht
die Kiste auf Feld 2, der Arbeiter auf Feld 3 und ist Feld 1 frei, dann kann er die
Kiste auf das Feld 1 schieben, wobei er sich selbst auf Feld 2 bewegt. Der Arbeiter
kann sich auf den freien weißen Feldern senkrecht und waagerecht bewegen (er darf
auch die Zielfelder benutzen, jedoch nicht die dunklen Felder), darf aber das Feld
mit der Kiste nicht uberschreiten, ohne die Kiste zu schieben. Die in Abbildung
11.11 dargestellte Konstellation ist ein moglicher Startzustand.
1. Modellieren Sie die Bewegungen der Spielfigur (gehen, schieben) und der Kiste
(geschoben werden) mit STRIPS , und modellieren Sie die in Abbildung 11.11
dargestellte Situation. Formulieren Sie also eine Datenbasis und Zielbeschrei-
bung entsprechend der dargestellten Situation in der Abbildung und definieren
Sie entsprechende STRIPS -Operatoren.
2. Skizzieren Sie den Suchraum zur Losung des Problems bei Vorwartssuche.
3. Uberlegen Sie sich eine Sokoban-Situation mit mehreren Kisten, in der eine
lineare Zielabarbeitung (erst Kiste 1 auf ein Zielfeld bringen, dann Kiste 2) in
eine Sackgasse fuhrt (vgl. Sussman-Anomalie).
Abbildung 11.11 Sokoban-Startzustand zu Selbsttestaufgabe 11.6