Suchen mit Agenten

Seminar Softwareagenten

Simon Fischer

Gliederung

Motivation Suchprobleme Suchalgorithmen für Agenten Zusammenfassung/Kritik

Motivation

„Suche“ nach Informationen

Stichwort: „intelligente Suchmaschine“

Lösungen komplexe Aufgaben

Hilfe Unterstützung / Teambildung

Wegen Navigation, Orientierung

Beispiele

intelligente Suchmaschinen „Information Retrieval“ und „Content

Analysis“ mit Agenten

komplexe Aufgaben z.B. „Suche das günstigste

Urlaubsangebot für die nächsten Ferien!“

Navigationssystem incl. dynamischer

Verkehrsstauumgehung

Suchräume und Ziele

Quantifizierung von qualitativen Aspekten.

Spezielle Agenten für bestimmte Suchräume

unterschiedliche Ziele: eine Lösung! beste Lösung!

Suchprobleme

„Suche“ als Oberbegriff für eine Reihe von Problemlösungstechniken in der KI.

Aktionsreihenfolge zur Lösung des Problems vorher nicht bekannt. Anwendung von „Trial & Error“-

Techniken

Probleme/Aufgaben lassen sich klassifizieren:

Suchprobleme (2)

„Constraint Satisfaction Problems“ Urlaubsrecherche 8/n-Damen Problem Graphenfärbung

„Path-Finding Problems“ Navigationssystem n-Puzzle Labyrinth / Hindernisflächen

„Two-Player Games“ Verhandlungen Tic-Tac-Toe

Suchalgorithmen für Agenten

Eigenschaften eines Agenten Kein globales Wissen!! Begrenzte Wahrnehmung Begrenzte Ressourcen

Daher: Kooperation mit anderen Agenten Asynchroner Informationsaustausch

oder/und Schrittweises Vorgehen und lösen des

lokalen Problems

Constraint Satisfaction Problems

Definition n-Variablen: x1,x2,...,x n

Wert der Variable jeweils aus einer „Domain“: D1,D2,...,Dn (diskret, endlich)

„Constraint“: pk(xk1,....,xkj)

Ermittlung einer Wertkonstellation die alle Bedingungen erfüllt.

Problemmodellierung

Bsp.: 8-Damen Problem Je Schachbrettzeile eine Variable

(x1,...,x8) „Domain“ jeweils {1,2,...,8} – Position

in der Zeile Bedingungen:

xi xj (Keine zwei Damen in einer Spalte) und |i-j| | xi –xj | (keine Diagonalen)

Problemmodellierung (2)

„Constraint“-Graph Voraussetzung: Bedingungen immer

nur zwischen 2 Variablen („binary CSP‘s“)

Knoten: Variablen Kanten: Bedingung

Knoten mit direkter Verbindung sind „Nachbarn“

X1

{1,2}

X2

{2}

X3

{1,2}

Distributed CSP‘s

Pro Variable ein Agent Problem:

lokale Sicht: Treffen lokaler Entscheidungen ohne

globales Wissen Interdependenzen mit andern Agenten

über „Constraints“ Wichtig: Modellierung der

„Constraints“ asynchrone Kommunikation

Keine „Lost Messages“ Reihenfolge der Nachrichten bleibt erhalten

Filtering Algorithm

„Preprocessing“ evtl. nur Reduktion des Problems (wiederholte) Kommunikation der

eigenen „Domain“ an seine Nachbarn Elimination der Werte der eigenen

Domain, die in jedem Fall einen Konflikt erzeugen.

Filtering Algorithm

3-Damen Problem

x1

x2 x3

x1

x2

x3

x1

x2 x3

procedure revise(xi,xj)for all vi in Di doif there is no value vj in Dj such that vj is consistent with vi

then delete vi from Di; end if; end do;

Hyper-Resolution-Based Consistency Algorithm

Grundlagen Constraint-Modellierung über

„nogoods“ Bsp. Graphenfärbung:

Bedingung: Benachbarte Knoten nie gleichfarbig„nogoods“: {x1=red,x2=red},{x1=blue,x2=blue}

Hyper-Resolution Regel:Domain

A1 A1 ... Am

„nogoods“(A1 A11 ... ), (A2 A21 ... .), ..., (Am Am1 ...)

=>„nogood“ (A11 ... A21 ... Am1 ... )

Hyper-Resolution-Based Consistency Algorithm (2)

„nogood“ Beispiel:Bekannte„nogoods“ bei x1:

{x1=red,x2=red}

{x1=blue,x2=blue}

{x1=red,x3=red}

{x1=blue,x3=blue} Hyper-Resolution Regel:

