Proseminar

Einführung in die Künstliche Intelligenz

Sommersemester 1995

Prof. Dr. H.D. Burkhard, R. Kühnel Institut für Informatik, LIN116, LIN117
E-Mail: {hdb,kuehnel}@informatik.hu-berlin.de Tel: 20181-{214,217}

Anforderungen und Zielstellung

Eine grundlegende Herangehensweise auf dem Gebiet der Künstlichen Intelligenz ist die Trennung der Wissensrepräsentation von den Mechanismen des Problemlösens. Einerseits soll das Wissen für verschiedene Problemlöser zugänglich sein, andererseits sind Problemlösemethoden gefragt, die nicht vom repräsentierten Wissen abhängen.

In diesem Seminar wird eine Klasse derartiger Problemlösemethoden behandelt, die heuristischen Suchverfahren. Das Lösen eines Problems wird dabei als erfolgreiche Suche im Lösungsraum verstanden. Die potentielle Komplexität eines solchen Lösungsraumes erfordert spezielle Suchverfahren, die Wissen über die Verteilung der Lösungen ausnutzen. In dem Buch ''Problemlösen durch heuristische Suche in der AI'' von Hermann Kaindl, welches die Grundlage für das Proseminar bildet, wird dieses Wissen, die Heuristik, als ''die Kunst des Entdeckens'' bezeichnet.

Das Proseminar richtet sich an Studenten im Grundstudium. Als zusätzliche Wissensquelle für dieses Gebiet wird die Vorlesung ''Wissensrepräsentation und Inferenz'' von Herrn Heitsch empfohlen.

Die folgenden Bedingungen sind an den Erhalt eines Proseminarscheins geknüpft.

• ein mindestens mit genügend bewerteter Vortrag zu einem vorgegebenen Thema
• regelmäßige Teilnahme am Seminar

Themen

In den Vorträgen zu den einzelnen Suchverfahren sind jeweils der Algorithmus, die Effizienz und die Einsatzbedingungen zu erläutern und an einem Beispiel zu demonstrieren. Eine Implementation der Algorithmen bzw. der Hinweis auf Schwierigkeiten bei der Implementation wären ebenfalls interessant. C++-Kundige können auch Teile der Suchalgorithmenbibliothek ''aisearch'' vorstellen.

• 20.4.: Problemdarstellung, Und-/Oder-Bäume, Spielbäume, Begriffsbestimmungen, [ka89 Kap.1],[re 89 Kap. 1.1,1.2], Jens-Uwe Rumstich, Matthias Wagenknecht
• 27.4.: Allgemeine Suchmethoden [ka89 Kap. 2.1.-2.5.], Niklas Weis, Gregor Burkhard
• 11.5.: Best-First Search (A*) [ka89 Kap. 2.5.], Kai? Schröter, Fr. Müller
• 18.5.: Depth-First Iterative-Deepening und Bidirectional Search [ka89 Kap. 2.5,2.6], Jens Fleischer, Regina Lasch
• 01.6.: Minimax [ka89 Kap. 3.1], [re89 Kap. 1.3], Hr. Schulski, Torsten Oettel
• 08.6.: Depth-First Search [ka89 Kap. 3.2.], [re89 Kap. 2.1.], Myrko Thum, Derrick Hepp
• 15.6.: Nullfenster-Suchverfahren [re89 Kap. 2.2.], Michael Piefel, Lars Leppin
• 22.6.: Best-First Search (SSS* und DUAL*) [ka89 Kap 3.4.1], [re89 Kap. 2.3.2,2.3.3], Peter Weiße
• 29.6.: B* und PB* [ka89 Kap 3.4.2], Matthias Schwan
• 06.7.: Effizienz der Minimax-Verfahren [ka89 Kap 3.5], Sebastian Kircher

Literatur

• [ka89] H. Kaindl: Problemlösen durch heuristische Suche in der Artificial Intelligence, Springer-Verlag Wien - New York, 1989.
• [re89] A. Reinefeld: Spielbaum-Suchverfahren, Springer-Verlag, 1989.