Towards implementing contrastive explanations for answer-set programs

Abstract

Die Antwortmengenprogrammierung (ASP) ist ein deklaratives logisches Programmierparadigma mit vielen Anwendungen in der Wissensrepräsentation und Künstlichen Intelligenz. Probleme wie, Terminplanung, Klassifikation, Planung oder Produktkonfiguration, werden in ASP als Regeln ausgedrückt. Deren Lösungen werden als Antwortmenge präsentiert, i.e. Mengen von Atomen. Eine besondere Schwierigkeit bei ASP besteht in der Fehlersuche und in der Nachvollziehbarkeit, also warum ein bestimmtes Atom in einer Antwortmenge enthalten ist oder nicht. Kontrastive Erklärungen versuchen zu erläutern, warum ein bestimmtes Ereignis im Gegensatz zu einem anderen aufgetreten ist. Eiter et al. haben kontrastive Erklärungen für ASP formalisiert. Diese Formalisierung bildet den theoretischen Rahmen für diese Masterarbeit. Das Hauptziel dieser Masterarbeit ist es, die praktische Umsetzbarkeit der Anwendung des theoretischen Ansatzes kontrastiver Erklärungen auf ASP zu bestimmen. Zu diesem Zweck wurde ein neues Programm entwickelt, bestehend aus einem naiven Grounder, einem Backend, das den von Eiter et al. gegebenen Definitionen folgt, und einer benutzerfreundlichen Schnittstelle. Das Programm wurde hinsichtlich seiner Leistung durch Tests an bekannten Problemen evaluiert. Die Benutzerfreundlichkeit wurde anhand von Fallstudien beurteilt, die die Benutzeroberfläche des Programms in zwei realistischen Szenarien demonstrierten. Die Ergebnisse der Experimente zeigen, dass der Ansatz bei kleinen bis mittelgroßen Problemen gut funktioniert.

Answer-set programming (ASP) is a declarative logic programming paradigm with many applications in knowledge representation and artificial intelligence. In ASP, problems such as scheduling, classification, planning, or product configuration are encoded as rules. Solutions to these problems are presented as answer sets. An important difficulty for ASP is debugging and understanding why a certain atom is or is not included in an answer set. Contrastive explanations try to explain why a certain event occurred in contrast to another. Eiter et al. formalized contrastive explanations for ASP. This formalization forms the theoretical framework for this Master’s thesis. The main goal of this thesis is to determine the practical feasibility of applying the theoretical approach of contrastive explanations to ASP. To achieve this, a new tool was created, consisting of a naive grounder, a backend, which follows the definitions provided by Eiter et al., and a user-friendly interface. The tool was then evaluated regarding performance by testing it on well known problems. Furthermore, its user-friendliness was evaluated through case studies demonstrating the program’s interface in two realistic scenarios. The results of the experiments show that the approach performs well for small to medium-sized problems.