The top-down evaluation techniques for modular nonmonotonic logic programs

Abstract

Answer Set Programming (ASP) ist ein sehr nützliches Werkzeug für die Wissensrepräsentation und zum Lösen von deklarativen Problemstellungen. In letzter Zeit werden Modularitätsaspekte in ASP zunehmend interessant, bei dem es darum geht, (Sub-)Programme zu einem (kombinierten) Logikprogramm zusammenzusetzen. Modularität erlaubt nicht nur das gegebene Problem in seine Teilprobleme zu zerlegen, sondern erleichtert auch die Wiederverwendbarkeit von logischen Programmen und bietet bessere Unterstützung für große Softwareprojekte. Zu den gegenwärtigen Ansätzen in diesem Bereich zählen Modular Nonmonotonic Logic Programs (MLP), welche einige Stärken aufweisen: Sie erlauben wechselseitige rekursive Aufrufe und nutzen Prädikatensymbole als Modul-Input, wodurch dynamischere Kodierungen der Probleme entstehen.<br />MLPs sind sehr ausdrucksstark und haben eine hohe computationale Komplexität, deswegen ist es sehr anspruchsvoll, eine praktikable Implementierung für diesen Formalismus zu erstellen.<br />In dieser Arbeit entwickeln wir TD-MLP, einen konkreten Algorithmus zur Berechnung von Modellen für MLPs. TD-MLP basiert auf Top-down-Auswertungstechniken, die nur relevante Modulaufrufe berücksichtigen. Wir integrieren eine Optimierungstechnik, die Modulinstanzen separiert und damit redundante Berechnungen vermieden werden. Wir haben diese Optimierungstechnik implementiert und Experimente auf Benchmark Instanzen zeigen vielversprechende Resultate.<br />Darüber hinaus evaluieren wir auch unterschiedliche Kodierungen für Probleme, um modularen und mit einfachen logischen Programmen zu vergleichen. Experimente zeigen, dass in einigen Fällen die modulare Kodierung die gewöhnlichen Programme übertreffen können.<br />

Answer Set Programming (ASP) is a very useful tool for knowledge representation and declarative problem solving. Recently, enabling modularity aspects in ASP has gained increasing interest to help composing (sub-)programs to a combined logic program. Modularity not only allows for problem decomposition, but also facilitates high (code) reusability and provides better support for large-scale projects. Among the contemporary approaches, Modular Nonmonotonic Logic Programs (MLPs) have distinguished strengths, e.g., they allow for mutual recursive calls and utilize predicate symbols as module inputs, resulting in more dynamic problem encodings. MLPs are very expressive and have high computational complexity, thus creating practicable implementations for this formalism is a very challenging task.<br />In this thesis, we develop TD-MLP, a concrete algorithm for computing answer sets for MLPs. TD-MLP is based on a top-down evaluation technique which considers only relevant module calls. In addition, we have devised an optimization technique that splits module instantiations to avoid redundant recomputation. We have incorporated the optimization technique into the original approach and experiments on a benchmark suite show promising results. Furthermore, we also evaluate the performance of different encodings for different problems, involving modular and ordinary encodings. Experiments show in some cases our modular encoding can outperforms the ordinary ones.<br />