Um Constraint-Löser in einer höheren Sprache schnell und ausreichend effizient zu spezifizieren und implementieren, wurde in der ersten Hälfte der 90er Jahre eine spezielle regelbasierte Sprache, "Constraint Handling Rules" (CHR), entwickelt. CHR kann in eine beliebige herkömmliche Programmiersprache als Bibliothek eingebettet werden. Die derzeit wichtigsten Implementierungen von CHR-Bibliotheken gibt es in Eclipse und Sicstus Prolog, zwei der in der Forschung am meisten benutzten Prolog-Systeme. Im Projekt wird die Constraint-Sprache CHR einerseits weiter untersucht, andererseits zur Implementierung von Anwendungen eingesetzt.
Die Constraint-Sprache CHR erleichtert die Implementierung von Constraint-Lösern erheblich und ermöglicht, dass Programmierer mit wenig Vorkenntnissen Constraint-Programme entwickeln. Wie es bei höheren Programmiersprachen oft der Fall ist, erweist sich die automatische Analyse und Verifikation von in der Constraint-Sprache CHR implementierten Constraint-Lösern als vielversprechend.
Eine essentielle, jedoch bei einer Regelsprache wie CHR nicht offensichtliche Eigenschaft eines Constraint-Lösers ist die Konfluenz. Sie garantiert, dass dasselbe Ergebnis berechnet wird, unabhängig davon, in welcher Reihenfolge die Constraints eintreffen und in welcher Reihenfolge die CHR-Regeln darauf angewandt werden, um sie abzuarbeiten. In diesem Projekt werden Bedingungen zur Konfluenz von CHR-Programmen und deren automatische Überprüfung untersucht. Darüber hinaus werden Verfahren entwickelt, um ein nichtkonfluentes CHR-Programm zu einem konfluenten zu vervollständigen.
Ansprechpartner: Dipl.-Inform. Slim Abdennadher
In diesem Teilprojekt werden Anwendungen der Constraint-Programmierung untersucht. Um die Hypothese zu überprüfen, derzufolge die Constraint-Sprache CHR auch von Programmierern ohne besonderen mathemathematische Kentnisse einsetzbar sei, werden Anwendungen bevorzugt, die den Einsatz von fortgeschrittenen numerischen Verfahren nicht erfordern. Das Hauptziel des Teilprojekts ist es, die Eignung der Constraint-Sprache CHR zur einfachen Programmierung beziehungsweise "rapid prototyping" experimentell zu belegen.
Mit einem Mietspiegel lässt sich eine Vergleichsmiete für eine Mietwohnung errechnen. Der Mietspiegelberechnungsdienst im Internet, IMS, erlaubt es, durch eine Formularseite im World-Wide-Web in wenigen Minuten die ortsübliche Vergleichsmiete einer Wohnung zu berechnen. Er kann auch mit ungenauen oder unvollständigen Angaben korrekt umgehen. Damit lässt sich erstmals ein Mietspiegel auch dazu verwenden, bei der Wohnungsuche das Mietpreisniveau zu bestimmen, ohne sich auf eine bestimmte Wohnung festlegen zu müssen. Die Münchner Presse erwähnte den Prototyp, die Stadtverwaltung München bietet ihn in ihren Web-Seiten an. Dadurch bekam er eine große Aufmerksamkeit in der Münchner Öffentlichkeit.
Die Implementierung besteht aus zwei Komponenten, einem in der Sprache CHR implementierten Constraint-Löser und einer deklarativen Spezifikation des Münchner Mietspiegels. Beide Komponenten sind besonders kurz: der Constraint-Löser ist eine halbe Seite lang, die Mietspiegelregeln selber umfassen zwei Seiten. Der Constraint-Löser spezifiziert die angewandte Intervallarithmetik und die Behandlung von unvollständigen Informationen. Er ist unabhängig von den sogenannten Mietspiegeltabellen und kann auch zur Mietspiegelberechnung für andere Städte eingesetzt werden. Die zweite Komponente der Spezifikation ist spezifisch für den Münchner Mietspiegel.
Der erste Prototyp wurde in Zusammenarbeit mit ECRC GmbH entwickelt. Er wird nun ausgewertet und weitere Entwicklungen werden überlegt.
IMS aufrufen: http://www.pst.informatik.uni-muenchen.de/personen/fruehwir/miet-demo.html
Ansprechpartner: Dipl.-Inform. Slim Abdennadher
Die Generierung von Dienstplänen für Krankenstationen ist ein besonders komplexes Problem, das heute noch Gegenstand der Forschung ist. Die Generierung eines Dienstplanes, speziell bei größeren Krankenstationen, ist sehr aufwendig: Üblicherweise benötigt eine Person mindestens einen ganzen Tag zur Planung eines Monates. Der Ansatz "Constraint Reasoning" eignet sich besonders gut zur Spezifikation der Bedingungen, die ein Dienstplan erfüllen muss. Ziel des Projektes ist es, durch die Nachahmung der Dienstplangenerierung von Hand die Komplexität des Problems empirisch einzuschränken. Dabei wird für jede Schwester (oder jeden Pfleger) einer Station sowie für jeden Tag des Planungszeitraums eine Schicht (wie etwa Früh-, Spät- oder Arbeitsfreischicht) zugeteilt, wobei auf eine optimale Lösung verzichtet wird. Vielmehr sollen manche "harte" Bedingungen unbedingt erfüllt werden, und manche "weiche" Bedingungen nur nach Möglichkeit.
Ein erster interaktiver Prototyp, das in IF-Prolog implementierte System INTERDIP, erlaubt es, Teillösungen als endgültig festzulegen, was einerseits die Komplexität einschränkt, andererseits die Akzeptanz durch die Benutzer erhöht. Für 20 Schwestern und 30 Tage z.B. kann INTERDIP einen Dienstplan teilautomatisch und interaktiv innerhalb weniger Minuten - statt von Hand einiger Stunden - erstellen. Die Implementierung beruht auf einem unanpassbaren Constraint-Löser für harte Constraints der Sprache IF-Prolog. Die Behandlung der weichen Constraint beruht auf einem Branch-and-Bound-Verfahren. Mit der Constraint-Sprache CHR können dagegen Constraint-Löser geschrieben werden, die harte und weiche Constraints gemeinsam behandeln. Diese Erfahrung mit INTERDIP ist die Motivation für den Instituts-Stundenplaners . Derzeit wird der Prototyp INTERDIP bewertet.
Der Prototyp INTERDIP wurde in Zusammenarbeit mit einer Abteilung von Siemens AG erstellt.
INTERDIP aufrufen: http://www.pms.informatik.uni-muenchen.de/~interdip/
Ansprechpartner: Dipl.-Inform. Slim Abdennadher
Der Stundenplaner soll für unser Institut, jeweils ausgehend vom Stundenplan des vorhergehenden Semesters, einen neuen für das kommende Semester erstellen. Dabei stellt die Kontinuität in der Stundenplanung eines der Optimalitätskriterien dar. Mit Papier und Bleistift braucht man leicht einen Tag, um einen Stundenplan zu generieren. Der bereits vorhandene erste Prototyp eines automatischen Stundenplaners reduziert die Berechnungszeit auf wenige Minuten. Der in der Constraint-Sprache CHR implementierte Prototyp unterscheidet zwischen "harten" und "weichen" Constraints. Um die weichen Constraints behandeln zu können, wurde ein Constraint-Löser über endlichen Bereichen so modifiziert, dass jeder Wert im Domain einer Variable mit einer Präferenz vermerkt ist. Die Constraint-Sprache CHR erwies sich zur Behandlung der weichen Constraints aus zwei Gründen als besonders geeignet: Zum einen konnte unter dem Einsatz der Constraint-Sprache CHR die Behandlung der harten und weichen Constraints spezifiziert werden. Zum anderen besteht das CHR-Programm aus nur ca. 20 Zeilen Code.
Den Instituts-Stundenplaner aufrufen: http://www.pms.informatik.uni-muenchen.de/~ifiplan
Ansprechpartner: Dipl.-Inform. Slim Abdennadher
Der in der vorangehenden Anwendung untersuchte Ansatz soll erneut, diesmal zur Erstellung des Lehrplanes eines Gymnasium, angewendet werden. Dabei soll der gleiche empirische Ansatz verfolgt werden: Das System soll interaktiv sein und es soll zwischen unbedingt zu erfüllenden "harten" und nach Möglichkeit zu erfüllenden "weichen" Constraints unterschieden werden. Die neue Anwendung unterscheidet sich von den zwei vorangehenden dadurch, dass auf den Lehrplan des vorherigen Zeitraumes nicht zurückgegriffen werden soll. Statt dessen soll für jeden Zeitraum von null an ein neuer Lehrplan erstellt werden.
Das Vorhaben ist eine Zusammenarbeit mit dem Augsburger Maria-Theresia-Gymnasium.
Ansprechpartner: Dipl.-Inform. Slim Abdennadher und Claus Schmalhofer (Maria-Theresia-Gymnasium, Augsburg)
Lehr- und Forschungseinheit
Institut
Universität