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







Suchfunktionen

  • uninformierte Suche: hat keine Information darüber, wie weit man noch vom Ziel entfernt ist.

  • Informierte / heuristische Suche hat eine Funktion die angibt, wie weit man vom Ziel entfernt ist.


Beispiele für Realweltanwendungen

  • Route Planning, Shortest Path Problem
    Simple in principle (polynomial problem). Complications arise when path costs are unknown or vary dynamically (e.g. Routeplanning in Canada)

  • Traveling Salesperson Problem (TSP)
    A common prototype for NP-complete problems

  • VLSI Layout
    Another NP-complete problem

  • Robot Navigation (with a high degree of freedom)
    Difficulty increases quickly with the level of freedom. Further possible complications: errors of perception, unknown environments

  • Assembly Sequencing
    Planning of the assembly of complex objects (by robots)
    Konstruktion von Objekten mit Teilobjekten.

  • Sheduling, z.B. Stundenpläne, Raumbelegungen


Implementierung von Suchbäumen (mit Knoten)

  • Zustand (aktueller Knoten)

  • Vorgänger (Parent-Node)

  • Aktion (Operator, der den Knoten generiert)

  • Tiefe (Schritte entlang des Pfades vom Anfangszustand beginnend)

  • PfadKosten (Anfangszustand aktueller Knoten)


Operationen

  • make_queue(Elements)

  • empty(queue)

  • first(queue)

  • remove_first(queue)

  • insert(element, queue)

  • insert_all(elements, queue)


Beispiel (s.l.):

Node repräsentiert den aktuellen Zustand. Node hat einen VorgängerZustand (parent) und zwei mögliche Nachfolgezustände (entw. die 4 oder 8 mit dem Blank tauschen)

Aktion=right wurde ausgeführt um den aktuellen Zustand zu generieren.




  • Fringe := Kandidatenliste (Warteschlange/Queue), z.B. (3,3,1) wurde expandiert und man erhielt (3,2,0), (2,2,0), ... als neue Kandidatenliste

  • return failiur wenn es keine Lösung gibt, d.h. wenn es keine Kandidaten mehr gibt und noch keine Lösung gefunden wurde

  • Zum Finden einer Lösung wird jeweils der erste Kandidat mittels goal-test überprüft

  • Ist der gestestete Knoten keine Lösung, so wird er Expandiert und seine Nachfolger in die Kandidatenliste übernommen

  • Für das Expandieren, wird für jede Aktion angewandt auf den als Parameter mitgegebenen Zustand/Knoten neue Knoten generiert. Pfadkosten und Tiefe werden ebenfalls angepasst

  • Beim Expandieren wird also noch nicht getestet, ob der Nachfolger den Zielzustand bereits erfüllt. Der goaltest findet nur in der Hauptfunktion statt.


Es ergeben sich verschiedene Suchverfahren, je nachdem wie man die Insert-All- sowie die Remove-First-Routine implementiert (z.B. Fifo, ... --> ergibt Breiten- oder Tiefensuche)



Kriterien der Suchfunktionen

  • Vollständigkeit: exisitiert eine Lösung wird sie auch gefunden

  • Zeitkomplexität: Wieviel Zeit nimmt die Suche in Anspruch

  • Speicherkomplexität: Wieviel Speicher ist notw. für die (erfolgreiche) Suche
    (wichtiger, da oft nicht ausreichend in der KI)

  • Optimalität: Algorithmus ist optimal, wenn eine optimale Lösung exisitiert und diese stets gefunden wird


Suchstrategien

  • uninformierte (blinde) Suche.
    Keine Ahnung, wie weit man vom Ziel entfernt ist oder in welcher Richtung man suchen muss, d.h. keine Information über Länge des Pfades oder Pfadkosten

  • Breiten(first)suche, Tiefen(first)suche, uniform cost search

  • limitierte Tiefensuche und Iterative Tiefensuche

  • Bidirektionale Suche: ausgehend von Start- und Zielzustand wird in beide Richtungen gesucht.

  • Informierte (heuristische Suche)


Breitensuche

Bei der fringe wird die FIFO-Methode = FIFO-QUEUE() angewandt

