Problemlösen durch Suchen. Überblick Problemlösende Agenten Motivation: Problemlösen durch Suche...

Problemlösen durch Suchen

Überblick

• Problemlösende Agenten

• Motivation: Problemlösen durch Suche

• Problemtypen

• Probleme formulieren

• Beispielprobleme

• Einfache Suchalgorithmen

Problemlösende Agenten

Offline-Problemlösen, da Wissen vollständig!

Begriffe: Online / Offline

• Offline:1. Berechne erst vollständige Lösung

2. Dann Ausführung in der Realwelt

• Online: „Interleaving“, d.h. Verzahnung – Berechnung– Aktion– Berechnung– Aktion …

Problemlösen durch Suchen

• Erinnerung: Modellbasierte Agenten „denken“ über Wirkung ihrer Aktionen nach

• Besonders wichtig, wenn eine Aktion nicht ausreicht, um zum Ziel zu kommen, …

• … sondern mehrere Aktionen in der richtigen Reihenfolge nötig sind!

• Ansatz: Mehrere Aktionsfolgen durchspielen

Beispiel: Rumänien

• Standort: Arad• Ziel: Bukarest• Zielformulierung:

– In Bukarest sein

• Problemformulierung:– Zustände: Verschiedene Städte– Aktionen: Von einer Stadt zur anderen fahren

• Lösung finden:– Folge von Städten finden, z.B. Arad, Sibiu, Fagaras,

Bukarest

––

–•

Beispiel: Rumänien

Einordnung der Umgebung „Landkarte“

• Statisch: Städte fest• Beobachtbar: Agent kennt Standort• Diskret: Fahrt nur durch „diskrete“ Städte, nicht

querfeldein• Deterministisch: Aktion „Fahre nach X“ endet in X

Weitere Begriffe: Problemtypen• Deterministisch, vollständig beobachtbar Ein-Zustands-Problem (single state problem)

– Agent weiß genau, in welchem Zustand er gelangen wird; Lösung ist eine Zustandsfolge

(Ein-Zustands-Problem heißt nicht, dass es nur einen Zustand gibt!)• Nicht-beobachtbar Sensorloses Problem (“Angepasstes

(conformant) Problem”)– Z.B. Staubsauger kennt seinen Ort nicht ; Lösung ist eine Zustandsfolge

• Nicht-deterministisch und/oder teilweise beobachtbar Kontingenzproblem– Wahrnehmungen liefern neue Information über aktuellen Zustand– Meist Interleaving erforderlich– Wenn die neue Information durch anderen Agenten verursacht wird:

Adversariales Problem• Unbekannter Zustandsraum Explorationsproblem

–

––

Beispiel: Staubsaugerwelt

• Einzustands-Problem, Start #5 Lösung?

•

Beispiel: Staubsaugerwelt

• Einzustands-Problem, Start #5

Lösung? [Rechts, Saugen]

•

Beispiel: Staubsaugerwelt

• Sensorlos, Start in {1,2,3,4,5,6,7,8} z.B. Rechts geht über in {2,4,6,8},

d.h. Menge von Zuständen

statt nur eines Zustands.Lösung?

Beispiel: Staubsaugerwelt

• Sensorlos, Start in {1,2,3,4,5,6,7,8} z.B. Rechts geht über in {2,4,6,8} },

d.h. Menge von Zuständen

statt nur eines Zustands. Lösung? [Rechts,Saugen,Links,Saugen]

Beispiel: Staubsaugerwelt

• Kontingenz-Problem – Nicht-deterministisch:

Z.B. Saugen kann Teppich

verschmutzen!– Teilweise beobachtbar:

Ort, Schmutz am aktuellen Ort.– Wahrnehmung:

[L, Sauber], d.h. Start in #5 oder #7

Lösung?

Beispiel: Staubsaugerwelt

• Kontingenz-Problem – Nicht-deterministisch:

Z.B. Saugen kann Teppich

verschmutzen!– Teilweise beobachtbar:

Ort, Schmutz am aktuellen Ort.– Wahrnehmung:

[L, Sauber], d.h. Start in #5 oder #7