Domainx1=red, x1=blue

„nogoods“(x1=red x2=red), (x1=blue x3=blue)

=>„nogood“ (x2=red x3=blue)

X1

{redt,blue}

X2

{red,blue}

X3

{red,blue}

Hyper-Resolution-Based Consistency Algorithm (3)

Algorithmus: Austausch neuer „nogoods“ mit Nachbarn Problem nicht lösbar, sobald „nogood“ leere

Menge Lösung, falls keine neuen „nogoods“

generierbar

Problem:Generierung von sehr vielen „nogoods“ teuer

Restriktion der max. Länge von „nogoods“ führt nur zur Gesamtproblemreduktion (vgl. Filtering Algorithm)

Asynchronous Backtracking

Agenten/Variablen werden angeordnet (z.B. x1>x2>x3...)

2 Nachrichten-Typen: Ok?-Messages „nogood“-Messages

Vorgehen Initialwerte kommunizieren (ok?) Bei Erhalt einer ok?-Message:

Wertänderung, falls inkonsistent mit höherwertigen Agenten

nicht möglich? -> „nogood“ Erzeugung Kommunikation des „nogood“ an

„niedrigsten“ Agenten aus dem „nogood“

X1

{1,2}

X2

{2}

X3

{1,2}

(ok?,(x1,1) (ok?,(x2,2)

(nogood, {(x1,1),(x2,2)})

Asynchronous Backtracking (2)

Beim Erhalt einer „nogood“-Message:

„Kontakt“ zu bisher unbekannten Agenten aufbauen (-> zukünftige Updates)

„Local view“ ergänzen und überprüfen

X1

{1,2}

X2

{2}

X3

{1,2}

(nogood, {(x1,1),(x2,2)})

Add neighbour request

local view{(x1,1)}

Asynchronous Backtracking (3)

Vorgehen wie bei OK?-Message: Falls möglich neuen Wert wählen Sonst: „Nogood“ Message

erzeugen usw...

3 Proceduren: When received (ok?...) When received (nogood...) Check local view!

Generate and send new (nogood...)

Send (ok?...)

X1

{1,2}

X2

{2}

X3

{1,2}

(nogood, {(x1,1)})

local view{(x1,1)}

(nogood, {(x1,1),(x2,2)})

Asynchronous Backtracking (4)

Zusammenfassung: Anordnung der Agenten Auswahl eines initialen Wertes Kommunikation an Nachbarn Aufbau eines „local view“ (Werte anderer Agenten) Überprüfung des eigenen Wertes mit Werten von

höherpriorisierten Agenten anhand der „Constraints“ Änderung – ansonsten Generierung eines „nogood“

(nur aktueller Zustand wird berücksichtigt) Kommunikation des „nogood“ an den

niedrigstpriorisierten Agenten aus dem „nogood“ Dadurch: sukzessive Änderungen entlang der

Priorisierung Problem

Ungünstige Entscheidung von hochpriorisierten Agenten bedingen umfangreiche Suchaktionen niedrigerer Agenten

Asynchronous Weak-Commitment Search

Verbesserung des „Asynchronous Backtracking“

Dynamische Ordnung: Zusätzlich: Ein ansteigender Prioritätswert

(initial 0) Bei gleichem Wert gilt fixe Ordnung

Reduktion der Wahrscheinlichkeit von falschen Entscheidungen

Auswahl eines neuen Werte mittels „min-conflict“-Heuristik

Asynchronous Weak-Commitment Search (2)

Erhöhung der Priorität: Nur, falls kein konsistenter Wert gefunden wird

und ein neues(!) „nogood“ generiert werden kann.

„min-conflict“-Heuristik: Auswahl des Wertes, der konsistent mit

höherpriorisierten Agenten ist und die wenigsten Konflikte mit niedrigerpriorisierten Agenten verursacht.

Probleme: Gewährleistung der Vollständigkeit wird evtl.

teuer erkauft.

Path-Finding Problems

Definition Modellierung als Graph:

Zustände = Knoten N Aktion = Kante L Startzustand als Ausgangspunkt Menge von Zielknoten als Endzustände Kantengewichte als Kosten der Aktion

bzw. Entfernung zwischen zwei Knoten Ermittlung des „kürzesten“ Weges

vom Startknoten zu einem Endknoten

Problemmodellierung

Bsp.: 8-Puzzle Jede mögliche

Anordnung als Knoten Kosten pro „Zug“ = 1

Labyrinth Gitternetz Jeder gültiger Ort ein

Knoten Kanten entsprechen

den möglichen Bewegungsrichtungen

1 4 23 5

6 7 8

14 23 5

6 7 8

1 4 23 56 7 8

1 4 23 567 8

1 4 23 56

7 8

1

1

1

1

„Path-Finding“ mit Agenten

Suche nach möglichst kurzen Wegen mit evtl. mehreren Agenten.

Konkurrenzsituationen bei „Bottlenecks“ Zielgerichtete Navigation in unbekannten

Umgebungen Klassifikation

Unidirektionale Bidirektionale Multidirektional

Problem auch hier: nur lokale Sicht

Asynchronous Dynamic Programming

Grundlagen Optimalitätsprinzip:

Ein Pfad ist genau dann optimal, wenn jeder Teilpfad auch optimal ist.

Definitionen h*(j) - Kürzester Weg von Knoten j zum Ziel k(i,j) – Kosten der Kante von i zu j f*(j) – Kürzester Weg über Knoten j zum Ziel

f*(j)=k(i,j)+h*(j) Kürzester Weg von Knoten i zum Ziel

h*(i)= minjf*(j)

Asynchronous Dynamic Programming (2)

Problem:h*(j) unbekannt

Idee: Pro Knoten ein Agent h(i) - aktuell kürzeste Entfernung

Initial: Zielknoten=0 sonst z.B. . Jeder Agent hat Zugriff auf aktuellen „h“-Wert

der Nachbarn und die Kosten der Kante Jeder Knoten berechnet dann wiederholt seinen

h-Wert als minj(k(i,j)+h(j))

Algorithmus ist nicht praxisrelevant aber Basisidee für andere Algorithmen

Learning Real-Time A* (LRTA*)

Unidirektional Ein Agent (vgl. Roboter) Reduktion auf Entscheidung über

nächsten optimalen Knoten Vorgehen:

Initiale h(j) werden geschätzt (Heuristiken)1. f(j) für jeden Nachbarknoten bestimmen2. Wert h(i) des aktuellen Knoten neu

setzen: minj(f(j))

3. Zu „vielversprechendstem“ Knoten wechseln

Real-Time A* (RTA*)

Variante von LRTA* Update des aktuellen Wertes mit

dem zweitkleinsten f-Wert der Nachbarknoten

Weiterhin Wechsel zu Nachbarn mit kleinstem f-Wert

Vorteil: RTA* lernt effizienter

Heuristiken

Anforderung an Heuristiken „Zulässigkeit“

Eine Heuristik ist zulässig (admissible) wenn sie nie den tatsächlichen Wert überschätzt! h(i)h*(i)

Heuristik statt globales Wissen: Effizienz des Algorithmus abhängig

von Optimalität der Heuristik

Moving Target Search

Generalisierung von LRTA* für bewegte Ziele Verwendung einer Matrix heuristischer

Werte - h(x,y) y als Position des Zieles. Voraussetzung: Information über

Bewegung des Zieles Unterschiedliche Update-Prozeduren

für h-Werte des aktuellen Knotens bei eigener Bewegung bzw. Bewegung des Zieles

Real-Time Bidirectional Search

Bidirektional 2 Agenten Startpositionen:

Ausgangszustand Endzustand

Ermittlung des Gesamtweges durch Treffen des anderen Agenten

Unterschiedliche Ergebnisse bei unterschiedlichen Organisationsformen:

Centralized RTBS Decoupled RTBS

Real-Time Multiagent Search

Vorteile beim Einsatz von mehreren Agenten:

Start

Ziel

Two-Player Games

Konkurrierende Agenten Grundlage

Modellierung des Spiels als Baum Vollständiger Baum wäre Grundlage für perfekte

Strategie – aber: zu komplex „Minmax“-Algorithmus

Pro Zug wird ein Teil des Baumes evaluiert Mögliche zukünftige Spielzustände werden über

Heuristik bewertet und in die nähere Zukunft propagiert.

Mögliche Aktionen des Gegenspielers werden berücksichtigt

Nächster Zug gemäß besseren Zukunftsaussichten

Two-Player Games

Optimierung: Alpha-Beta Pruning

Basiert auf Vorgehen bei der Bewertung der Teilbäume (Depth-first order)

Äste, die nur noch schlechtere Spielzustände versprechen werden erst gar nicht untersucht.

„Speed-up“ bzw. tiefere Suche möglich

Zusammenfassung/Kritik

+ Interessante Algorithmen für Agenten Distributed Constraint-Satisfaction Problems Distributed Path-Finding Problems Two-Player Games

+ evtl. Grundlage für viele Anwendungen Geeignete Modellierung als Voraussetzung

- Effizienz ist problemabhängig- Keine Aussagen bzgl. Praxistauglichkeit- Abhängigkeit von der Qualität der

Heuristik