Visualisation and graphical editing of answer sets : the Kara system

Abstract

Diese Diplomarbeit beschäftigt sich mit der Visualisierung von Answer Sets für logische Programme. Answer-Set Programmierung ist ein deklaratives Programmierparadigma aus dem Bereich der logikbasierten künstlichen Intelligenz. Obwohl es in der universitären Forschung eine etablierte Methode darstellt, fehlen noch Entwicklungswerkzeuge, die es als Problemlösungstechnik effizienter einsetzbar machen. Die bereits existierenden Solver berechnen die Answer Sets für ein Answer-Set Programm und geben diese Answer Sets in Form einer Textausgabe am Bildschirm des Programmierers aus. Bei steigender Komplexität der Programme wird meistens auch die Ausgabe der Answer Sets am Bildschirm größer und füllt in der Praxis oftmals mehr als den ganzen Bildschirm aus. Diese Ausgabe ist für den Programmierer selbst nur mehr sehr schwer oder gar nicht mehr überschaubar. In dieser Arbeit wird auf dieses Problem eingegangen und ein Problemlösungsansatz durch eine bestimmte Visualisierungstechnik erarbeitet, der in dem Tool Kara implementiert wird. Das Tool verfolgt die Idee, dass der Benutzer durch das Verfassen eines Visualisierungsprogramms festlegen kann wie ein Answer Set grafisch dargestellt werden soll. Daraus folgt, dass durch die Kombination eines Answer Sets mit dem passenden Visualisierungsprogramm die grafische Darstellung des Answer Sets festgelegt wird, welche einfacher zu interpretieren ist als die direkte Textdarstellung des Solvers. Dadurch ist es nötig, eine Visualisierungssprache festzulegen mit der der Benutzer die Möglichkeit hat seine erhaltenen Answer Sets grafisch darzustellen. Diese Sprache besteht aus vordefinierten, in dieser Diplomarbeit festgelegten Prädikaten, die für Kara eine spezielle Bedeutung haben. Dadurch wird es ermöglicht, dass der Benutzer auf einfache Weise geometrische Formen spezifizieren kann. Das Ergebnis der Kombination eines gegebenen Answer Sets und eines Visualisierungsprogramms ergibt wiederum ein Answer Set, das intern weiterverarbeitet werden kann.<br />Desweiteren bietet Kara auch die Möglichkeit für den Benutzer die Visualisierung grafisch zu bearbeiten. Dadurch können neue Mengen entstehen, die nicht mehr notwendigerweise Answer Sets des gegebenen Answers-Set Programms darstellen. Dies soll einerseits die Fehlersuche für den Benutzer erleichtern und andererseits auch die Möglichkeit bieten, durch das Generieren neuer Answer Sets Testdaten zu erstellen.<br />Da es es sich nach dem grafischen Bearbeiten der Answer Sets nicht mehr um Answer Sets des ursprünglichen Answer-Set Programms handelt, wird dem Benutzer desweiteren die Möglichkeit geboten, die bearbeitete grafische Darstellung auf ein entsprechendes Answer Set des ursprünglichen Answer-Set Programms rückzurechnen. Dies wird im Zuge der Diplomarbeit auf ein Abduktionsproblem zurückgeführt, wodurch ein Abduktionsprogramm erstellt wird, welches wiederum durch einen Solver ausgeführt werden kann und ein Answer Set in der ursprünglichen Kodierung liefert.<br />

This thesis deals with the visualisation of answer sets, which are the output of answer-set programs. Answer-set programming (ASP) is a fully declarative programming paradigm based on logic programming and non-monotonic reasoning. Although ASP is an acknowledged formalism in logic-based artificial intelligence, development tools for supporting the programmer during coding are missing, which could make it more popular in non-academic settings. Several highly performant solvers computing answer sets of an answer-set program exist. A characteristic feature of these solvers is that they return these answer-sets as textual output on the screen. When the complexity of the problems or the input instances rises, the output of the solver often gets larger and is probably too large for the user to be analysed or interpreted. In this thesis, we address this problem by developing an appropriate visualisation system, Kara, for answer sets. By writing a visualisation program, the user has the possibility to define the graphical representation of the answer set. Thus, the combination of an answer set with the corresponding visualisation program defines the visualisation of the answer set, which can then be interpreted much easier than the textual output of the solver. In this thesis, a visualisation language is presented with which the user gets the possibility to specify the graphical representation with ASP itself. The language consists of special predicates dedicated to several shapes and properties of these representations. Using this information of the visualisation program, Kara is able to draw the graphical representation of the answer set. The result of combining a given answer set with a visualisation program written by the user outputs in turn an answer set, which, when executed by a solver, can then be processed further by Kara. The tool Kara also allows the user to edit the visualisation graphically and thus to easily change properties or even graphical objects encoded in the original answer-set program. While editing, the user may generate new sets of atoms referred to as interpretations which are not necessarily answer sets of the original answer-set program. This should ease the debugging process as well and offer the possibility to create new interpretations for test-data generation. Due to the visualisation language, the answer set of the visualisation is in general not an answer set of the original answer-set program. Thus, Kara offers the user the possibility to compute the corresponding interpretation of the original answer-set program from the actual visualisation. The problem of computing the interpretation corresponding to the original program is represented as an abduction problem. This problem is in turn encoded by an abduction program, which-when executed with a solver-outputs the interpretation corresponding to the original program.