Referat zum theoretischen Hintergrund des Themas (Vortrag, Kurzfassung) (Gruppenleistung)
theoretische Arbeit, Implementation, Experimente; dokumentiert durch Projektbericht (Gruppenleistung)
Vorstellung der Implementation und Rücksprache
Termine und Gruppen (hier finden sich auch gruppenspezifische Informationen sowie Referats-Folien)
Themen
Übersicht
Im Projekt MMML 2 befassen wir uns jedes Jahr mit Themen aus dem und um
das Gebiet Induktive Programmsynthese: Algorithmen zur induktiven
Synthese rekursiver Funktionen aus Anfangsprogrammen (Geradeausprogramme,
Operatorsequenzen), Anwendung von Problemlöse- und Planungsalgorithmen
zur Generierung von Anfangsprogrammen aus Ein-/Ausgabebeispielen, Analoges
Problemlösen und Lernen als alternative Strategie zu "synthesis from
scratch" und zum Erwerb von generalisiertem/abstraktem Programmierwissen.
Dieser Themenkomplex integriert verschiedene Forschungsgebiete der KI
und basiert auf Ansäen der Theoretischen Informatik (Semantik rekursiver
Funktionen, Termalgebra, grammatische Inferenz, Graphtheorie).
Anwendungskontext ist die wissensbasierte Softwareentwicklung. Das Thema
"Lernen aus Problemlöseerfahrung" hat starke Bezüge zu
kognitionswissenschaftlichen Fragestellungen.
Als Hintergrund dienen folgende Arbeiten:
Unser Ansatz zur Programmsynthese:
F. Wysotzki: Representation and Induction of Infinite Concepts and Recursive Action Sequences, Proc. 8.
Internat. Joint Conf. on Artificial Intelligence, Karlsruhe 1983.
Unser Ansatz zur Integration von Planung und Programmsythese:
F. Wysotzki: Program Synthesis by Hierarchical Planning, in: Artificial Intelligence II, Methodology, Systems,
Applications. Proceed. of the 2nd Internat. Conf. on Artificial Intelligence: Methodology, Systems, Applications
(AIMSA '86), Varna, Bulgaria, 1986 / Ed. by Ph. Jorrand and V. Sgurev.- Amsterdam u.a.: Elsevier Sc. Publ.,
1987, pp.3-11
Schmid, U. (1999). Iterative macro-operators revisited: Applying
program synthesis to learning in planning. Technical Report CMU-CS-99-114,
School of Computer Science, Carnegie Mellon University, Pittsburg, PA.
(90 pages, lots of figures esp. in chap. 4)
[dvi, 227472 bytes] [ps.gz 335252, bytes] - select "save link as..." to download
Dieses Semester werden wir uns auf den Bereich Planung konzentrieren:
Unser Planungssystem DPlan (aktuelle Version) ist ein zustandsbasierter, nicht-linearer Rückwärts-Planer. DPlan plant für Mengen von Zustäanden und ist damit ein
"universeller" Planer. DPlan kann einmal als "stand alone" System betrachtet --
und damit mit andereren aktuellen Ansätzen zur Planung (AI Repository/Planning Systems) verglichen werden (Ausdrucksstärke der Domain-Repräsentationssprache, Effizienz).
Zum anderen ist DPlan ein Werkzeug zur Generierung von Anfangsprogrammen fü unseren Synthesealgorithmus.
Wir werden zu den ersten beiden Projektsitzungen eine Einführung in
unseren Ansatz zur Planung und Programmsynthese und verwandte Ansätze
geben. Es wird von den Projektteilnehmern erwartet, daß sie sich bis
Ende April in die relevante Literatur einarbeiten (natürlich mit unserer
Unterstützung). Die konkreten Themen für die Projektgruppen werden
wir dann bis spätestens 3.5. gemeinsam (unter Berücksichtigung Eurer
Interessen und Vorkenntnisse) festlegen.
Mögliche Themen sind:
Erweiterung der Planspezifikationssprache (von STRIPS + Bedingte Effekte
zu ADL; damit kann der Planer auch auf Zahlen- und Listenprobleme angewendet werden)
Empirischer Vergleich von DPlan mit anderen Planungssystemen (Ziel: Teilnahme am nächsten AIPS Wettbewerb)
Reformulierung des DPlan Algorithmus ohne Zugriff auf Zustandsmengen als
Benutzer-Input (Algorithmus ist in CMU-CS-99-114 bereits skizziert)
Lernziele für Projektteilnehmer
Allgemein sind unsere Lehrziele für studentische Projekte:
Wie arbeitet man sich in ein neues Thema ein? (Literatursuche, Auswahl
relevanter Arbeiten, Darstellung des Stands der Forschung in mündlicher und schriftlicher Form)
Wie bearbeitet man ein Projekt auf professionelle Art? (Konkrete Formulierung des Themas, solide Zeitplanung, Koordination der Gruppenarbeit, klare Darstellung der erzielten Ergebnisse in Form eines Projektberichts)
Beide Aspekte sind grundlegend sowohl für Diplomarbeiten, als auch für spätere Arbeit in Forschung oder Praxis!
Unsere Lehrziele für dieses studentische Projekt:
Überblick über klassische und aktuelle Ansätze zur Planung
Einblick in Ansätze zur Makro-Generierung in der Planung, in
Ansätze zur induktiven Programmsynthese, in kognitionswissenschatliche
Erkenntnisse zum learning by doing
Methoden zum empirischen Vergleich der Performanz verschiedener Systeme
Erweiterung und Modifikation eines bestehenden Systems
Programmierung in LISP
Nützliche Informationen
(to be continued...)
Literatur zum Thema Planung (zahlreiche Referenzen finden sich in
CMU-CS-99-114):
James Allen, James Hendler and Austin Tate, editors,
"Readings in Planning", Morgan-Kaufmann Publishers, 1990. 754 pages,
ISBN 1-55860-130-9 paper ($49.95).
Stuart Russell and Peter Norvig, "Artificial Intelligence -- A modern
Approach", Prentice Hall, 1995. (Kapitel 11 bis 13)
aktuelle Ansätze wie Graphplan, Satplan, model based planning
finden sich leider noch nicht in Überblicksliteratur, am besten
informiert man sich über aktuelle Proceedings (z.B. der AIPS); spezifische Literatur für die Einzelthemen des Projekts siehe unter [Termine und Gruppen]
