Themen im Bereich der Constraint-Programmierung und Constraint Handling Rules

Unten finden Sie eine Liste möglicher Themen für Praktika und Diplom/Bachelor/Master-Arbeiten im Bereich der Constraint-Programmierung und Constraint Handling Rules. Die Themen sind als Vorschläge gedacht und können bei Interesse entsprechend angepasst werden. Auch eigene Themenvorschläge sind willkommen.

Bei Interesse wenden Sie sich an Prof. Frühwirth oder Frank Raiser.

Abschlussarbeit: Paralleles CHR mit CUDA

Moderne GPUs verfügen über Hunderte von Kernen, was sie für High-Performance Computing geeignet macht. Die Programmiersprache CHR andererseits ist inherent parallel aufgebaut.

Die Aufgabe in dieser Abschlussarbeit ist die Evaluierung möglicher Implementierungsansätze, die das Ausführen von CHR Regeln auf GPUs erlauben. Die Arbeit bietet zwei mögliche Richtungen je nach Interesse des durchführenden Studenten: der Fokus kann entweder auf die Verwendung von CHR Regeln für deklarative und ausführbare Graphikalgorithmen, d.h. eine Abstraktion von CUDA, gelegt werden, oder darauf traditionelle CHR Programme parallel auf einer GPU ausführen zu können.

Benötigte Vorkenntnisse: Kenntnis von CHR oder CUDA hilfreich

Aushang

Betriebspraktikum: SecuritEase

SecuritEase is a company located in Wellington, New Zealand. Their main product is a fully integrated front office and back office stock broking system. Their clients process 45% of the NZSX equity market.
SecuritEase is cooperating with the CHR research group Ulm, as their software is based on Prolog and CHR. They offer two internships for students: First, a Prolog/CHR-based tool has to be developed to assist the conversion of Java/Swing applications to an internal format. Second, a CHR-SQL interface has to be developed that executes CHR rules on data combined from external sources and a database.

Offer by SecuritEase: Payment for 2 months, return airfares to Wellington, New Zealand, and free accommodation (near office, close to sea).

Required knowledge: good command of English language, knowledge of CHR and Prolog

Aushang

Praktikum: CHR meets Android

In dieser Arbeit soll CHR auf das Android-Betriebssystem portiert werden und eine prototypische CHR-Anwendung auf einem Smartphone realisiert werden.

Benötigte Kenntnisse: Grundlagenwissen über CHR oder Android.

Praktikum: Development of a Visual Tracer for Constraint Handling Rules

Die operationelle Semantik von CHR erfordert, dass Regeln solange angewandt werden, bis keine weiteren mehr anwendbar sind. Daher beinhaltet ein Programmlauf normalerweise keine Information darüber welche Regeln angewendet wurden.

Die Aufgabe dieses Praktikums ist es einen Java-basierten CHR Compiler zu modifizieren, um Informationen über Regelanwendungen zu extrahieren und den Programmablauf zu visualisieren. Das resultierende Werkzeug sollte für den Einsatz in der Lehre geeignet sein.

Aushang

Praktikum: Source-to-Source Transformation Engine for Constraint Handling Rules

Die CHR Forschungsgemeinschaft entwickelt häufig Erweiterungen von CHR mit Hilfe von Source-to-Source Transformationen, d.h. neue Features der Sprache werden realisiert, indem eine Implementierung in der CHR Kernsprache angegeben wird.

Die Aufgabe dieses Praktikums is die Entwicklung eines Rahmenwerks zum vereinfachten Entwickeln von Source-to-Source Transformationen. Das resultierende Werkzeug soll evaluiert werden, indem prototypisch bekannte Transformationen implementiert werden (z.B. high-level Compiler-Optimisierungen).

Aushang

Praktikum: Long-Term Routing for Robotic Sailing Ships

InnoC.at hat erfolgreich autonome Robotersegelschiffe geschaffen, welche nach Eingabe von GPS-Koordinaten ohne menschliches Zutun dorthin segeln können. Ein nächster Schritt im Ausbau dieser autonomen Schiffe ist die Integration von Langzeitplanung in deren Routenberechnung.
Die CHR Forschungsgruppe Ulm kooperiert mit InnoC.at, um eine CHR-basierte Lösung zu entwickeln, die Wegpunkte für Langzeitrouten ermittelt. Dabei müssen aktuelle Wetterbedingungen, Strömungen, etc. berücksichtigt werden, um ein Schiff schnell und sicher ans Ziel zu bringen.
Die Aufgabe im Praktikum ist die Entwicklung eines Prototyps zur Berechnung und Visualisierung einer geeigneten Route mit Wegpunkten.

Aushang

Praktikum: CHR-GUI