z.B. wird Startzustand a in (b,c) expandiert. Da b zuerst erzeugt wurde wird nun b in (d,e) expandiert. Das älteste Element ist nun b, welches als nächstes expandiert wird, usw.

  • --> ebenenweises vorgehen

  • Suche ist vollständig

  • Suche findet immer zuerst den shallowest Zielzustand

  • Die Lösung ist optimal, wenn die Pfandkosten eine nicht-fallende Funktion ist,
    z.B. wenn jede Aktion identische und nicht-negative Kosten hat.

  • Die Suchkosten sind stets sehr hoch. Sei b der maximale BranchingFaktor (maximale Anzahl von Kinder/Nachfolger) und d die Tiefe der Lösung. Dann ist die max. Anzahl von Knoten, die generiert/ durch Expandierung erzeugt werden = b + b² + bÂł + ... bd
    + b(d+1)-b. (b(d+1) da man evtl. fast die nächste Ebene vollst. generiert, ehe man feststellt, dass der letzte Knoten der Ebene die Lösung ist.


Uniforme Kosten Suchen

modifiziere die Breitensuche so, dass immer der Knoten mit den niedrigsten Kosten g(n) als nächstes expandiert wird, anstatt sich wie bisher an der Tiefe zu orientiern.

S Startzustand, G Zielzustand

  • findet immer die billigste (optimale) Lösung

  • Voraussetzung: nur positive Kosten, so dass
    g(nachfolger(n)) >= g(n) für alle n


Tiefensuche

  • verwende Lifo-Methode für die fringe.

  • Hat man einen Graph statt Baum (z.B. vernetzter Verkehrsweg mit Zyklus), zirkuliert die Tiefensuche und liefert auch nicht immer die optimale Lösung

  • Tiefensuche nicht vollständig und nicht optimal,
    da bspw. erst Lsg. Auf Level10 statt 5 gefunden wird.


  • Daher wird eine cut-off-ebene (Tiefen limitierte Suche) angegeben, wo die Tiefensuche stoppt. Die max. Pfadlänge sollte stets < n-1 Knoten sein.


Iterative Tiefensuche


kombiniert die Vorteile aus Breiten- und Tiefensuche: Optimal und vollständig, wie die Breitensuche, benötigt jedoch weniger Speicherplatz. Die Funktion gibt eine Sequenz von Lösungen zurück.


funktion Iterative-Deepening-Search(problem)

FOR (depth=0 to ) {
IF (Depth-Limited-Search(problem, depth) erfolgreich) THEN { return result; }

}

return failur


Nachteil: gleiche Knoten werden auf
verschiedenen Levels mehrmals
generiert/expandiert/analysiert

--> Redundanz

Dafür findet man optimale Lösungen
mit geringerer Tiefe

Die Anzahl der Expandierungen ist geringer
als bei der Breitensuche

IDS: Level(d) + Level(d-1) + ... = bd + 2bd-1 + 3bd-2 + ... + (d-1)b2 + db  O(bd)
Speicherkomplexität: O(bd), d.h. linear zum BranchingFaktor (=Konstante)

BFS: BreitenFirstSuche = b + b² + bÂł + ... bd + b(d+1)-b  O(bd+1)


z.B. b=10, d=5

IDS: 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450

BFS: 10 + 100 + 1,000 + 10,000 + 100,000 + 999,990 = 1,111,100


Bidirektionale Suchen


Suche vom Initialzustand ausgehend (meist mit Breitensuche) vorwärts, sowie vom Zielzustand ausgehend rückwärts. Sofern die Suche symmetrisch verlaufen, muss somit nur 2mal bis zur halben Tiefe gesucht werden, d.h die Komplexität wird von O(bd) auf O(2bd/2) = O(bd/2) reduziert.

  • Allerdings ist die Rückwärtssuche nicht immer möglich, da Vorgänger evtl. nicht ermittelbar sind

  • Bei einer Menge von Ziel- oder auch Startzuständen ist dieses Verfahren nicht mögl.

  • Die überprüfung, ob ein neuer Knoten bereits im anderen Suchbaum enthalten ist, muss effizient möglich sein, z.B. Hashfunktion

  • Welche Suchmethode soll jeweils angewandt werden?


b BranchingFaktor (Anzahl der Nachfolger) 1 b ist endlich

d Tiefe der Lösung 2 Schritt kostet mehr als c

m maximale Tiefe des Baumes 3 Aktionskosten alle gleich

l Limit der Tiefensuche 4 beide Richtungen mit BFS

C Kosten der optimalen Lösung

c minimale Kosten einer Aktion


Breiten-Suche

Uniform-Kosten-suche

Tiefen-Suche

Tiefen-limitierte Suche

Iterative Tiefen-suche

Bidirektio-nale Suche

Vollständigkeit

Ja1

Ja1,2

Nein

Nein

Ja1

Ja1,4

Zeitkomplexität

O(bd+1)

O(bC/c)

O(bm)

O(bl)

O(bd)

O(bd/2)

Speicherkomplexität

O(bd+1)

O(bC/c)

O(bm)

O(bl)

O(bd)

O(bd/2)

Optimal

Ja3

Ja

Nein

Nein

Ja

Ja3,4

Tiefensuche ist entweder vollständig oder optimal


Wiederholende Zustände

führt zu exponentieller overhead

verwende Graphen- statt Baumsuche:

  • Erweitere Baumsuche um eine Liste
    bereits besucher Knoten (closed-list)

  • Ignoriere neu expandierte Knoten, die bereits in der closed-liste sind

  • Closed-list kann mit Hasfkt. impl. weden

  • Benötigt viel Speicherplatz

  • Kann zu suboptimalen Lösungen führen, wenn der optimale Weg erst im zweiten Anlauf gefunden werden würde, der Knoten jedoch schon in der closed-list aufgef. Ist


Informed Search Methods (Heuristics, Local Search Methods,Genetic Algorithms)


Best-First Search
Suchverfahren unterscheiden sich bei der Bestimmung des zu expandierenden Nachfolgerknotens

  • Uninformed Search:
    Rigides Verfahren, das nicht weiß, wie gut ein Knoten ist

  • Informed Search:
    Qualität des gegebenen Knoten bekannt in Form einer Evaluierungs-Funktion h,
    die jedem Knoten einen Wert zuweiset.

  • Best-First Search:
    Suchverfahren, dass den Knoten mit “bestem” (kleinstem) h-Wert expandiert


Allgemeiner Algorithmus

function Best-First-Search(problem, Evaluierungsfunktion)

{

Queueing-Funktion <-- ordnet die Knoten gem. der Evaluierungsfunktion

return General-Search(problem, Queueing-Funktion)

}


Wenn die Evaluierungsfunktion perfekt ist, benötigt man keine Suche!


Greedy Search

Eine Möglichkeit den Wert eines Knotens zu beurteilen, ist die Entfernung zum Ziel zu schätzen: h(n) = estimated distance von Knoten n zum Ziel

Voraussetzunh ist, dass h(n) = 0 wenn n das Ziel ist


Die Best-First-Search mit dieser Funktion wird greedy best-first search genannt

z.B. route-finding: h = Luftlinie zweier Orte



  1. Arad: h=366

  2. Arad != Ziel

  3. Arrad expandieren

  4. mit h sortierte Kandidatenliste: (Sibiu, Timisoara, Zerind)

  5. Sibiu != Zieltest

  6. Entferne Sibiu aus fringe-Liste und expandiere Sibiu
    (wo kommt man von Sibiu ausgehend überall hin, und welchen h Werte besitzt der Ort)

Probleme der Greedy-Suche

  • Findet suboptimale Lösungen, z.B. Arad, Sibiu, Rimnicu, Pitesti, Bucharest

  • Verfahren kann sich verlaufen, z.B. Iasi nach Fagaras endet bereits bei Neamt,Iasi,N...

  • unvollständig, wenn wir nicht Duplikate ermitteln


Die Evaluierungsfunktion wird in der GreedySuche auch heuristische Funktion oder Heuristik genannt.

In der Künstl. Intelligenz hat Heuristik (Problemlösungs-Verfahren) zwei Bedeutungen:

    • Heuristiken sind schnell in bestimmten Situationen jedoch unvollständig

    • Heuristiken sind Methoden, die die Suche fokusieren (in die richtige Richtung), ohne zur Unvollständig zu führen

    • Heuristiken sind immer problembezogen (individuell entwickelt) und sollen das System immer in die richtige Richtung lenken


A*: Minimalisierung der gesamten, geschätzten Pfadkosten


A* kombiniert die die GreedySuche mit dem Uniformen-Kostensuchverfahren

g(n) = tatsächliche Kosten vom Startzustand zum Zustand n

h(n) = geschätzte Kosten von n zum nähesten Zielzustand

f(n) = g(n) + h(n)= geschätzte Kosten der billigsten Lösung über n

h*(n) = tatsächliche Kosten des optimalen Pfads von n zum nähesten Ziel


h ist zulässig, wenn für alle n gilt: h(n) h*(n), d.h. h muss eine Unterschätzung sein.

A* ist vollständig und optimal




Optimalität von A*

Satz: Die erste gefundene Lösung der Baumsuche hat minimale Pfadkosten

Beweis: Es gäbe einen Zielknoten G mit optimalen Pfadkosten C*, doch A* findet zuerst

einen anderen Knoten G2 mit g(G2)>C*, insb. F(G2)>C*



Alle Kosten müssen strikt positiv sein und der BranchingFaktor darf nicht unendlich sein.


Werden Graphen statt Bäume durchsucht, gibt es zwei Möglichkeiten A* anzuwenden.

  • Vertausche teuren mit billigeren Pfad, beim wiederholten Besuch eines Knotens

  • stelle sicher, das der zuerst besuchte Pfad der optimale ist:
    Dazu Monotonie&Konsistenz: Eine Heuristik ist konsistent, wenn für alle Knoten n und deren Nachfolger succ(n)=n' folgende Dreiecksungleichung gilt:
    h(n)  h(n') + c(n,a,n') = geschätzte Kosten vom Nachfolger zum nächsten Ziel + tats. Kosten a für den übergang von n nach n'

  • Jede konsistente Heuristik ist zulässig: ...

  • A* ist für die Graphensuche optimal, wenn die Heuristik konsistent ist

  • Ist h konsistent, können die Werte von f entlang des Pfades nicht abnehmen (Monot.)
    f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') >= g(n) + h(n) = f(n)

  • Hat man keine konsistente Heuristik, kann man das Verfahren dennoch anpassen,
    indem man das maximum beider Werte max{8,9} für den falschen Wert 8 nimmt.


Vollständigkeit

Falls eine Lösung exisitiert, findet A* diese, sofern (1) jeder Knoten eine endliche Anzahl von Nachfolger hat (das heißt BranchingFaktor darf nicht Unendlich sein) und (2) eine positive Konstante d exisitiert, so dass jede Operation mindestens Kosten d hat.
--> endliche Anzahl von Knoten n mit f(n)<=f*, d.h. es ex. dann ein f(n) <= opt. Lösung


Konturen von A*

Innerhalb des Suchraumes wachsen Konturen, in denen alle Knoten für die gegebenen F-Werte expandiert werden.


Zuerst wird innerhalb der ersten Kontur gesucht. Nach der Expansion


Komplexität

Das gewöhnliche Wachstum ist exponential da der Fehler proportional zu den Pfadkosten ist. Modifiziere daher um suboptimale Lösungen zu finden und erlaube nicht-zulässige Heuristiken.
In den Fällen, wo der Fehler zwischen den tats. minimalen Kosten und den heuristischen minimalen Kosten |h*(n)-h(n)| <= O(log(h*(n)) ist, wird nur eine sub-exponentielle Anzahl von Knoten expandiert. Sonst gilt eben die exponentiale worst-case-Komplexität.

Daher sucht man manchmal auch nur nach guten und nicht unbedingt den besten Lösungen.


änderung von A* um die Speicherkomplexität zu verbessern:

IDA* = Iterative TiefenA*Suche. Dabei wird nicht wie bei der limitierten Tiefensuche, die Tiefe stets erhöht, sondern der Suchradius anhand der Konturen f festgelegt.

dabei erhöht man die conturwerte z.b. schrittweise um 20 wobei innerhalb der kontur die knoten mit geringeren f-werten (=g+h) liegen.


Function IDA*(problem) returns a solution sequence

static: f-limit, the current f-Costs limit
root, a node

root := makenode(inital_state(problem))

f-limit = f-cost(root)

loop {

solution, f-limit = DFS-Konturen(root, f-limit)

if solution is non-null then return solution
if f-limit = unendlich then return failiure; end

}


Funktion DFS-Konturen(node, f-limit) returns a solution sequence and a new f-Cost limit

static: next-f, the f-Cost limit for the next contour, initally unendlich

if f-cost(node) > f-limit then return null, f-cost(node)

if goal-test(problem)(state(node)) then return node, f-limit

for each node s in successors(node) do

solution, new-f = DFS-Konturen(s, f-limit)

if solution is non-null then return solution, f-limit

next-f = min(next-f, new-f); end;

return null, next-f









IDA* und RBFS verbrauchen eigentlich zu wenig Speicherplatz, da sie nur ein Pfad betr.



Wie entwirft man nun Heurisiken?

Vereinfache das Problem indem man Einschränkungen weglässt und Relaxionen bildet,
z.B. durch Luftliniendistanz, Kollisionen bei Navigation ignorieren, negative Effekte ignorieren. 8-puzzle:

h1 = anzahl falscher positionen

h2 = manhatten distanz


Wie wählt man die beste aus einer Menge von Heuristiken? -> Konzept der Dominanz

Gilt für alle Knoten n dass Heuristik h2(n)>=h1(n) dann dominiert h2 die Heuristik h1 und eignet sich besser für die Suche.

Hat man zwei Heuristiken die einander nicht dominieren, kann man daraus eine dritte bauen: h(n)=max(h1(n), h2(n)). h dominiert dann h1 und h2




Lokale Suchmethoden

Oft ist es nicht möglich den gesamten Suchraum systematisch zu erforschen, da dieser zu groß ist.Daher gibt es lokale Suchmethoden, die zwar weder Vollständigkeit oder Optimalität garantieren, jedoch praktisch anwendbar sind. Das globale Optimum ist durch eine objektive Funktion gegeben (Qualitätsmaß für die Höhe des Bergs). Beginne mit einer zufällig gewählten Konfiguration und verbessere dich schrittweise (Hill-Climbing)

--> unvollständig, jedoch in sehr großen Räumen anwendbar.

Hat der Nachfolgerzustand einen schlechteren Wert, dann behalte den aktuellen bei, ansonsten wähle den Nachfolger.






wie gesagt, ist dieses Verfahren nicht vollständig und kann evtl. nur zum
lokalen statt globalen
Maximum führen.


Genauso weiß man nicht ob links oder rechts wenn man sich auf einem plateau befindet.


Der Wert 17 zeigt die Anzahl der Möglichkeiten, die Dame auf diesem Feld zu schlagen. Bewege die Dame immer auf das Feld mit dem geringsten Wert. Lokale Maxima können auftreten.


Probleme der lokalen Suchmethode:

1. lokale Maxima -> suboptimale Lösungen

2. Plateaus --> zufällige Entscheidung notwendig

3. Ridges:

Lösungen:

  • mehrmaliger random restart und wähle anschließend das beste lokale maximum

  • inject noice (rauschen): gehe nicht deterministisch in die beste richtung sondern mit einer gewissen wahrscheinlichkeit. gehe mit geringer wahrscheinlichkeit in die falsche Richtung -> random walks

  • Tabu-search: Wende die letzten n Operatoren nicht erneut an: muss empirisch ausprobiert werden.


Simulated Annealing


Genetic Algorithms

Imitiert die Evolution (Natur). Idea: Similar to evolution, we search for solutions by “cross-over” (Zwei parents produzieren einen Nachfolger mit geerbten Eigenschaften), “mutation” (Zufallseinflüsse), and “selection” (ein node ändert seinen Zustand) successful solutions.

Ingredients:

• Coding of a solution into a string of symbols or bit-string

• fitness-Funktion (ähnlich zur Evaluierungsfunktion) to judge the fitness of configurations

• A population of configurations

Beispiel: 8-queens-Problem als eine Verkettung von 8 Zahlen.

Fitness is judged by the number of non-attacks. The

population consists of a set of arrangements of queens.



Die Besten haben die größte WSK selektiert zu werden

Eine Zufallsposition wird in die Konfiguration mit aufgenommen


while(fitness-Funktion sich nicht mehr verbessert)


(a) es gibt 8^8 Populationen, denen einen Wert durch die fitness-Funktion (b) zugeordnet wird. Auf Grund dieser wird die WSK für deren Selektion (c) bestimmt. Die selektierten Elemente werden gekreuzt (d) und mutieren anschließend (e)


Mögliche Versuche:

  • Reactive: Berechne die Bewegung des Motors, Kommandos basieren auf der aktuellen Beobachtung und Zielposition. Versuche gerade aus zum Ziel vorwärts zu bewegen und umfahre Hindernisse. Kann in lokalen Optimas steckenbleiben (suboptimal)

  • Deliberative: Generiere/Plane einen fast optimalen Pfad zum Ziel


Vereinfachende Annahmen

  • kontinuirliche oder millimetergenaue Navigation nicht möglich. Teile Raum auf -> Diskretisierung.

  • Die Bewegung anderer Agenten ist bekannt oder irrelevant

  • ändert sich die Umgebung (Zustand) muss kontinuirlich neu geplant werden (replaning), d.h. der Pfad neu berechnet werden.


Suche im 5D-Raum

  • Postition des Agenten (x,y) = location

  • Richtung/Sicht des Agenten = orientation 

  • Geschwindigkeit w

  • Beschleunigung v

Durchsuche diesen Raum mittels A* um den schnellsten Weg zur Zielkonfiguration zu finden. Da die Suche zu speicherintensiv ist, finden weitere Vereinfachungen statt:

  • loaction nur in 2D

  • suche den kürzesten Pfad, ignoriere die orientation

  • alle objekte sind kreise

  • reduziere den agenten als punkt und vergrößere die anderen objekte mit diesem unterschied.





Durchsuche den Visibility-Graph und verwende die Luftliniendistanz als Heuristik

--> beschränkter Such/Zustandsraum

--> Optimale Lösung des Sichtbarkeitsgraphen ist nicht zwangsläufig die optimale Lösung des ursprünglichen Problems.

--> Kreise fixierd, weil die Bewegung der anderen Agenten zur Vereinfachung ignoriert

--> kürzeste Weg ist weder der sicherste noch der schnellste.


  • Heuristiken werden benutz, um die Suche in die richtige Richtung zu steuern
    --> Vollständigkeit, Optimalität

  • Es gibt viele Variantionen von A*

  • Alernativen: Lokale und genetic Suchmethoden

  • Es gibt meist keine fertigen Lösungen, sondern basiert meist auf Versuchen und Verbessern



5. Constraint Satisfaction Probleme


In den bisherigen Suchproblemen hatten die Zustände keine innere Struktur. Bei den CPS haben die Zustände innere Strukturen/Variablen mit Werten. Der Zieltest prüft, ob alle Variablen ihren gültigen Zustand erreicht haben.



Oftmals lassen sich Hyper-Graphen in binäre umwandeln

Später werden auch Baumstrukturen untersucht


Variationen:

  • endliche Werte d, z.B. 3 Farben --> d^n Möglichkeiten, z.B. 3^n Färbungsmöglichkeiten

  • unendliche domain
    - reel oder ganzzahlig (int)
    - lineare constraints
    lösbar in P (polynomiel)
    - nicht-lineare consists
    nicht lösbar oder NP

Anwendungen: FloorPlaning, Scheduling, Timetabling, Spreadsheets

Backtracking-Suche (Form der Tiefensuche, da den Variablen ebenenweise Werte zugeordnet werden, bis auf einer Ebene ein Konflikt entsteht und man backtracken muss)


assigned = Zuweisung für Variablen


Verbesserte Effizienz:

  • Variablenordnung: Welche Variablen soll zuerst ausgewählt werden?


    • 1ste Heuristik: most constraint first
      Die eingeschränkteste Variable ist diejenige, der noch am wenigsten verbleibende Werte aus ihrer Domain zur Verfügung stehen
      --> Reduzierung des Branchingfaktors

    • 2te Heuristik: most constraining variable first
      Wähle die Variable, die am meisten Bedingungen mit anderen Variablen eingeht
      z.B. färbe zuerst SA (oben blau) ein, da diese mit 5 Nachbarländern Bedingungen eingeht, danach evtl. NT (oben grün), da dieses 2 Bedingungen einginge, ...

  • Wertordnung: Welcher Wert soll zuerst probiert werden?

    • Gegebene Variable: Wähle den am wenigsten eingeschränkten Wert. --> Wertzuweisung soll gefunden werden, die allen Bedinungen genügt.

    • Forward-checking: Bei der Wertzuweisung zu einer Variablen, haben andere Variablen evtl. ungültige Werte, die entfernt werden.
      WA=rot -> NT kann nicht rot werden. Wurden für eine Variable alle Werte entfernt, ist der Wertebereich leer und wir können die Suche stoppen.
      --> Speedup zum normalen Backtracking

    • Forward-Checking propagiert zwar Informationen von zugewiesenen Variablen auf noch nicht zugewiesene Variablen, jedoch nicht von unassigned zu unassigned:
      siehe Beispiel rechts, wo in der dritten Zeile
      kein Informationsaustausch zwischen NT und SA (beide unzulässigerweise blau) stattfindet -> Forward-checking unvollst.
      --> Kantenkonsistenz

    • Kantenkonsistenz mittels gerichtetem KonsistenzGraph. Ein ungerichteter Graph lässt sich durch Ersatz in jeweil zwei gerichtete Kanten umwandeln.
      Eine gerichtete Kante X->Y ist konsistent, wenn es für jeden Wert von X einen Wert von Y existiert, so dass (x,y) die Bedingung erfüllt ist.
      z.B. ist der Zustand in der dritten Zeile nicht kantenkonsist, da SA->NT nicht konsistent ist.
      Kantenkonsistenz entdeckt Fehler früher. Versuche Kantenkonsistenz mittels Backtracking herbeizuführen, z.B. entferne blau aus SA in der dritten Zeile.
      Kann als preprocessing (Vorbereitung) verwendet werden.
      --> als Algorithmus AC3


    • Komplexität von AC3 in O(dÂłn²), mit n Knoten und d als max. Wertebereich
      AC3 findet nicht alle Inkosistenzen, da dies NP-Hart ist.

  • Versuche Fehler so früh wie möglich zu entdecken

  • Versuche die Problemstruktur zu erforschen, z.B. ist die kleine Insel unabhängiger Subgraph, d.h. CSP hat unabhängige Teilkomponenten. Löse diese Teile unabhängig voneinander und füge sie zu einer Gesamtlösung zusammen --> reduziert den Suchraum extrem
    Ist der Graph ein Baum, vereinfacht sich das Problem zu O(nd²), denn allg. benötigen CSP O(n^d) im worst case. Idee: Bestimme einen Knoten als Wurzel und ordne die restlichen Knoten entsprechend an. Prüfe auf inkonsistente Kanten von den Blättern ausgehend zur Wurzel.

Bem.: alle dies ist nicht problemspezifisch


  • über den Knoten stehen die möglichen, anwendbaren Farben angeschrieben

  • Wende die Kantenkonsistenz an für (Xi,Xk) mit Xi ist parent von Xk.

  • Nun kann mit der Wertzuweisung begonnen werden. zufällige Initialbelegung, hier: rot für E

  • Der Algorithmus ist linear.

  • Ist (D,F) kantenkonsistent? Ja, den für R gibt es B und G, für G gibt es R und B

  • Ist (D,E) kantenkonsistent? Nein, denn für R gibt es keinen zulässigen Wert. Streiche daher das R in D.

  • (B,D) ist nicht konsistent; streiche daher G

  • (A,B): streiche R

  • Go forward: Wähle nun aus den verbleibenden Möglichkeiten eine Belegung aus

  • (D,F): G muss aus F entfernt werden



Bei Strukturen, die kein aber fast ein Baum sind, gibt es 2 Möglichkeiten

  • Conditioning: Initialisiere eine Variable mit einem Wert und update die umgebenden Variablen gem. den Bedingungen (unsystematisch: welcher Wert, welche Variable?)

  • Cutset Conditioning: Suche eine Anzahl von Variablen und überprüfe die Auswirkung.
    Das Finden einer minimalen Anzahl von Knoten, um einen Baum zu bekommen, (minimal Cut Set) ist NP-hart

  • Tree Decomposition
    Teile die Struktur in Subprobleme auf, die eine Baumstruktur darstellt, löse sie unabhängig und füge die Lösungen am Schluss zusammen.
    Folgende Eigenschaften müssen erfüllt sein:

    • Jede Variable des urspr. Problems muss noch in einem Teilproblem vorkommen.

    • Jede Bedingung des urspr. Problems muss auch in einem Teilproblem vorkommen.

    • Jede Variable, die in zwei Subproblemen vorkommt, muss auch in jedem dazwischenliegenden SubProblemen vorkommen, z.B. kommt SA ganz links und ganz rechts vor und somit auch in den dazwischenliegenden zwei Subproblemen.

    • Zwei Subprobleme sind miteinander verbunden, wenn sie eine Bedingung gemeinsam haben, z.B. sind die beiden Subprobleme, die NT-SA enthalten, miteinander verbunden.

    • Die Verbindungen formen eine Baumstruktur

Die zu Subproblemen zusammengefassten Knoten können nun mit Mega-Variablen
belegt werden (d.h. immer eine bestimmte Kombination aus Wertzuweisungen)
Nach der Wahl einer Wertzuweisung, müssen die anderen Subprobleme in überein-
stimmung dazu gebracht werden.

Die Komplexität hängt von der Baumweite (Größe des größten Teilproblems 1)
ab. Im Beispiel enthält das größte Subproblem 3 Variablen, so dass sich also 2 erg.


Die Baumweite des Graphen ist die minimalste Baumweite die man unter Betracht-
ung aller möglichen Dekompositionen finden kann (NP-hart)
Ist jedoch eine Dekompositionen mit Weite w bekannt, so kann das Problem in
O(nd^(w+1)) gelöst werden.


6 Adversarial Search


Die Welt ist nicht mehr statisch, sondern ein Externer erzeugt für uns ungünstige Situationen, d.h. es existiert ein Gegner, der unseren Nutzen minimieren möchte.


6.1 Spieltheorie

es existiert mehr als nur ein Agent --> Zustand der Welt nicht mehr hervorsagbar --> nicht alles auf einmal planbar, sondern updates der Berechnung erforderlich --> generiere Aktionen die auf diese Ungewissheit ausgerichtet ist, d.h. gut ist, unabhängig von der Handlung des Gegners (competetive environment)


Vereinfachungen:

  • extensive games
    Wir betrachten eine Folge/Sequenz von Aktionen (also nicht gleichzeitig). Ein zeitlicher Bezug besteht.

  • deterministic game. Jede Aktion wird tatsächlich ausgeführt

  • two-player-game: Genau zwei Agenten

  • Nullsummenspiel: Der Ausgang des Spiels addiert sich immer zu0, d.h. was der eine gewinnt, geht dem andern verloren und es kann nicht sein, dass beide gewinnen.

  • perfekte Informationen: vollständig beobachtbare Welt der andere Spieler spielt nicht verdeckt


Iterative Tiefensuche


kombiniert die Vorteile aus Breiten- und Tiefensuche: Optimal und vollständig, wie die Breitensuche, benötigt jedoch weniger Speicherplatz. Die Funktion gibt eine Sequenz von Lösungen zurück.


funktion Iterative-Deepening-Search(problem)

FOR (depth=0 to ) {
IF (Depth-Limited-Search(problem, depth) erfolgreich) THEN { return result; }

}

return failur


Nachteil: gleiche Knoten werden auf
verschiedenen Levels mehrmals
generiert/expandiert/analysiert

--> Redundanz

Dafür findet man optimale Lösungen
mit geringerer Tiefe

Die Anzahl der Expandierungen ist geringer
als bei der Breitensuche

IDS: Level(d) + Level(d-1) + ... = bd + 2bd-1 + 3bd-2 + ... + (d-1)b2 + db  O(bd)
Speicherkomplexität: O(bd), d.h. linear zum BranchingFaktor (=Konstante)

BFS: BreitenFirstSuche = b + b² + bÂł + ... bd + b(d+1)-b  O(bd+1)


z.B. b=10, d=5

IDS: 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450

BFS: 10 + 100 + 1,000 + 10,000 + 100,000 + 999,990 = 1,111,100


Bidirektionale Suchen


Suche vom Initialzustand ausgehend (meist mit Breitensuche) vorwärts, sowie vom Zielzustand ausgehend rückwärts. Sofern die Suche symmetrisch verlaufen, muss somit nur 2mal bis zur halben Tiefe gesucht werden, d.h die Komplexität wird von O(bd) auf O(2bd/2) = O(bd/2) reduziert.

  • Allerdings ist die Rückwärtssuche nicht immer möglich, da Vorgänger evtl. nicht ermittelbar sind

  • Bei einer Menge von Ziel- oder auch Startzuständen ist dieses Verfahren nicht mögl.

  • Die überprüfung, ob ein neuer Knoten bereits im anderen Suchbaum enthalten ist, muss effizient möglich sein, z.B. Hashfunktion

  • Welche Suchmethode soll jeweils angewandt werden?


b BranchingFaktor (Anzahl der Nachfolger) 1 b ist endlich

d Tiefe der Lösung 2 Schritt kostet mehr als c

m maximale Tiefe des Baumes 3 Aktionskosten alle gleich

l Limit der Tiefensuche 4 beide Richtungen mit BFS

C Kosten der optimalen Lösung

c minimale Kosten einer Aktion


Breiten-Suche

Uniform-Kosten-suche

Tiefen-Suche

Tiefen-limitierte Suche

Iterative Tiefen-suche

Bidirektio-nale Suche

Vollständigkeit

Ja1

Ja1,2

Nein

Nein

Ja1

Ja1,4

Zeitkomplexität

O(bd+1)

O(bC/c)

O(bm)

O(bl)

O(bd)

O(bd/2)

Speicherkomplexität

O(bd+1)

O(bC/c)

O(bm)

O(bl)

O(bd)

O(bd/2)

Optimal

Ja3

Ja

Nein

Nein

Ja

Ja3,4

Tiefensuche ist entweder vollständig oder optimal


Wiederholende Zustände

führt zu exponentieller overhead

verwende Graphen- statt Baumsuche:

  • Erweitere Baumsuche um eine Liste
    bereits besucher Knoten (closed-list)

  • Ignoriere neu expandierte Knoten, die bereits in der closed-liste sind

  • Closed-list kann mit Hasfkt. impl. weden

  • Benötigt viel Speicherplatz

  • Kann zu suboptimalen Lösungen führen, wenn der optimale Weg erst im zweiten Anlauf gefunden werden würde, der Knoten jedoch schon in der closed-list aufgef. Ist


Informed Search Methods (Heuristics, Local Search Methods,Genetic Algorithms)


Best-First Search
Suchverfahren unterscheiden sich bei der Bestimmung des zu expandierenden Nachfolgerknotens

  • Uninformed Search:
    Rigides Verfahren, das nicht weiß, wie gut ein Knoten ist

  • Informed Search:
    Qualität des gegebenen Knoten bekannt in Form einer Evaluierungs-Funktion h,
    die jedem Knoten einen Wert zuweiset.

  • Best-First Search:
    Suchverfahren, dass den Knoten mit “bestem” (kleinstem) h-Wert expandiert


Allgemeiner Algorithmus

function Best-First-Search(problem, Evaluierungsfunktion)

{

Queueing-Funktion <-- ordnet die Knoten gem. der Evaluierungsfunktion

return General-Search(problem, Queueing-Funktion)

}


Wenn die Evaluierungsfunktion perfekt ist, benötigt man keine Suche!


Greedy Search

Eine Möglichkeit den Wert eines Knotens zu beurteilen, ist die Entfernung zum Ziel zu schätzen: h(n) = estimated distance von Knoten n zum Ziel

Voraussetzunh ist, dass h(n) = 0 wenn n das Ziel ist


Die Best-First-Search mit dieser Funktion wird greedy best-first search genannt

z.B. route-finding: h = Luftlinie zweier Orte





  1. Arad: h=366

  2. Arad != Ziel

  3. Arrad expandieren

  4. mit h sortierte Kandidatenliste: (Sibiu, Timisoara, Zerind)

  5. Sibiu != Zieltest

  6. Entferne Sibiu aus fringe-Liste und expandiere Sibiu
    (wo kommt man von Sibiu ausgehend überall hin, und welchen h Werte besitzt der Ort)

Probleme der Greedy-Suche

  • Findet suboptimale Lösungen, z.B. Arad, Sibiu, Rimnicu, Pitesti, Bucharest

  • Verfahren kann sich verlaufen, z.B. Iasi nach Fagaras endet bereits bei Neamt,Iasi,N...

  • unvollständig, wenn wir nicht Duplikate ermitteln


Die Evaluierungsfunktion wird in der GreedySuche auch heuristische Funktion oder Heuristik genannt.

In der Künstl. Intelligenz hat Heuristik (Problemlösungs-Verfahren) zwei Bedeutungen:

    • Heuristiken sind schnell in bestimmten Situationen jedoch unvollständig

    • Heuristiken sind Methoden, die die Suche fokusieren (in die richtige Richtung), ohne zur Unvollständig zu führen

    • Heuristiken sind immer problembezogen (individuell entwickelt) und sollen das System immer in die richtige Richtung lenken


A*: Minimalisierung der gesamten, geschätzten Pfadkosten

A* kombiniert die die GreedySuche mit dem Uniformen-Kostensuchverfahren

g(n) = tatsächliche Kosten vom Startzustand zum Zustand n

h(n) = geschätzte Kosten von n zum nähesten Zielzustand

f(n) = g(n) + h(n)= geschätzte Kosten der billigsten Lösung über n

h*(n) = tatsächliche Kosten des optimalen Pfads von n zum nähesten Ziel


h ist zulässig, wenn für alle n gilt: h(n) h*(n), d.h. h muss eine Unterschätzung sein.

A* ist vollständig und optimal




Optimalität von A*

Satz: Die erste gefundene Lösung der Baumsuche hat minimale Pfadkosten

Beweis: Es gäbe einen Zielknoten G mit optimalen Pfadkosten C*, doch A* findet zuerst

einen anderen Knoten G2 mit g(G2)>C*, insb. F(G2)>C*



Alle Kosten müssen strikt positiv sein und der BranchingFaktor darf nicht unendlich sein.


Werden Graphen statt Bäume durchsucht, gibt es zwei Möglichkeiten A* anzuwenden.

  • Vertausche teuren mit billigeren Pfad, beim wiederholten Besuch eines Knotens

  • stelle sicher, das der zuerst besuchte Pfad der optimale ist:
    Dazu Monotonie&Konsistenz: Eine Heuristik ist konsistent, wenn für alle Knoten n und deren Nachfolger succ(n)=n' folgende Dreiecksungleichung gilt:
    h(n)  h(n') + c(n,a,n') = geschätzte Kosten vom Nachfolger zum nächsten Ziel + tats. Kosten a für den übergang von n nach n'

  • Jede konsistente Heuristik ist zulässig: ...

  • A* ist für die Graphensuche optimal, wenn die Heuristik konsistent ist

  • Ist h konsistent, können die Werte von f entlang des Pfades nicht abnehmen (Monot.)
    f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') >= g(n) + h(n) = f(n)

  • Hat man keine konsistente Heuristik, kann man das Verfahren dennoch anpassen,
    indem man das maximum beider Werte max{8,9} für den falschen Wert 8 nimmt.


Vollständigkeit

Falls eine Lösung exisitiert, findet A* diese, sofern (1) jeder Knoten eine endliche Anzahl von Nachfolger hat (das heißt BranchingFaktor darf nicht Unendlich sein) und (2) eine positive Konstante d exisitiert, so dass jede Operation mindestens Kosten d hat.
--> endliche Anzahl von Knoten n mit f(n)<=f*, d.h. es ex. dann ein f(n) <= opt. Lösung


Konturen von A*

Innerhalb des Suchraumes wachsen Konturen, in denen alle Knoten für die gegebenen F-Werte expandiert werden.


Zuerst wird innerhalb der ersten Kontur gesucht. Nach der Expansion


Komplexität

Das gewöhnliche Wachstum ist exponential da der Fehler proportional zu den Pfadkosten ist. Modifiziere daher um suboptimale Lösungen zu finden und erlaube nicht-zulässige Heuristiken.
In den Fällen, wo der Fehler zwischen den tats. minimalen Kosten und den heuristischen minimalen Kosten |h*(n)-h(n)| <= O(log(h*(n)) ist, wird nur eine sub-exponentielle Anzahl von Knoten expandiert. Sonst gilt eben die exponentiale worst-case-Komplexität.

Daher sucht man manchmal auch nur nach guten und nicht unbedingt den besten Lösungen.


änderung von A* um die Speicherkomplexität zu verbessern:

IDA* = Iterative TiefenA*Suche. Dabei wird nicht wie bei der limitierten Tiefensuche, die Tiefe stets erhöht, sondern der Suchradius anhand der Konturen f festgelegt.

dabei erhöht man die conturwerte z.b. schrittweise um 20 wobei innerhalb der kontur die knoten mit geringeren f-werten (=g+h) liegen.


Function IDA*(problem) returns a solution sequence

static: f-limit, the current f-Costs limit
root, a node

root := makenode(inital_state(problem))

f-limit = f-cost(root)

loop {

solution, f-limit = DFS-Konturen(root, f-limit)

if solution is non-null then return solution
if f-limit = unendlich then return failiure; end

}


Funktion DFS-Konturen(node, f-limit) returns a solution sequence and a new f-Cost limit

static: next-f, the f-Cost limit for the next contour, initally unendlich

if f-cost(node) > f-limit then return null, f-cost(node)

if goal-test(problem)(state(node)) then return node, f-limit

for each node s in successors(node) do

solution, new-f = DFS-Konturen(s, f-limit)

if solution is non-null then return solution, f-limit

next-f = min(next-f, new-f); end;

return null, next-f



RBFS - IDA Stern


IDA* und RBFS verbrauchen eigentlich zu wenig Speicherplatz, da sie nur ein Pfad betr.



Wie entwirft man nun Heurisiken?

Vereinfache das Problem indem man Einschränkungen weglässt und Relaxionen bildet,
z.B. durch Luftliniendistanz, Kollisionen bei Navigation ignorieren, negative Effekte ignorieren. 8-puzzle:

h1 = anzahl falscher positionen

h2 = manhatten distanz


Wie wählt man die beste aus einer Menge von Heuristiken? -> Konzept der Dominanz

Gilt für alle Knoten n dass Heuristik h2(n)>=h1(n) dann dominiert h2 die Heuristik h1 und eignet sich besser für die Suche.

Hat man zwei Heuristiken die einander nicht dominieren, kann man daraus eine dritte bauen: h(n)=max(h1(n), h2(n)). h dominiert dann h1 und h2



Lokale Suchmethoden

Oft ist es nicht möglich den gesamten Suchraum systematisch zu erforschen, da dieser zu groß ist.Daher gibt es lokale Suchmethoden, die zwar weder Vollständigkeit oder Optimalität garantieren, jedoch praktisch anwendbar sind. Das globale Optimum ist durch eine objektive Funktion gegeben (Qualitätsmaß für die Höhe des Bergs). Beginne mit einer zufällig gewählten Konfiguration und verbessere dich schrittweise (Hill-Climbing)

--> unvollständig, jedoch in sehr großen Räumen anwendbar.

Hat der Nachfolgerzustand einen schlechteren Wert, dann behalte den aktuellen bei, ansonsten wähle den Nachfolger.


wie gesagt, ist dieses Verfahren nicht vollständig und kann evtl. nur zum
lokalen statt globalen
Maximum führen.


Genauso weiß man nicht ob links oder rechts wenn man sich auf einem plateau befindet.



Der Wert 17 zeigt die Anzahl der Möglichkeiten, die Dame auf diesem Feld zu schlagen. Bewege die Dame immer auf das Feld mit dem geringsten Wert. Lokale Maxima können auftreten.


Probleme der lokalen Suchmethode:

1. lokale Maxima -> suboptimale Lösungen

2. Plateaus --> zufällige Entscheidung notwendig

3. Ridges:

Lösungen:

  • mehrmaliger random restart und wähle anschließend das beste lokale maximum

  • inject noice (rauschen): gehe nicht deterministisch in die beste richtung sondern mit einer gewissen wahrscheinlichkeit. gehe mit geringer wahrscheinlichkeit in die falsche Richtung -> random walks

  • Tabu-search: Wende die letzten n Operatoren nicht erneut an: muss empirisch ausprobiert werden.


Simulated Annealing




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