Matthias Bernauer - Freiburg im Breisgau
      Start > Skript-Sammlung > Kuenstliche Intelligenz > Problemtypen >>







Problemtypen

Problemtypen

  • SingleState-Probleme
    Agent weis immer, in welchen Zustand er sich befindet (complete action and worldstate knowlege), z.B. weis Staubsauger in welcher Zelle er sich befindet und ob diese sauber ist

  • Multi-State-Probleme
    ohne diese Kenntnis betrachtet der Agent die Menge aller möglichen Zustände = Believes
    anfangs bspw. alle acht Zustände.

  • Kontingenzprobleme
    es ist nicht möglich eine vollst. Aktionssequenz zu generieren, da Informationen über Zwischenzustände fehlen (Definitionslücken, wenn unvorhergesehenes passiert)

  • Explorationsprobleme
    Zustände und Wirkung der eigenen Handlungen sind nicht bekannt. muss der Agent erst herausfinden




Staubsauger als SingleState-Problem

Die Lösung ist die Reduktion darauf, den kürzesten Pfad von Anfangszuständen zu Endzu-ständen zu suchen
Wandle Abbildung daher in Such-Baum um.

Ziel erreicht mit 3 Aktionen:
saugen, move, saugen
wenn die Umwelt vollst. beobachtbar



Staubsauger als MultiState-Problem

Da die Aktionen deterministisch sind, reduzieren die einzelnen Aktionen die Menge der mögl. Zustände, in denen sich der Agent nun befinden kann.
z.B. Aktion left --> Agent nun auf alle Fälle im linken Feld (wenn er schon dort war, tut sich nichts)


Ziel erreicht mit 4 Aktionen:
move, saugen, move, saugen
wenn die Umwelt nicht vollst. beobachtbar



Komponenten der Problemformulierung

  • Startzustand

  • State space (Zustandsraum): alle mögl. Konfigurationen

  • mögliche Aktionen (Nachwirkefunktion F: Believe-->Believe wenn unbeobachtbar, sonst
    f: State --> State)

  • Zieltest: wurde der Zielzustand erreicht?

  • Pfad: Aktionssequenz, die den Agenten von einen in den anderen Zustand überführt

  • Pfadkosten: Summe der einzelnen Kosten: Funktion, die den einzelnen Aktionen Kosten zuordnet. Darstellung durch Kostenfunktion G

  • Lösung: Pfad vom Anfangs- in den Zielzustand

  • Suchkosten: Kosten für Zeit und Speicherplatz (wichtiger), um Lösung zu finden

  • Gesamtkosten: Suchkosten + Pfadkosten


Beispiel: 8er Puzzle

  • Zustand: Beschreibung wo sich die 8 Elemente und (aus Effizienzgründen) Leerstelle befinden

  • Startzustand: Anfangskonfiguration

  • Aktion: Tausch eines der vier Element, die das Blank umgeben, mit dem Blank, d.h bewege Blank r, l, up, down

  • Zieltest: matched die aktuelle Konfiguration mit dem Endzustand

  • Pfadkosten: Jeder Schritt eine Einheit


Beispiel: 8Queens-Problem

acht-Dame-Problem: Können Damen so positioniert werden, dass sie sich nicht schlagen dürfen?

  • Zustände: 0bis8 Damen werden irgendwie verteilt.

  • Anfangszustand: keine Dame ist positioniert (Brett leer)

  • Nachfolgerfunktion: postitioniere Dame auf ein leeres Feld

  • Zieltest: kann keine Dame eine andere schlagen?

  • Pfadkosten=0, da immer nach 8 Aktionen fertig --> Suchkosten irrelevant.


  • Naive Problemformulierung:
    positioniere Damen beliebig und zähle alle Möglichkeiten auf (brute force):
    64*63*62*...*57 = 10^14 Zustände

  • bessere Formulierung:
    Zustände: zwei Damen dürfen nicht in der gleichen Spalte/Zeile/Diagonale stehen
    Nachfolgerfunktion: positioniere Dame in der am weitest links stehende Spalte in einem
    Feld, das nicht attakiert wird
    --> Reduzierung auf 2057 States



Beispiel zur Problemloesung

Missionare und Kannibalen Beispiel:

Jeweils 3 Missionare und 3 Kannibalen auf gegenüberliegenden Uferseiten wollen die Seite wechsel. Der Transfer soll sich gestaltet sein, so dass an einer Seite nie mehr Kanibalen als Missionare sind. In das Boot passen maximal zwei Leute.

  • Zustand: Tripel (x,y,z) mit 0<=x,y,z<=3,
    entspricht der aktuellen Zahl von Missionare, Kanibalen, Boote am Ufer1

  • Startzustand: (3,3,1), d.h. 3 Kanibalen, 3 Missionare und ein Boot am Ufer1

  • Zielzustand: (0,0,0)

  • illegale Zustände, bspw. (0,0,1) nicht erreichbar, da das boot nicht alleine zurück kann

  • Pfadkosten: 1 pro überquerung

  • Nachfolgerfkt: Boot überbringt entw. 1 oder 2 Missionare/Kannibalen oder gemischt

  • Lösung: (3,3,1), (2,2,0), (3,2,1), (3,0,0), (3,1,1), (1,1,0), (2,2,1), (0,2,0), (0,3,1), (0,1,0)
    (0,2,1), (0,0,0)


Allgemeine Suche

Generiere vom Startzustand beginnend alle Zustände sukzessive --> Suchbaum

(c) führt zurück in den Startzustand
--> unerwünscht



Google MSN Suche
<< Start | Studium | Poolmgr | Tanzen | GPG | Impressum >>
Matthias Bernauer