Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen

Das logische Schließen, also das Ableiten von Schlussfolgerungen aus einer Daten- oder Wissensbasis, ist eine fundamentale Aufgabe in der Computer-Wissenschaft. Es hat zahlreiche interessante Anwendungen insbesondere in der Künstlichen Intelligenz wie beispielsweise Antwortmengenprogrammierung, logisches Schließen im Web mit Beschreibungslogiken, Wissensrevision, Abstrakte Argumentation, Diagnose, etc. Diese Bereiche haben in den letzten Jahren ein reges Forschungsinteresse erfahren. Dabei wurden solide theoretische Grundlagen geschaffen und Algorithmen entwickelt, die zumindest theoretisch die gebräuchlichsten Berechnungsaufgaben in diesen Bereichen lösen. Praktisch hat sich aber gezeigt, dass die hohe Komplexität der meisten dieser Aufganben ein gravierendes Hindernis für die Anwendung dieser Algorithmen auf Probleminstanzen realistischer Größe darstellt. Bislang wurde keine befriedigende Lösung für diese hohe Komplexität gefunden. In den letzten Jahren hat sich die parametrisierte Komplexitätstheorie zu einem vielversprechenden Ansatz entwickelt, um mit hoher Komplexität umzugehen. Das vorrangige Ziel einer parametrisierten Komplexitätsanalyse ist es, sogenannte FPT-Fragmente ("fixed-parameter tractable") für harte Probleme zu identifizieren, d.h.: Problemparameter zu identifizieren, die die effiziente Lösung eines harten Problems ermöglichen, vorausgesetzt dass diese Parameter klein sind. Dieser Ansatz wurde in vielen Bereichen der Computer-Wissenschaft erfolgreich eingesetzt vor allem bei harten Problemen in der Graphentheorie. Die Anwendung dieser Techniken auf harte Probleme des logischen Schließens steckt aber noch in den Kinderschuhen. In diesem Projekt wollen wir die erfolgreiche Anwendung von Methoden der parametrisierten Komplexität auf den Bereich der Künstlichen Intelligenz und des logischen Schließens ausdehnen. In erster Linie werden wir daher eine systematische Erforschung von möglichen Problemparametern initiieren und das Potenzial dieser Parameter beim Definieren von effizient lösbaren Fragmenten harter Probleme des logischen Schließens untersuchen. Wir werden dann die Ergebnisse der parametrisierten Komplexitätsanalyse verwenden, um neue, effiziente Algorithmen für Fragmente von harten Problemen des logischen Schließens zu entwickeln und um mögliche Verbesserungen für bestehende Lösungsverfahren dieser Probleme zu identifizieren.

Logisches Schließen ist eine wichtige Aufgabe in der Informatik. Es beschäftigt sich mit der Ableitung von logischen Schlüssen aus einer Daten- oder Wissensbasis. Es hat viele interessante Anwendungen insbesondere in der Künstlichen Intelligenz. Allerdings haben viele Probleme in diesem Bereich eine hohe Komplexität, was ein größeres Hindernis für das Entwickeln von effizienten Algorithmen darstellt. Das Hauptziel dieses Projekts war es, Methoden der parametrisierten Komplexität anzuwenden, um ein tieferes Verständnis dieser Komplexitäten zu bekommen und um neue Algorithmen zu entwickeln, die effizient arbeiten unter der Voraussetzung, dass der Input eine bestimmte Struktur aufweist. Daraus ließen sich zwei Hauptthemen für den Projektplan ableiten: 1. Parametrisierte Komplexitätsanlysen der Rechenprobleme in vielen Gebieten der Künstlichen Intelligenz und des logischen Schließens. 2. Entwicklung neuer, effizienter Algorithmen für diese Rechenprobleme unter Verwendung unterschiedlicher algorithmischer Paradigmen. Die Bereiche, die hier untersucht wurden, umfassen mehrere Untergebiete der Künstlichen Intelligenz und des logischen Schließens wie Logisches Programmieren, Beschreibungs- logiken, das Erfüllbarkeitsproblem der Aussagenlogik, die Behandlung inkonsistenter Daten (die durch Datenänderungen oder das Zusammenführen von widersprüchlichen Wissens- basen entstanden sind), Abduktion, Planungsprobleme und Argumentation. Die algorithmischen Paradigmen, die dabei verwendet wurden, umfassen parametrisierte Algorithmen, Zerlegungsmethoden (die häufig einen Spezialfall von parametrisierten Algorithmen darstellen), Reduktionen von einem Problem auf ein anderes (wie zum Beispiel Reduktionen auf das Erfüllbarkeitsproblem der Aussagenlogik, um die vorhandenen Programme für dieses Problem auf andere Bereiche anzuwenden) und parallele Algorithmen basierend auf verteilten Datenverarbeitungstechniken aus der Big Data Forschung.