Projektseminar:

Pattern-Datenbanken für heuristische

Suchverfahren

Inhalt
Heuristische Suchalgorithmen werden in der Künstlichen Intelligenz, in Planungssystemen und in der kombinatorischen Optimierung eingesetzt, um Zustandsgraphen nach kostenoptimalen Lösungen zu durchsuchen. Die Effizienz des Suchprozesses hängt ganz wesentlich von der Güte der verwendeten Heuristik ab. Aktuelle Algorithmen verwenden als Heuristik sogenannte Pattern-Datenbanken (pattern databases), die komprimiert im Hauptspeicher liegen und über schnelle Indizierungsfunktionen adressiert werden.

Am Beispiel von Einpersonen-Puzzles (n-Puzzle, Rubics Cube) und Sequenz-Alignmentverfahren der Bioinformatik wollen wir effiziente, parallele Algorithmen für die Erstellung großer Pattern-Datenbanken programmieren, die dann ihrerseits für die Lösungssuche in komplexen Problemen angewandt werden. Dabei kommen die Programmiersprachen C, C++ und Assembler sowie thread-parallele Methoden (OpenMP) zum Einsatz. Zur Entwicklung und Erprobung stehen hochparallele Cluster-Systeme mit großem Hauptspeicher und breiten Vektoreinheiten zur Verfügung.

Die Studierenden sollten Programmiererfahrung (möglichst C, C++) sowie Grundkenntnisse in Systemarchitektur mitbringen. Nach einer Einführung durch den Veranstalter halten die Studierenden Kurzvorträge zu ausgewählten Suchalgorithmen und Pattern-Datenbanken. Diese werden in Kleingruppen programmiert, getestet und optimiert und die Ergebnisse in einem Abschlussvortrag vorgestellt.

Ort/Zeit
Mittwochs, 13-15 und 15-17 Uhr
Raum 1'307 im CMS-Gebäude

Planung, Unterrichtsmaterial (Passwort geschützt)

10.04.2019   Organisatorisches (.pdf) <- aktualisiert am 05.06.2019
10.04.2019   Einführung (.pdf)
17.04.2019   Depth-First Iterative-Deepening (.pdf)
24.04.2019   Literaturstudium / Vorbereitung der Vorträge
01.05.2019   Feiertag
08.05.2019   Vorträge zu Themen 1 und 2
    Paralleles A* (.pdf)
    Paralleles IDA* (.pdf)
15.05.2019   Vorträge zu Themen 3 und 6
    Bidirektionale Suche (.pdf)
    Compressing Pattern Databases (.pdf)
23.05.2019   Pattern Datenbanken (Folien .pdf, Artikel .pdf)
    MapReduce für parallele Heuristische Suche (.pdf)
29.05.2019   Festlegung der Projektthemen
05.06.2019   Diskussion im Plenum zum Projektfortschritt
    Message Passing Interface (.pdf)
12.06.2019   Termin entfällt: Programmierarbeit in Kleingruppen
19.06.2019   Vorstellung erster Projektergebnisse im Plenum
26.06.2019   Integration mit Kompressions-API (siehe git), kein Treffen
03.07.2019   Vorstellung der Projektergebnisse im Plenum
10.07.2019   Vorstellung der Projektergebnisse im Plenum
    IDA* Duplicate Node Detection (.pdf)
    Projektergebnis Parallel A* (.pdf)