In diesem Praktikum soll eine GUI entwickelt werden, die CHR-Constraints während der Ausführung visualisiert. Dabei sollen Constraints Graphiken zugeordnet werden können und auf diese Weise auch Animationen ermöglicht werden.

Praktikum: CHR meets Google Documents

In diesem Praktikum soll eine Schnittstelle zwischen Google Documents und CHR entwickelt werden. Damit soll es ermöglicht werden CHR Reasoning-Methoden auf Spreadsheets anzuwenden (z.B. Konsistenzüberprüfungen, autom. Dateninferenz, ...).

Benötigte Vorkenntnisse: Kenntnisse zu CHR oder Google Documents API.

Abschlussarbeit: Konfluenz von CHR Programmen

Bei CHR Programmen stellt sich oft die Frage, ob für eine bestimmte Eingabe unabhängig von der Reihenfolge der Regelanwendungen immer das gleiche Ergebnis berechnet wird. Diese Eigenschaft wird Konfluenz genannt und ist für terminierende CHR Programme entscheidbar. Im Rahmen dieser Arbeit soll der bearbeitende Student sich mit CHR und Konfluenz vertraut machen. Ein existierender Konfluenz-Tester für CHR Programme soll zudem um die Analyse invarianten-basierter Konfluenz erweitert werden.

Bei Bearbeitung durch einen Master- oder Diplom-Studenten kann zusätzlich noch eine Auswahl der folgenden Thematiken behandelt werden:

• Useability und Performance-Aspekte
• Program Equivalence

Benötigte Vorkenntnisse: Kenntnisse in Prolog. Kenntnis von CHR ist von Vorteil.

Kontakt: Prof. Dr. Frühwirth, Frank Raiser

Literatur:

Abschlussarbeit: Parallele Berechnung der Kanten-Konsistenz des alldifferent-Constraints

Das alldifferent-Constraint ist ein in der Constraint-Programmierung häufig eingesetztes Constraint, welches für die angegebenen Variablen spezifiziert, dass eine gültige Lösung diese mit unterschiedlichen Werten belegen muss. Das alldifferent-Constraint findet zum Beispiel bei der Lösung des bekannten 8-Damen-Problems Einsatz.

Ziel dieser Arbeit ist es für das alldifferent-Constraint einen effizienten parallelen Löser in CHR zu entwickeln. Bisherige Löser basieren auf einem Flussalgorithmus, welcher nicht trivial parallelisierbar ist. Vor kurzem wurde jedoch eine parallele Implementierung für CHR entwickelt, so dass der bearbeitende Student sich im Rahmen der Arbeit damit vertraut machen soll. Anschließend soll die Implementierung angewendet und erweitert werden, um einen parallelen CHR-Löser für das alldifferent-Constraint zu entwickeln.

Benötigte Vorkenntnisse: Kenntnis von CHR.

Abschlussarbeit: Attributierte Graphtransformationssysteme in CHR

Algebraische Graphtransformationssysteme (GTS) besitzen zahlreiche Anwendungen. Dabei werden anhand vorgegebener Regeln Graphen transformiert. Da diese Transformationen mathematisch fundiert sind lassen sich darauf weitreichende Analysen, wie etwa Korrektheit, Terminierung, Konfluenz, ... durchführen. In [1] wurde gezeigt, dass sich CHR besonders gut eignet, um Prototypen für GTS zu entwickeln.

Die bisherigen Resultate umfassen lediglich getypte Graphtransformationssysteme und sollen im Rahmen dieser Arbeit erweitert werden um attributierte getypte GTS. In einem attributierten GTS kann zusätzlich den Kanten und Knoten eines Graph ein Attribut zugeordnet werden. Im Rahmen der Transformation kann dieses Attribut gemäß einer zugrundeliegenden Algebra modifiziert werden.

Aufgrund des Einarbeitungsaufwands in CHR und attributierte GTS eignet sich dieses Thema nicht für die zeitlich kürzer veranschlagten Bachelor-Arbeiten.

Benötigte Vorkenntnisse: keine.

Abschlussarbeit: PersistentCHR

CHR eignet sich in seiner allgemeinsten Formulierung besonders für eine parallele Ausführung. Allerdings zeigte sich, dass die bestehenden Semantiken schwer umzusetzen sind in einer parallelen Umgebung. Ein neuer Ansatz der Ulmer CHR Forschungsgruppe auf der Basis persistenter Constraints verspricht hier wesentliche Vereinfachungen.

Ziel der Arbeit ist das Erstellen einer parallelen CHR Implementierung mit Unterstützung persistenter Constraints. Im Rahmen einer Master- oder Diplomarbeit werden dabei zusätzliche Optimierungstechniken aus der CHR Forschung eingebaut (Indexing, Programmtransformationen, ...).