|
Vorlesungsfolien
Vorlesungsskript
Übungen
|
 Spezialvorlesung WS 06/07: Suchalgorithmen
Veranstalter: PD Dr. Stefan Edelkamp
Termin: Mi. 14:15-15:45, Raum: OH16-105
Thema
Die grundlegende Erforschung von Suchverfahren zur
Exploration extrem großer, mitunter unendlicher, sowohl
propositionaler als auch numerischer Zustandsräume, steht
derzeit in keinem Vergleich zu den erzielten Anfangserfolgen und
dem zu erwarteten industriellen Nutzen in den Bereichen des
Handlungs- bzw. des Routenplanens, der Bio-Informatik,
der Robotik, des automatischen Beweisens, der Software- sowie
der Hardwareverifikation.
In der Suche wird das Problemlösen als die Traversierung
eines Zustandsraums modelliert, d.h., man geht von einem
Startzustand aus, der das gegebene Problem beschreibt und hat
Übergangsregeln, um von einem Zustand zu einem oder mehreren
Nachfolgezuständen zu gelangen. Diese Übergangsregeln müssen
ausgehend vom Startzustand dann solange angewandt werden, bis
schließlich ein gewünschter Endzustand erreicht ist. In der
Regel ist man an einer kürzestmöglichen Folge derartiger
Übergänge interessiert und beschreibt den Problemgraphen
implizit durch eine Nachfolgererzeugungsfunktion.
Den meisten effizienten Suchverfahren ist eine allgemeine Schätz-
bzw. Bewertungsfunktion der verbleibenen Weglänge zum Ziel gemein.
Ist sie eine untere Schranke, so heißt die Schätzfunktion
optimistisch. Eine stärkere, aber häufig anzutreffende
Eigenschaft ist die der Konsistenz, die zu monotonen
Kostenfunktionen führt. Im Reinforcement-Lernen
werden die Bewertungsfunktionen aus der Exploration heraus gelernt.
Zu Beginn Vorlesung werden unterschiedliche Charakterisierungen
von Zustandsräumen und Methoden der implizite Graphsuche
vorgestellt und analysiert. Zustandsräume sind gewichtete
Graphen, Automaten, Kripke-Strukturen, Transitions- und
Produktionssysteme.
Literatur
Prüfungsrelevant sind die Folien der Vorlesung.
Zur Vertiefung der Vorlesung dienen ausgewählte Kapitel. Insbesondere
I. Theory
- Heuristic Search
- External Search
- Distributed Search
- Adversery Search
- Constraint Search
- Real-Time Search
- Incremental and Anytime Search
- Selective Search
II. Applications
- Search for Planning
- Search for Model Checking
- Search for Vehicle Navigation
- Search for Robotics
- Search for Sequence Alignment
der Buchvorlage
-
Stefan Edelkamp, Stefan Schroedl, and Sven Koenig
Heuristic Search: Theory and Practice
Morgan Kaufmann (To appear in 2007)
|
|