Loading…
Asynchrones Constraintlösen
Ein generisches Ausführungsmodell zur adaptiven, inkrementellen Constraintverarbeitung
Ringwelski, Georg
Constraint Satisfaction Probleme (CSP) bestehen aus einer Menge von Randbedingungen (Constraints), die einen gesuchten Lösungszustand beschreiben. Das Lösen von CSP, also das finden von Konfigurationen, in denen alle Randbedingungen erfüllt sind, ist ein aktuelles Forschungsgebiet mit vielen Anwendungsfeldern in Wirtschaft, Technik und dem alltäglichen Leben. CSP sind NP-vollständig, so daß in der Künstlichen Intelligenz nach Verfahren gesucht wird, die trotz des erforderlichen Nichtdeterminismus schnell genug für ihr jeweiliges Anwendungsgebiet eine oder mehrere Lösungen finden. In der Dissertation wird ein Ausführungsmodell definiert und verifiziert, das den Einsatz solcher effizienten Verfahren zum Lösen realer Problem erlaubt. Dieses Ausführungsmodell, das Asnychrone Constrainlösen (ACS), beschreibt, wie man Constraintlöser und Constraints für konkete Anwendungsgebiete erstellt und welche Ergebnisse dort berechnet werden können. ACS erlaubt, im Gegensatz zum Stand der Technik, auch das dynamische Hinzufügen und Zurücknehmen von Constraints während des Lösungsprozesses. Diese adaptive Constraintverarbeitung unterstützt die Verwendung Constraint-basierte Techniken in interaktiven und kontinuierlichen Softwaresystemen, die zuvor wegen der technischen Einschränkungen der erhältlichen Systeme kaum bearbeitbar waren, obwohl sie vom deklarativen Standpunkt aus oft sehr gut als CSP formuliert werden können. Desweiteren ist das Ausführungsmodell so konzipiert, daß es zur Verarbeitung von Constraints in verteilten und nebenläufigen Systemen geeignet ist. Auch für diesen immens an Bedeutung gewinnenden Anwendungsbereich waren zuvor nur sehr restriktive Ausführungsmodelle bekannt. In der Arbeit wird das ACS Modell und eine prototypische Implementierung vorgestellt, so daß sich neben den theoretischen Eigenschaften auch die Eignung für praktische Probleme zeigen lies.
