Eine ausführliche, abschnittsweise Erklärung der Folien mit den Beispielen aus dem Deck: Rumänien-Routen, 8-Puzzle, 8-Damen, BFS/DFS, A* und Heuristiken.
WS_26_27/EIKI/VL3/AI101-03.pdf. Das Original-PDF wird hier nicht öffentlich mitgehostet; die Seite enthält daraus abgeleitete Lernnotizen und keine Originalfolienbilder.Wie wird eine alltagssprachliche Aufgabe für einen Agenten lösbar gemacht?
Die Titelfolie ordnet Suchalgorithmen in zwei Familien: un-/blind (BFS, Uniform-Cost, DFS, Depth-Limited, Iterative Deepening, bidirektionale Suche) und informiert (Best-First und A*). Die Vorlesung knüpft an die vorherigen Agenten-Themen an: Agenten nehmen ihre Umgebung wahr, entscheiden und handeln; sie versuchen ein Leistungsmaß zu optimieren. [1][2]
Die Folie stellt die Situation vor, in einer fremden Stadt ohne Smartphone, aber mit einer Karte, vom Hotel mit öffentlichen Verkehrsmitteln zum Strand zu kommen. Die Leitfrage „Was machst du?“ motiviert Problemdefinition, Suchbaum, Suchstrategie, uninformed search, Heuristiken und informed search. [3]
Ein zielbasierter Agent nutzt Sensoren, um die Umgebung und den aktuellen Zustand einzuschätzen, ein Modell davon, wie sich die Welt entwickelt und was Aktionen bewirken, sowie Ziele. Er projiziert mögliche Handlungsfolgen in die Zukunft, vergleicht die erwarteten Zustände mit den Zielen und wählt daraus eine Aktion für die Aktuatoren. [4]
Problem-solving agents sind ergebnisorientiert: Sie konzentrieren sich darauf, ein Ziel zu erfüllen. Weil Probleme oft in menschlicher Sprache beschrieben sind, muss die Beschreibung für den Agenten umformuliert werden. Die Folien nennen als erste Schritte: Ziel formulieren und anschließend das Problem passend zu diesem Ziel formulieren. [5]
Zustand beschreibt eine mögliche Situation; der Zustandsraum umfasst die möglichen Situationen. Aktionen/Transitionen verbinden Zustände durch einzelne Schritte. Kosten unterscheiden Aktionen; häufig soll die Gesamtkostensumme bis zum Ziel minimiert werden. Ein Problem wird durch Zustandsraum und Startzustand, mögliche Aktionen, Zieltest und Kostenfunktion beschrieben. [6][7]
Ein Zustandsraumdiagramm stellt zwei Räume, die Position des Staubsaugers und die Schmutzverteilung dar. Kanten mit Aktionen wie L, R oder S verbinden Situationen; manche Aktionen verändern den Zustand, andere können als Schleife zum selben Zustand zurückführen. Die erreichbaren Zustände und Übergänge ergeben gemeinsam den Zustandsgraphen. [8]
Ein Zustandsraum ist die Menge der vom Start erreichbaren Zustände. Ein Pfad ist eine Folge von Zuständen, die durch Aktionen verbunden sind. Eine Lösung führt vom Start zu einem Zielzustand; eine optimale Lösung hat unter den Lösungen die geringsten Pfadkosten. [9]
Startzustand ist Arad; Aktionen führen in benachbarte Städte; der Zieltest prüft, ob Bukarest erreicht ist. Kosten können etwa die zurückgelegte Strecke oder ein anderes Reisekriterium abbilden. Die Lösung ist die Reihenfolge der Städte beziehungsweise Aktionen, die zum Ziel führt. [10]
Reale Probleme vereinfachen, ohne die entscheidende Struktur zu verlieren.
Die Folien stellen die komplexe reale Straßenkarte einer abstrakten Darstellung gegenüber: Städte werden zu Knoten und Straßen zu gewichteten Kanten. So wird aus der geografischen Welt ein Suchproblem, in dem mögliche Verbindungen und Streckenkosten systematisch untersucht werden können. Die gezeigten Kantenwerte umfassen unter anderem Arad–Sibiu 140, Sibiu–Rimnicu Vilcea 80, Rimnicu Vilcea–Pitesti 97, Pitesti–Bukarest 101 und Fagaras–Bukarest 211. [11]
Oradea–Zerind 71; Zerind–Arad 75; Arad–Timisoara 118; Oradea–Sibiu 151; Timisoara–Lugoj 111; Lugoj–Mehadia 70; Mehadia–Drobeta 75; Drobeta–Craiova 120; Sibiu–Fagaras 99; Rimnicu Vilcea–Craiova 146; Craiova–Pitesti 138; Bukarest–Giurgiu 90; Bukarest–Urziceni 85; Urziceni–Hirsova 98; Hirsova–Eforie 86; Urziceni–Vaslui 142; Vaslui–Iasi 92; Iasi–Neamt 87. [12]
Computational: Welches Ziel und welche vereinheitlichenden Prinzipien verfolgt die Berechnung? Algorithmisch: Welche Repräsentationen und Algorithmen setzen sie um? Implementational: Wie wird das System in Hardware beziehungsweise durch Neuronen realisiert? Die Folie verbindet das mit dem Punkt, dass Abstraktion wissenschaftliches Verstehen ermöglicht, aber auch Fragen dazu aufwirft, welche Muster und Idealisierungen relevant sind. [13]
Die Folie formuliert einen konkreten Start- und Zielzustand des 3×3-Schiebepuzzles. Ein Zustand ist die Position der Kacheln; die Aktionen verschieben das Leerfeld nach links, rechts, oben oder unten; der Zieltest vergleicht mit der Zielanordnung; jeder Zug kostet 1. Zwischenpositionen während des Schiebens und physische Probleme wie ein verklemmter Schieber werden im Modell ignoriert. [14]
Gesucht ist eine Anordnung von acht Damen auf einem 8×8-Schachbrett, bei der keine zwei einander bedrohen. Eine naive vollständige Zustandsdarstellung betrachtet beliebige Platzierungen der acht Damen – die Folie schätzt dafür etwa 3·1014 Zustände. Eine inkrementelle Formulierung setzt Damen Spalte für Spalte und lässt nur konfliktfreie Fortsetzungen zu; dadurch nennt die Folie nur 2057 Zustände. [15][16]
In dieser effizienteren Form sind Zustände konfliktfreie Damen in den ersten n Spalten; als Aktion wird eine konfliktfreie Dame in Spalte n+1 ergänzt; Zieltest ist, dass kein Paar sich schlagen kann; Pfadkosten sind hier nicht wichtig. [17]
Ein Planungsproblem hat einen Startzustand und ein gewünschtes Ziel, das durch Aktionen und deren zukünftige Folgen erreicht werden soll. Suche ist der Prozess, eine – möglichst optimale – Aktionsfolge zu finden. Tree Search behandelt den Zustandsraum wie einen Baum, startet beim Anfangszustand, wählt nach einer Strategie einen Blattknoten und erweitert ihn, bis ein Ziel gefunden oder kein Kandidat mehr vorhanden ist. Jeder Suchbaumknoten steht dabei für einen Pfad im Zustandsgraphen. [18][19]
Welche Knoten expandieren wir – und welche Eigenschaften hat die Strategie?
Vom Start Arad expandiert man zunächst nach Sibiu, Timisoara und Zerind; bei weiterer Expansion von Sibiu kommen Arad, Fagaras, Oradea und Rimnicu Vilcea dazu. Die fringe/frontier ist die Menge der Endknoten bislang besuchter Pfade; die Tiefe zählt Ebenen im Suchbaum. Ein Zustand beschreibt die Situation, während ein Suchknoten zusätzlich Elternknoten, Aktion, Pfadkosten und Tiefe enthält. Expansion erzeugt Nachfolgerknoten und aktualisiert den Baum. [20][21][22]
Eine Strategie legt fest, in welcher Reihenfolge Knoten expandiert werden. Bewertet wird sie nach Vollständigkeit (findet sie eine Lösung, falls eine existiert?), Zeit (Anzahl Expansionen), Speicher (maximale Zahl gespeicherter Knoten) und Optimalität (findet sie eine Lösung mit minimalen Kosten?). In den Komplexitätsangaben stehen b für maximalen Verzweigungsfaktor, d für Tiefe der optimalen Lösung und m für maximale Tiefe. [23]
Uninformierte Suche kennt nur die Problemdefinition; dazu gehören BFS, Uniform-Cost Search, DFS, Depth-Limited Search und Iterative Deepening. Informierte Suche nutzt Zusatzwissen darüber, wo Lösungen wahrscheinlich liegen; die Folien nennen Greedy Best-First, A* und speicherbegrenzte heuristische Suche. [24]
Uniform-Cost Search expandiert jeweils den Knoten mit den geringsten bisher aufgelaufenen Pfadkosten. BFS ist der Spezialfall, wenn alle Schritte gleich viel kosten: Es untersucht den Baum Ebene für Ebene. Die Folien geben an, dass beide bei positiven Schritt-Kosten vollständig und optimal sind; UCS ist nach kumulierten Kosten geordnet. [25]
Bei einem angenommenen Verzweigungsfaktor b=10, einer Million generierter Knoten pro Sekunde und 1000 Byte pro Knoten zeigt die Folie den exponentiellen Ressourcenanstieg: Tiefe 6 etwa 1 GB; Tiefe 10 ungefähr 10 TB; Tiefe 12 rund 1 PB. Die Zahlen sind illustrative Annahmen der Folie und sollen zeigen, dass die Speicherkosten die praktische Nutzbarkeit begrenzen können. [26]
| Tiefe | Knoten (Folie) | Zeit (Folie) | Speicher (Folie) |
|---|---|---|---|
| 2 | 110 | 0,11 ms | 107 kB |
| 4 | 11.110 | 11 ms | 10,6 MB |
| 6 | 10⁶ | 1,1 s | 1 GB |
| 8 | 10⁸ | 2 min | 103 GB |
| 10 | 10¹⁰ | 3 h | 10 TB |
| 12 | 10¹² | 13 Tage | 1 PB |
| 14 | 10¹⁴ | 3,5 Jahre | 99 PB |
| 16 | 10¹⁶ | 350 Jahre | 10 EB |
Speicher gegen Vollständigkeit und optimale Lösung abwägen.
Die Folien heben hervor, dass uninformed Suche mit exponentiellen Kosten außerhalb kleiner Instanzen schnell unpraktisch wird. DFS geht einen Zweig möglichst tief hinunter und kehrt dann zurück, um Alternativen zu untersuchen. Sie benötigt typischerweise weniger Speicher, ist aber in unendlichen Tiefen oder bei Zyklen nicht vollständig und findet nicht notwendigerweise die kostengünstigste Lösung; die angegebene Worst-Case-Zeit ist O(bm) und der Speicher O(bm). [28][29]
Im gezeigten Baum besucht BFS die Knoten levelweise: A, B, C, D, E, F, G, H, I. DFS folgt erst einem Zweig so weit wie möglich: A, B, D, E, I, F, C, G, H. Die Folien vergleichen BFS als speicherintensiver und oft langsamer mit DFS als speichersparender; BFS eignet sich, wenn das Ziel eher nahe an der Wurzel liegt, DFS wenn es tief liegt – wobei DFS keine Optimalität garantiert. [30][31]
Depth-Limited Search setzt eine feste Grenze l; Knoten tiefer als l werden nicht betrachtet. Die Folie nennt O(bl) Zeit und O(bl) Speicher, ist im Allgemeinen nicht vollständig und nicht optimal und fragt, wie l sinnvoll gewählt wird. Die Pseudocode-Routine unterscheidet Erfolg, Fehlschlag und cutoff, damit eine erreichte Grenze nicht mit einem wirklichen Fehlschlag verwechselt wird. [32]
IDS führt Tiefensuche wiederholt mit steigender Grenze aus: l=0,1,2,…, bis Lösung oder Fehlschlag feststeht. Dadurch wird die Suche vollständig und findet bei gleichen Schritt-Kosten eine Lösung mit minimaler Tiefe; der Speicherbedarf bleibt linear O(bd), während obere Ebenen mehrfach durchsucht werden. [33]
Hier laufen zwei Suchen gleichzeitig: eine vom Start und eine vom Ziel; beendet wird, wenn sich die Suchbereiche treffen. Im idealisierten Vergleich sinkt der Aufwand von Größenordnung bd zu ungefähr 2·bd/2. Das funktioniert nur, wenn die Aktionen rückwärts ausgeführt werden können; bei DFS ist nicht garantiert, dass die Suchpfade passend zusammentreffen. [34]
| Verfahren | Vollständig? | Speicher-Tendenz | Optimal? |
|---|---|---|---|
| BFS | Ja, unter den Folienbedingungen | hoch, O(bd+1) in der Tabelle | Ja* |
| Uniform-Cost | Ja* | hoch | Ja |
| DFS | Nein | niedrig, O(bm) | Nein |
| Depth-Limited | Ja, falls l ≥ d | O(bl) | Nein |
| Iterative Deepening | Ja | O(bd) | Ja* |
* Die Sterne verweisen auf Voraussetzungen und Einschränkungen in der Vorlesungsfolie; bei UCS etwa positive Mindestschritt-Kosten.
[35]Zusatzwissen lenkt die Suche – aber eine schlechte Schätzung kann in die Irre führen.
Eine Heuristik h(n) ist eine Faustregel beziehungsweise Funktion, die die verbleibenden Kosten von n bis zum Ziel schätzt. Sie soll die Suche effizienter machen, indem sie „vielversprechende“ Knoten bevorzugt; sie kann aber falsch liegen. Für Routen kann die Luftlinienentfernung zum Ziel als Schätzung der noch nötigen Strecke dienen. [36]
Greedy verwendet f(n)=h(n) und expandiert den Knoten mit der kleinsten geschätzten Restdistanz. Im Rumänienbeispiel ist h(n) die Luftlinienentfernung nach Bukarest; Arad wird mit 366, Sibiu mit 253 und Bucharest mit 0 angegeben. Die Methode kann schnell eine Richtung vorgeben, aber sie berücksichtigt die bisher tatsächlich angefallenen Kosten nicht. [37]
Die open list enthält erzeugte, noch nicht expandierte Knoten (Frontier); die closed list hält bereits expandierte Knoten fest und verhindert redundante Wiederbesuche. Greedy ist nicht allgemein vollständig oder optimal; die Folie zeigt als Gegenbeispiel die Suche von Iasi nach Fagaras: Neamt erscheint der Heuristik näher am Ziel als Vaslui, obwohl diese Vorliebe in die falsche Richtung führen kann. [38][39]
A* ist eine informierte Best-First-Suche, die nicht nur die Schätzung bis zum Ziel berücksichtigt. Sie kombiniert bisherige Kosten g(n) mit geschätzten Restkosten h(n):
Damit schätzt f(n) die Gesamtkosten eines Weges zum Ziel, der über n führt. [40]
Vom Start Arad haben die Nachfolger zunächst diese Bewertungen: Sibiu 393=140+253, Timisoara 447=118+329, Zerind 449=75+374. A* wählt also Sibiu. Danach ergeben sich unter anderem Rimnicu Vilcea 413=220+193 und Fagaras 415=239+176; die Suche expandiert jeweils den aktuell kleinsten f-Wert. Die Kartenfolien illustrieren die fortschreitende Auswahl der Route Richtung Bukarest. [41][42]
Wann darf man A* vertrauen, und wie viel Arbeit spart eine bessere Heuristik?
In der Rumänien-Demonstration kann ein Zielknoten bereits in der Frontier liegen, während A* noch einen anderen Knoten – etwa Pitesti – expandiert. Der Grund ist, dass ein noch offener Weg eine günstigere Gesamtlösung liefern kann; die Folien stellen das der Greedy-Suche gegenüber und motivieren so den Optimalitätsnachweis von A*. [43]
Die Folie sagt, A* sei vollständig, außer wenn unendlich viele Knoten mit f(n)≤f(G) existieren. Die Laufzeit kann exponentiell wachsen; A* muss im Allgemeinen alle Knoten im Speicher behalten. Die Optimalität hängt von Eigenschaften der Heuristik ab. [44]
h₁: Anzahl falsch liegender Kacheln. h₂: Summe der Manhattan-Distanzen – für jede Kachel die Zahl der horizontalen plus vertikalen Kästchen bis zum Zielplatz. Auf dem gezeigten Startzustand ist h₁=8 und h₂=18. Die Tabelle aus 100 Puzzle-Instanzen vergleicht IDS und A*: Manhattan-Heuristik h₂ erzeugt in den aufgeführten Tiefen deutlich weniger Knoten als h₁ und IDS. [45][46]
Eine Heuristik ist zulässig, wenn sie die tatsächlichen Kosten zum Ziel nie überschätzt: h(n)≤h*(n). Die Luftlinienentfernung ist auf der Rumänienkarte ein Beispiel für eine zulässige Schätzung der Straßenentfernung. [47]
Eine Heuristik ist konsistent, wenn für jeden Zustand n und jeden Nachfolger n′ gilt: h(n)≤c(n,a,n′)+h(n′). Die Folien nennen dies eine Art Dreiecksungleichung. Jede konsistente Heuristik ist zulässig; außerdem sind bei Konsistenz die f-Werte entlang eines Pfads nicht abnehmend. [48]
Von gelockerten Problemen bis zum Optimalitätsargument.
Ein gelockertes Problem hat weniger Einschränkungen bei den Aktionen. Die Kosten der optimalen Lösung des gelockerten Problems sind eine zulässige Heuristik für das ursprüngliche Problem. Beim 8-Puzzle: Lässt man Kacheln beliebig weit springen, ergibt sich die Zahl falsch liegender Kacheln; erlaubt man Bewegungen auf jedes benachbarte Feld, ergibt sich die Manhattan-Distanz. [49]
Wenn h₁ und h₂ beide zulässig sind und h₂(n)≥h₁(n) für alle n gilt, dominiert h₂ die schwächere Heuristik und liegt näher an der wahren Restkostenfunktion. Für das 8-Puzzle dominiert Manhattan die Zahl falsch liegender Kacheln. Sind mehrere zulässige Heuristiken nicht direkt vergleichbar, bleibt max(h₁,…,hₘ) zulässig und dominiert jede einzelne von ihnen; eine stärkere zulässige Heuristik kann unnötige Expansionen verringern. [50][51]
Die Vorlesungsfolie formuliert: A* mit Tree Search und zulässigem h ist optimal. Die Beweisidee: Auf einem optimalen Pfad liegt ein noch nicht expandierter Frontier-Knoten n; wegen h(n)≤h*(n) ist f(n) höchstens die optimale Lösungskost C*. Ein suboptimales Ziel G₂ hat f(G₂)=g(G₂)>C*. Daher wird es nicht vor einem optimalen Ziel ausgewählt. [52][53]
Die Folien nennen drei speicherbegrenzte Alternativen: IDA* ähnelt Iterative Deepening, verwendet aber eine Schranke auf f=g+h statt auf Tiefe; RBFS versucht Best-First mit linearem Speicher nachzubilden und merkt sich den besten Alternativwert; SMA* verwirft bei vollem Speicher den schlechtesten Blattknoten, speichert dessen Wert beim Elternknoten und kann ihn später erneut durchsuchen müssen. [54]
Eine Folie zeigt eine Verbindung aus Vision Transformer, Guidance Map und Neural-A*-Planer: Bild-/Kartenpatches werden codiert, daraus entsteht eine Guidance Map, und ein Planer liefert einen globalen Pfad, der in die Bewegungssteuerung eines vierbeinigen Roboters eingeht. Das Beispiel illustriert datengetützte Unterstützung klassischer Pfadplanung. [55]
Wiederholte Zustände können einen Suchbaum stark aufblasen: Eine schmale Folge von d Zuständen kann im Baum durch verschiedene Wege bis zu 2ᵈ Pfaden erscheinen; auf einem Raster können bei d Schritten nur ungefähr 2d² Zustände erreichbar sein, obwohl es viel mehr Pfade gibt. Graph Search verwaltet daher eine explored-Menge und fügt Nachfolger nur hinzu, wenn sie weder in der Frontier noch in explored sind; Dijkstras Algorithmus wird als Graph-Search-Variante von Uniform-Cost Search genannt. [56][57]
Was du nach diesem Vorlesungsblock erklären und anwenden können sollst.
Bei Tree Search repräsentiert jeder Knoten einen möglichen Pfad zum Zustand; derselbe Zustand kann mehrfach auf verschiedenen Pfaden auftauchen. Ein später gefundener Weg kann günstiger sein und dadurch frühere Arbeit überflüssig machen. Graph Search erkennt wiederholte Zustände; bei A* kann eine konsistente Heuristik außerdem sicherstellen, dass günstigere Pfade zuerst behandelt werden. [58][59]
Die Folien begründen die Zulässigkeit der Zahl falsch liegender Kacheln damit, dass jede falsch liegende Kachel mindestens einmal bewegt werden muss. Die Manhattan-Summe ist zulässig, weil jede Kachel mindestens ihre Manhattan-Distanz an Zügen bis zum Ziel benötigt. Im angeführten Beispiel lauten die Werte hMIS=8, hMAN=18 und optimale Restkosten h*=26. [60]
Die Lernziele sind: reale Probleme als Suchprobleme formulieren; Suchstrategien unterscheiden; uninformed von informed search erklären; DFS, BFS und A* schrittweise ausführen; Eigenschaften guter Heuristiken benennen. Als nächstes kündigen die Folien lokale Suchalgorithmen und adversarielle Suche an. [61]