NAVAS

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Toggle side column

NAVAS

Navigation im Lösungsraum von Answer Sets

Durch die kontinuierliche Weiterentwicklung in den letzten Jahren können heute eine Vielzahl anspruchsvoller kombinatorischer Suchprobleme von enormer praktischer Relevanz effizient durch Answer Set Programming (ASP) gelöst werden. Dabei kann es je nach Umfang des zu lösenden Problems sehr rasch zu einer “kombinatorischen Explosion” der Menge von Lösungen kommen. Während moderne ASP Solver problemlos mehrere Millionen von Lösungen in kurzer Zeit berechnen können, stellt dies den Anwender vor ein neues Problem: Wie soll der enorme Lösungsraum gehandhabt und zugänglich gemacht werden? Typischer Weise werden die Answer Sets in beliebiger Reihenfolge ausgegeben. Jedoch sind viele dieser Lösungen sehr ähnlich. In der Praxis sind hingegen oft nur Lösungen von Interesse, die sich hinreichend voneinander unterscheiden, die besondere Eigenschaften aufweisen, oder die einer gegebenen Menge von Lösungen ähnlich sind. Derlei Features werden allerdings bis jetzt noch nicht von ASP Solvern unterstützt. Um eine interaktive und transparente Navigation in ASP-Lösungsräumen zu ermöglichen wird sich das Projekt NAVAS mit den folgenden Themen befassen:

  1. Entwicklung von Methoden zur interaktiven und transparenten Navigation im Lösungsraum der Answer Sets;
  2. Implementierung der Methoden mit effizienten Algorithmen;
  3. Evaluation des Prototyps anhand von Anwendungsfällen aus den Bereichen Konfiguration und Argumentation.

Wir sind zuversichtlich, dass ASP-Technologie durch die in NAVAS erzielten Erkenntnisse, Entwicklungen und Implementierungen auch für eine breitere Masse zugänglicher wird. Hierbei sehen wir ein besonderes unmittelbares Potential im Bereich industrieller Anwendungen, etwa zur Produktkonfiguration.