Lösung?

[Rechts, wenn Schmutz dann Saugen]

Formulierung des Single-State Problems

Nach Festlegen der Zustände ist ein Problem definiert durch vierPunkte:

1. Anfangszustand, z.B. „in Arad"2. Aktionen, die in einem Zustand möglich sind, sind gegeben durch

die Nachfolgerfunktion S(x) = Menge der Aktion–Zustand Paare – Z.B. S(Arad) = {<Arad Zerind, Zerind>, … }

3. Pfadkosten (additiv)– Z.B. Summe der Distanzen, # Aktionen etc.– c(x,a,y) ≥ 0 sind die Schrittkosten

4. Zieltest:– Explizit, z.B. x = „in Bukarest"– Implizit, z.B. Schachmatt(x)

Eine Lösung ist eine Sequenz von Aktionen die vom Anfangszustandzum Zielzustand führen.

––

–

Wahl des Zustandsraums• Realwelt ist hochkomplex

Zustandsraum muss abstrahieren • Wahl der Zustände schwierigster Teil der Problemformulierung!• Hier:

– Zustand = Stadt– Kosten = Entfernung der Mittelpunkte

• Was wurde ignoriert / idealisiert?– Kosten = Strecke (nicht Fahrzeit, Spritkosten)– Ausdehnung der Stadt, Stau, Straßenzustand– Detailabläufe: Gas geben, lenken, …

• (Abstrakter) Zustand = Menge realer Zustände• (Abstrakte) Aktion = komplexe Kombination realer Aktionen

– Z.B. "Arad Zerind" repräsentiert eine komplexe Menge möglicher Routen, Umwege, Gasgeben, Lenken, etc.

• Um Realisierbarkeit zu garantieren muss jeder reale Zustand "in Arad“ zu einem realen Zustand "in Zerind“ führen

• (Abstrakte) Lösung = – Menge der Pfade die Lösungen in der Realwelt sind

• Jede abstrakte Aktion sollte "einfacher" sein als das reale Problem

•••

Pfadkostenfunktion• Hier: Pfadkosten = Summe der Schrittkosten• Schritt = Aktion, die von einem Zustand zum

nächsten führt• Sinnvoll z.B. bei Städte-Problem

– A nach B 20 km– B nach C 10 km– A über B nach C 30 km

• Gegenbeispiel:– Auto beschleunigt auf Weg von A nach B: 3 sec– Auto beschleunigt auf Weg von B nach C: 3 sec– Auto beschleunigt von A nach B (3 sec), ist also auf

Weg von B nach C schon schneller (1 sec) !

Staubsaugerwelt als Zustandsraum

• Zustände?• Aktionen?• Zieltest?• Pfadkosten?

•

Staubsaugerwelt als Zustandsraum

• Zustände? Diskreter Schmutz und diskreter Ort• Aktionen? Links, Rechts, Saugen• Zieltest? Kein Schmutz an allen Orten• Pfadkosten? 1 pro Aktion

Beispiel: Schiebefax

• Zustände?• Aktionen? • Zieltest?• Pfadkosten?

Beispiel: Schiebefax

• Zustände? Anordnungen • Aktionen? Verschiebe Lücke links, rechts, rauf, runter • Zieltest? Bestimmte Anordnung• Pfadkosten? 1 pro Verschieben

[Bemerkung: optimale Lösung der n-Puzzle Familie ist NP-hart]

••

8-Damen Problem

• Zustände: 0-8 Damen in bel. Anordnung• Ausgangszustand: Brett leer• Nachfolgerfunktion: 1 Dame auf freies Feld setzen• Pfadkosten: Egal• Zieltest: Alle 8 Damen da, keine wird bedroht

Verwandte Problem der Routensuche

• Routensuche (Zustand = Stadt)

• Touring Problem: – Jede Stadt 1x besuchen, Anfangs- = Endstadt– Zustand = Aktuelle Stadt + alle schon

besuchten

• Traveling Salesman Problem: Kürzesten Weg für Touring finden

Realweltproblem: Manipulation durch Roboter

