Development of High-Performance Systems for Model-based Problem Solving via Answer Set Programming

• Applicant: Professor Dr. Torsten Schaub
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 67090203

Die Antwortmengenprogrammierung ist ein neuartiges Paradigma zur deklarativen Programmierung, das ursprünglich im Gebiet der Wissensrepräsentation und –verarbeitung entwickelt wurde. Dank ihrer attraktiven Kombination aus einer einfachen, gleichzeitig aber ausdrucksstarken Modellierungssprache mit hochperformanten Problemlösungstechniken hat sie mittlerweile auch das Interesse verwandter Gebiete, wie der Bioinformatik, Robotik oder Systemsynthese geweckt. Die Grundidee der Antwortmengenprogrammierung besteht darin, ein Problem als logisches Programm auszudrücken, so dass die Modelle des Programms die Lösungen des ursprünglichen Problems beschreiben. Obwohl ähnlich zu Prolog-Programmen, basiert die Verarbeitung logischer Programme in der Antwortmengenprogrammierung auf modernen Boole’schen Problemlösungstechniken, die im letzten Jahrzehnt auf dem Gebiet des Erfüllbarkeitstestens entscheidend vorangebracht wurden. Das allübergreifende Ziel unseres Forschungsvorhabens ist die Entwicklung hoch-performanter Systeme zur Antwortmengenprogrammierung (ASP), die neue Standards setzen und das Gebiet für die Behandlung praxisrelevanter Anwendungsprobleme attraktiv machen. Beginnend mit der semantischen Charakterisierung haben wir bereits am Anfang der ersten Projektphase diverse neuartige Algorithmen entwickelt, die zur Implementierung verschiedener sequentieller ASP-Systeme — darunter der preisgekrönte ASP-Löser clasp — geführt haben. Die zweite Hälfte der ersten Projektphase wurde durch das Design und die Implementierung verschiedener Strategien zum parallelen ASP-Lösen dominiert. Überdies haben wir in dieser Phase mit der Umsetzung diverser Formen komplexer Schlussweisen begonnen, die für viele Anwendungen von entscheidender Bedeutung sind. Insgesamt wird unser Vorhaben stets von Anwendungen flankiert, die bei der Steuerung und der Validierung des Designs sowie der Implementierung eine wichtige Rolle spielen. All diese Aktivitäten haben zur Etablierung der offenen Plattform potassco.sourceforge.net geführt, über die unsere Systeme weltweite Verbreitung finden. Ihre Popularität wurde nicht zuletzt durch den Gewinn zahlreicher erster Preise bei internationalen Wettbewerben begünstigt. Bisher haben wir somit die theoretischen Grundlagen unseres Projektvorhabens gelegt und anspruchsvolle sequentielle und parallele Problemlösungsplattformen konzipiert und implementiert. Das jetzige Ziel besteht darin, die Leistungsfähigkeit der parallelen Plattform weit über die der seriellen Plattform zu steigern. Das soll nicht nur in Bezug auf Performanz und Robustheit, sondern vielmehr auch hinsichtlich der Mächtigkeit des Lösungsansatzes geschehen. Dafür wollen wir neue parallele Lösungstechniken entwickeln, die das gesamte Spektrum an komplexen ASP-Schlussweisen abdecken. Unser besonderes Interesse gilt dabei Sprachkonstrukten und Schlussweisen, die eine erhöhte Komplexität besitzen sowie der dazugehörigen Implementierung durch mehrere interagierende Lösungsmodule. Diese Hauptaufgabe wird zum einen durch die Weiterentwicklung der grundlegenden Suchverfahren und zum anderen durch infrastrukturelle Verbesserungen und eine kontinuierliche Validierung begleitet, um so die Nachhaltigkeit der von uns zu entwickelnden ASP-Lösungstechnologie zu garantieren.

• DFG Programme: Research Grants