Answer set programming with external sources : algorithms and efficient evaluation

Abstract

Antwortmengenprogrammierung (answer set programming, kurz ASP) ist ein deklarativer Programmieransatz der in den letzten Jahren stark an Popularität gewonnen hat. Sie ist für zahlreiche Probleme im Bereich der künstlichen Intelligenz gut geeignet, und hat sich dank zahlreicher Spracherweiterungen zu einer reichen Modellierungssprache weiterentwickelt. Während ASP-Systeme bereits für eine Vielzahl von Applikationen im Einsatz sind, fordern neue Trends, beispielsweise im Bereich der verteilten Systeme und dem World Wide Web, den Zugriff aus einem ASP-Programm auf externe Quellen, wie etwa XML- oder RDF- Dokumente, relationale Datenbanken, oder Formalismen aus dem Bereich der Wissensrepräsentation und -verarbeitung, beispielsweise Beschreibungslogiken (description logics). Zu diesem Zweck wurden HEX-Programme entwickelt, die sich als Generalisierung und Erweiterung von ASP verstehen, und die die Anknüpfung von externen Quellen an das ASP-System erlauben. Dies wird über sogenannte externe Atome (external atoms) erreicht, deren Wahrheitswert nicht im logischen Programm bestimmt, sondern von einer Hintergrundtheorie eingespeist wird, als Plugin in das ASP-System eingehängt wird. Der ursprüngliche Ansatz zur Auswertung von HEX-Programmen verwendet eine Übersetzung in gewöhnliche ASP-Programme. Externe Atome werden dabei durch gewöhnliche Atome ersetzt, deren Wahrheitswert nichtdeterministisch geraten wird. Das entstehende Programm kann von herkömmlichen ASP-Systemen ausgewertet werden. Anschließend wird jeder so gewonnene Modellkandidat auf seine Kompatibilität mit der Semantik der externen Quellen getestet und gegebenenfalls verworfen. Zwar ist dieser Ansatz elegant und natürlich, er skaliert aber schlecht für mittelgroße und größere Anwendungen. Außerdem erfordert diese Vorgehensweise die Einhaltung von sehr restriktiven syntaktischen Bedingungen, durch die die Ausdrucksstärke der Sprache eingeschränkt wird. Daher ist das Hauptziel dieser Dissertation die Entwicklung von neuen Evaluierungsalgorithmen für HEX-Programme, die externe Atome von Anfang an als solche behandeln und in die Berechnungen miteinbeziehen. Dadurch soll sowohl die Skalierbarkeit als auch die Ausducksstärke erhöht werden. Die Arbeit setzt sich aus zwei Hauptteilen zusammen. Im ersten Teil beschäftigen wir uns mit Algorithmen für variablenfreie HEX-Programme. Konflikt-getriebene Techniken (conflict-driven techniques) sind ein wichtiger Grundstein für unsere Algorithmen, müssen dazu aber von ASP auf HEX-Programme erweitert werden und externe Atome berücksichtigen. Es hat sich dabei auch herausgestellt, dass der Minimalitätscheck für Modellkandidaten eine wesentliche Rolle spielt, da er einen Großteil des gesamten Rechenaufwands verursacht. Deswegen werden wir uns in einem weiteren Schritt auch damit beschäftigen und neuartige Algorithmen zur Sicherung der Minimalität von Modellen präsentieren. Der zweite Teil der Arbeit befasst sich mit HEX-Programmen mit Variablen, und insbesondere mit Domänenerweiterung durch externe Quellen (value invention). Darunter versteht man das Hinzufügen von neuen Konstanten durch externe Quellen, die im ursprünglichen Programm nicht vorkommen. Im bisherigen Ansatz wird dies durch starke syntaktische Einschränkungen so weit beschränkt, dass das Programm mit den in ASP üblichen Methoden in ein variablenfreies Programm übersetzt werden kann. Da dies jedoch auch den Freiraum bei der Modellierung einschränkt, sollen die syntaktischen Einschränkungen gelockert werden, wenn immer das möglich ist. Der praktische Teil der Arbeit beschäftigt sich mit der Implementierung der neuen Methoden und Algorithmen in unserem Prototypsystem DLVHEX . Damit werden wir unsere Algorithmen auch empirischen Experimenten unterziehen, die zeigen, dass damit eine deutlich bessere Skalierbarkeit erreicht wird, und dass die Modellierungssprache nun deutlich weniger Einschränkungen unterliegt. Dies soll dazu beitragen, HEX zu einem praktisch nutzbaren Formalismus weiterzuentwickeln. Abschließend betrachten wir einige Anwendungen und Erweiterungen von HEX -Programmen, wobei der Fokus auf jenen Anwendungen liegt, die im Zuge dieser Arbeit neu entstanden sind oder wesentlich erweitert wurden.

Answer set programming (ASP) is a declarative programming approach which has gained in- creasing attention in the last years. It is useful for many tasks in artificial intelligence, and many language extensions have advanced the paradigm into a strong modeling language. While the ASP programming paradigm has proved to be fruitful for a range of applications, current trends in distributed systems and the World Wide Web, for instance, revealed the need for access to external sources in a program, ranging from light-weight data access (e.g., XML, RDF, or relational data bases) to knowledge-intensive formalisms (e.g., description logics). To this end, HEX-programs are an extension and generalization of answer set programs by external sources which can be tightly coupled to the reasoner. This is realized by external atoms, whose truth value is not determined within the logic program, but by a background theory, which is technically realized as a plugin to the reasoner. The traditional evaluation algorithm for HEX-programs uses a translation approach which rewrites them to ordinary ASP programs. The fundamental idea is to replace external atoms by ordinary ones whose truth values are guessed. The resulting program is then evaluated by a state-of-the-art ASP solver. The resulting model candidates are subsequently checked for compliance with the external sources, and are discarded if the guesses value differs from the real truth value. While this approach is intuitive and natural, it turned out to be a bottleneck in advanced applications. It does not scale well, as the number of candidate answer sets grows exponentially with the number of external atoms in the program. Moreover, the traditional algorithms also impose very strong syntactic safety conditions on the input program, which restricts the language. This motivates the development of novel evaluation algorithms for HEX- programs, which treat external atoms as first-class citizens and build models from first principles; it is expected that this increases scalability and expressiveness. The thesis consists of two major parts. In the first part, we present new algorithms for ground HEX-programs, i.e., programs without variables. Conflict-driven learning techniques will be an important basis for our algorithms, but need to be extended from ordinary ASP solving to HEX-programs. Moreover, minimality checking for model candidates of HEX-programs turned out to be an interesting topic because it causes the major part of the computational costs. Hence, new minimality checking methods will be developed and integrated into the overall evaluation algorithms. The second part is concerned with HEX-programs with variables in general, and with value invention in particular, i.e., the introduction of new constants by external sources, which do not show up in the input program. Traditionally, value invention is restricted by syntactic conditions such that grounding algorithms for ASP programs without external sources are applicable. However, this restricts the expressiveness of the language. Thus the syntactic restrictions shall be relaxed whenever possible, which also requires the development of a new grounding algorithm. The practical part of this thesis deals with the implementation of the new methods and algorithms in our prototype system DLVHEX . We will analyze and evaluate our work by empirical experiments, and show that the new algorithms provide a much better scalability and richer modeling language, which helps establishing HEX as a practical knowledge representation formalism. We then take a look at some practical applications and extensions of HEX-programs, with focus on those domains which newly emerged or have been significantly extended during the work on this thesis.