• Zustände?: Reellwertige Gelenkwinkel des Arms, reellwertige Objektkoordinaten

• Aktionen?: Kontinuierliche Gelenkwinkel, Gelenkwinkelgeschwindigkeiten, -beschleunigungen

• Zieltest?: Z.B. vollständige Montage• Pfadkosten?: Ausführungszeit

•••

•

Suchbäume

• Idee:– Offline, simulierte Exploration des Suchraums, indem

Nachfolger bereits untersuchter Zustände generiert werden (“Expandierung” von Zuständen)

–

Suchbaum: Beispiel

Suchbaum: Beispiel

Suchbaum: Beispiel

Implementierung: Allgemeiner Suchbaum

Implementierung: Zustände / Knoten• Ein Zustand ist eine Repräsentation einer physischen Konfiguration

• Ein Knoten ist eine Datenstruktur, die Bestandteil des Suchbaums ist. Umfasst Zustand, Elternknoten, Aktion, Pfadkosten g(x), Tiefe

• Ein Zustand kann durch mehrere Knoten repräsentiert sein! (Z.B. Arad – Sibiu – Arad bei ungünstiger Strategie)

• Die Expand Funktion erzeugt neue Knoten und belegt die Felder der Datenstrukturen mit Werten. Insb. wird die Nachfolgefunktion SuccessorFn des Problems angewendet, um die entsprechenden Zustände zu erhalten.

Suchstrategien• Eine Suchstrategie ist definiert durch die Reihenfolge, in

der die Knoten expandiert werden.

• Strategien werden anhand folgender Kriterien bewertet: – Vollständigkeit: Wird garantiert eine Lösung gefunden, falls eine

existiert?– Zeitkomplexität: Zahl der erzeugten Knoten – Speicherkomplexität: Maximalzahl der Knoten im Speicher – Optimalität: Wird die Lösung mit den geringsten Kosten sicher

gefunden?– Optimalität heißt nicht: Die (optimale oder suboptimale) Lösung

wird mit geringstem Suchaufwand gefunden!

• Zeit- und Speicherkomplexität werden in folgenden Größen ausgedrückt:– b: Maximaler Verzweigungs (branching-)faktor des Suchbaums– d: Minimale Tiefe (depth) der optimalen Lösung– m: Maximale Tiefe des Suchbaums (u.U. ∞)

––

Uninformierte Suchstrategien

• Uninformierte Suchstrategien verwenden nur die Information, die durch die Problemdefinition gegeben ist

• Wichtigste Strategien:– Breitensuche (Breadth-first search)

– Suche mit einheitliche Kosten (Uniform-cost search)

– Tiefensuche (Depth-first search )

– Tiefenbeschränkte Suche (Depth-limited search)

– Iterative Tiefensuche (Iterative deepening search)

–

–

–

–

Breitensuche

• Expandiere zuerst Knoten mit geringster Tiefe • Implementierung:

– Rand (fringe) ist eine FIFO-Schlange, d.h. neue Nachfolger werden am Ende der Schlange einsortiert

•

Breitensuche

• Expandiere zuerst Knoten mit geringster Tiefe • Implementierung:

– Rand (fringe) ist eine FIFO-Schlange, d.h. neue Nachfolger werden am Ende der Schlange einsortiert

•

Breitensuche

• Expandiere zuerst Knoten mit geringster Tiefe • Implementierung:

– Rand (fringe) ist eine FIFO-Schlange, d.h. neue Nachfolger werden am Ende der Schlange einsortiert

•

Breitensuche

• Expandiere zuerst Knoten mit geringster Tiefe • Implementierung:

– Rand (fringe) ist eine FIFO-Schlange, d.h. neue Nachfolger werden am Ende der Schlange einsortiert

•

Eigenschaften der Breitensuche

• Vollständig? Ja (falls b endlich)• Zeit? 1+b+b2+b3+… +bd + bd+1-b = O(bd+1) (Wenn Lsg. auf Tiefe d müssen noch bd+1-b Knoten (unnötig) erzeugt werden.)• Speicher? O(bd+1) (jeder Knoten wird

gespeichert)• Optimal? Ja (falls Kosten = 1 pro Schritt)

