Wumpus-Welt

Die Wumpus-Welt ist eine einfache Umgebung für wissensbasierte Software-Agenten, die häufig in der Lehre herangezogen wird, um die logische Funktionsweise von Software-Agenten zu erläutern. Die Umgebung entstammt dem Computerspiel Hunt the Wumpus.

Modellierung und Aufgabenumgebung

Beispiel einer 4*4 Felder großen Wumpus-Welt

Die Wumpus-Welt stellt eine Höhle dar und wird durch ein quadratisches Gitter modelliert. Zu jedem Zeitpunkt und für jedes Feld des Gitters ist eindeutig festgelegt, was bzw. wer sich auf diesem Feld befindet oder ob das Feld leer ist. Auf einem Feld versteckt sich der Wumpus. Auf einem anderen Feld befindet sich Gold. Die restlichen Felder haben entweder Fallgruben oder sind leer. Diese Felder werden vorher festgelegt und ändern sich nicht.

Die Aufgabe des Software-Agenten ist es in möglichst kurzer Zeit das Gold zu finden und unversehrt wieder zur Startposition zurückzukehren. Dabei geht von der Figur des Wumpus und mehreren Falltüren eine Gefahr aus. Zu Anfang hat der Agent kein Wissen darüber, was sich an welcher Stelle der Höhle befindet. Mithilfe von fünf Sensoren ist er jedoch in der Lage, seine nähere Umgebung wahrzunehmen und mithilfe dieser Wahrnehmungen durch logisches Schließen neues Wissen über die Höhle zu gewinnen. Anhand dieses Wissens trifft er die Entscheidung, wohin er sich als Nächstes bewegt, um dort erneut seine Umgebung wahrzunehmen.

Der Agent startet auf einem definierten Feld und bewegt sich in jedem Schritt auf ein angrenzendes Feld (gemeinsame Kante mit dem Feld, auf dem er sich befindet). Der Agent ist mithilfe eines Sensors in der Lage, eine Falltür wahrzunehmen, die sich auf einem angrenzenden Feld befindet (Luftzug). Er kann jedoch nicht wahrnehmen, welches der angrenzenden Felder dies ist. Mit der Wahrnehmung des Wumpus verhält es sich ebenso (Gestank). Das Gold wird erst erkannt, wenn der Agent sich direkt auf diesem Feld befindet (Glitzern). Ein vierter Sensor dient der Wahrnehmung eines Stoßes, wenn der Agent gegen eine Wand läuft. Der Agent hat außerdem genau einen Pfeil, mit dem er in eine Richtung (horizontal oder vertikal) bis zur nächsten Wand oder zum Wumpus schießen kann. Der fünfte Sensor dient der Wahrnehmung des Schreis, der ertönt, wenn der Wumpus von dem Pfeil getroffen wird, was dessen Tod bedeutet.

Eine präzise Definition für die Aufgabenumgebung des Agenten kann mit der PEAS-Beschreibung gegeben werden:

• Performance (Leistungsmaß): Jede Aktion des Agenten wird mit einer bestimmten Punktezahl bewertet. Aufheben des Golds: +1000, Betreten eines Felds mit einer Falltür oder des Wumpus-Felds, falls der Wumpus noch lebt: -1000. Benutzung des Pfeils: -10. Jede beliebige Aktion: -1.
• Environment (Umgebung): Das oben beschriebene Gitter mit Gold, Falltüren und Wumpus.
• Actuator (Akteur): Die Aktionen, die der Agent ausführen kann. Vorwärtsbewegung, Drehung um 90 Grad nach links oder rechts, Aufheben des Golds, Abschießen des Pfeils.
• Sensors (Sensoren): Die fünf oben beschriebenen Sensoren zum Wahrnehmen der Umgebung.

Beispiel

Die Zeilen und Spalten des Gitters in obiger Abbildung werden von 1 bis 4 durchnummeriert, die Zeilen werden von unten nach oben, die Spalten von links nach rechts gezählt. Jedes Feld wird mit $(x,y)$ bezeichnet, wobei $x$ die Nummer der Zeile und $y$ die Nummer der Spalte bezeichnet. Das Startfeld des Agenten ist $(1,1)$.

Auf dem Startfeld hat der Agent kein Wissen. Da er keinen Luftzug und keinen Gestank wahrnimmt, schließt er, dass die angrenzenden Felder rechts $(1,2)$ und oben $(2,1)$ sicher sind. Je nach Strategie entscheidet er sich nun für eines der beiden Felder, in diesem Beispiel geht er nach rechts. Hier nimmt er den Luftzug wahr und schließt, dass sich rechts neben oder über ihm eine Falle befindet. Die Bestimmung der genauen Position der Falle ist noch nicht möglich.

Der Agent hat nun folgendes Wissen über seine Umgebung: $(1,1),(1,2),(2,1)$: sicher. Auf $(1,3)$ oder $(2,2)$ befindet sich eine Falltür (das „oder“ ist nicht ausschließend, es kann auch auf beiden Feldern eine Falltür sein). Hingegen befindet sich weder auf $(1,3)$ noch auf $(2,2)$ der Wumpus, da er auf einem angrenzenden Feld keinen Gestank wahrgenommen hat.

In diesem Fall geht der Agent auf $(2,1)$ als einziges sicheres Feld, das er noch nicht betreten hat. Hier nimmt er Gestank wahr, woraus er folgert, dass ein Wumpus in der Nähe ist. Allerdings hat er keinen Luftzug und folgert daher, dass rechts von ihm $(2,2)$ und über ihm $(3,1)$ keine Falltür sein kann. Da er schon weiß, dass auf $(2,2)$ kein Wumpus ist, kann er dieses Feld nun als sicher identifizieren und der Agent entscheidet sich für das Betreten dieses Felds. Alternativ hätte er auch seinen Pfeil auf den Wumpus abfeuern können, da er mit dem Wissen über Feld $(2,2)$ auch sicher schließen konnte, dass der Wumpus auf $(3,1)$ sein muss. Auf $(2,2)$ nimmt er nichts wahr und kann seine Entscheidung aus den beiden sicheren Feldern $(3,2)$ (über ihm) oder $(2,3)$ (rechts neben ihm) treffen. Nach der ersten Entscheidung findet er direkt das Gold, nach der zweiten nimmt er einen Luftzug wahr und kann daher auf kein weiteres sicheres Feld folgern. Ihm bleibt das einzige sichere Feld $(3,2)$. Er geht daher wieder auf $(2,2)$ zurück und macht den sicheren Zug auf das Gold.

Literatur

• Stuart Russell, Peter Norvig: Künstliche Intelligenz Pearson Verlag, München 2004, ISBN 3-8273-7089-2

Weblinks

• Stuart Russell, Peter Norvig: Logical Agents. Chapter 7 of the textbook, Artificial Intelligence: A Modern Approach (Second Edition) (PDF-Datei; 417 kB)