|
Vorlesungsfolien
Vorlesungsskript
Inhaltsübersicht zur Prüfungsvorbereitung
Applet
|
 Spezialvorlesung WS 06/07: Suchalgorithmen
Veranstalter: PD Dr. Stefan Edelkamp
Termin: Mi. 14:15-15:45, Raum: OH-14 Raum 105
Thema
Die grundlegende Erforschung von Suchverfahren zur
Exploration extrem großer, mitunter unendlicher, sowohl
präpositionaler als auch nummerischer 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.
Inhalt
Die Vorlesung teilt sich in zwei Teile, einem theoretischen
Teil, der die Suchverfahren an sich beschreibt und analysiert
(ca 2/3 der Vorlesung) und einem Anwendungsteil (ca. 1/3 der
Vorlesung), der den gekonnten Einsatz der Verfahren in der Praxis
erläutert.
Zu Beginn Vorlesung werden unterschiedliche Charakterisierungen
von Zustandsräumen und Methoden der implizite Graphsuche
vorgestellt: gewichtete
Graphen, Automaten, Kripke-Strukturen, Transitions- und
Produktionssysteme. Basisalgorithmen,
wie A*/IDA*, Hill-Climbing, Dynamische Programmierung,
Bestensuche und Branch-and-Bound, werden kurz rekapituliert.
Der Einführungsteil beinhaltet auch den Einsatz von grundlegenden
Techniken zur Speicherung von Zuständen und zur
Beschneidung des Suchraumes.
Im weiteren Verlauf der Vorlesung werden neuere Entwicklungen
von Suchalgorithmen aufgegriffen und vorgestellt. Dabei steht
die Entwicklung von externen und parallelen bzw. verteilten
Verfahren genauso im Vordergrund, wie die Entwicklung von
Pfad- statt Zustandsbasierten Suchverfahren.
Es werden Constraint-Methoden erarbeitet, die
temporale Anforderungen an die zu erzeugende Lösung
befriedigen, und mit sanfte, d.h., nur gewünschte,
Anforderungen erfüllen.
In das bestehen Algorithmen-Portfolio werden
Realzeitverfahren eingefügt, für die nur ein
begrenzter Zeithorizont zur Nachfolgerauswahl zur
Verfügung steht, die aber über die Zeit hinweg
ihr Problemlöseverhalten verbessern.
Unter der selectiven Suche versteht man Verfahren,
bei denen die Nachfolgerauswahl randomisiert wird.
Der zweite Teil der Vorlesung betrifft die Adaption der
Suchverfahren and herausfordernde Anwendungen. Jeder der
Anwendung wird ausreichend Platz eingeräumt, um
die konzeptionellen Anforderungen zu verstehen, formal zu fassen
und an die eingeführten Suchverfahren anzupassen. Als Teilgebiete
wurden die KI-Handlungsplanung, die Modellpr&uum;fung von
Software, die Navigation beweglicher Objekte, die Robotik
und das Sequenzalignierungsproblem erörtert..
Literatur
Prüfungsrelevant sind die Folien der Vorlesung.
Zur Vertiefung der Vorlesung dienen ausgewählte Kapitel
des (englischsprachigen) Lehrbuchs
-
Stefan Edelkamp, Stefan Schroedl, and Sven Koenig
Heuristic Search: Theory and Practice
Morgan Kaufmann (ca. 750 pages, to appear in 2007)
Relevant für die Vorlesung sind
die folgenden Kapitel.
I. Theory
- Basic Search Algorithms (3)
- External Search (9)
- Distributed Search (10)
- Real-Time Search (12)
- Incremental and Anytime Search (13)
- Constraint Search (15)
- Selective Search (16)
II. Applications
- Search for Action Planning (17)
- Search for Model Checking (18)
- Search for Vehicle Navigation (19)
- Search for Sequence Alignment (20)
- Search for Robotics (21)
Die Vorlesung setzt Grundstudiumsvorlesungskenntnisse voraus.
Der Besuch einer KI- bzw. CI-Einführungsvorlesung ist
wünschenswert, aber kein notwendiges Kriterium.
|
|