• Speicher ist das Hauptproblem (noch mehr als Zeit)

••

•

Suche mit einheitliche Kosten

• Expandiere Knoten mit (bisher) geringsten Pfadkosten zuerst

• Implementierung:– Rand = Schlange geordnet nach Pfadkosten

• Equivalent zu breadth-first falls Schrittkosten alle gleich• Vollständig? Ja, falls Schrittkosten ≥ ε• Zeit? # Knoten mit g ≤ Kosten der optimalen Lösung,

O(bceiling(C*/ ε)), wobei C* = Kosten der optimalen Lösung• Speicher? # Knoten mit g ≤ Kosten der opitmalen

Lösung, O(bceiling(C*/ ε))• Optimal? Ja – Knoten werden in ansteigender Ordnung

von g(n) expandiert

••••

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search

• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Depth-first search• Expandiere tiefsten Knoten zuerst• Implementierung:

– Rand = LIFO Schlange, d.h. Nachfolger nach vorne

–

•

Eigenschaften der depth-first search

• Vollständig? Nein: Versagt in unendlich tiefen Suchräumen und Suchräumen mit Schleifen – Modifikation: Verbot der Zustandswiederholung

entlang eines Pfades Vollständig in endlichen Suchräumen

• Zeit? O(bm): Katastrophal falls m wesentlich größer als d– Aber: Falls Lösungen “dicht” sind, kann depth-first

wesentlich schneller sein als breadth-first

• Speicher? O(bm), d.h., linear im Speicher!• Optimal? Nein

••

–•

–

Tiefenbeschränkte Suche

= depth-first Suche mit Tiefenlimit l,

d.h. Knoten mit Tiefe l haben keine Nachfolger

• Rekursive Implementierung:

Iterative Tiefensuche

Iterative Tiefensuche l =0

• Schwarz: Expandierte Knoten ohne Nachfolger

• Neustart für jedes l !

Iterative Tiefensuche l =1

• Schwarz: Expandierte Knoten ohne Nachfolger

• Neustart für jedes l !

Iterative Tiefensuche l =2

• Schwarz: Expandierte Knoten ohne Nachfolger

• Neustart für jedes l !

Iterative Tiefensuche l =3

• Schwarz: Expandierte Knoten ohne Nachfolger

• Neustart für jedes l !

Iterative Tiefensuche

• Zahl der Knoten, die depth-limited Suche bis Tiefe d mit Verzweigungsfaktor b generiert:

NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd

• Zahl der Knoten, die Iterative Tiefensuche bis Tiefe d mit Verzweigungsfaktor b generiert: NIDS = (d+1)b0 + d b1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd

• Für b = 10, d = 5,– NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111– NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

• Overhead = (123,456 - 111,111)/111,111 = 11%

–

–•

Eigenschaften der Iterativen Tiefensuche

• Vollständig? Ja

• Zeit? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)

• Speicher? O(bd)

• Optimal? Ja, wenn Schrittkosten = 1

•

•

•

Übersicht

Wiederholte Zustände• Wenn wiederholte Zustände nicht erkannt werden, kann

ein lineares Problem exponentiell werden!

•

Zustandsraum Suchbaum

Graphensuche• Modifikation von Tree-Search: Liste bereits besuchter Zustände• Bei wiederholtem Zustand wird der neue Pfad verworfen• Findet daher i.a. nicht das Optimum, außer im Fall

– konstanter Kosten oder

– Breadth-first-seach

• Speicherprobleme bei sehr vielen Zuständen

Zusammenfassung

• Problemformulierung erfordert gewöhnlich Abstraktion. Irrelevante Details der Realwelt werden weggelassen um einen Zustandsraum zu erhalten, in dem das Problem durch Suche gelöst werden kann.

• Sehr unterschiedliche “blinde” / “uninformierte” Suchstrategien

• Iterative Tiefensuche benötigt nur linearen Speicher und nicht wesentlich mehr Zeit als andere uninformierte Algorithmen

• Graphensuche vermeidet wiederholte Zustände

••

•