Optimizing second-level dynamic programming algorithms : the D-FLAT 2 system: encodings and experimental evaluation

Abstract

Für viele bekannte AI-Probleme wurde bereits gezeigt, dass sie - bei beschränkter Baumweite (tree-width) - mit polynomiellen Ressourcen (tractable) lösbar sind. Es wurden diffizile Algorithmen für Baumzerlegungen (tree decompositions, TDs) basierend auf Dynamischer Programmierung (DP) entwickelt, die typischerweise wiederkehrende Muster (zB. Teilmengen-Minimierung) zeigen. Bei der Answer-Set Programmierung (ASP) zB. war oft Saturierung notwendig, um die volle Ausdrucksstärke auszunutzen, was zu entlastenden Ansätzen führte. Diese "Bequemlichkeiten" gibt es bei der DP noch nicht. Daher wird eine neue Methode vorgestellt, um Algorithmen basierend auf DP für TDs zu vereinfachen; im Speziellen wird dadurch Teilmengen-Minimierung (-Maximierung) automatisch durchgeführt. Diese Methode ermöglicht es beispielsweise, einen SAT-Algorithmus (entscheidet über Existenz einer formelerfüllenden Variablenbelegung einer aussagenlogischen Formel) gemeinsam mit einer einfachen Angabe, worüber optimiert wird, in einen Algorithmus für Teilmengen-minimale Modelle zu verwandeln. Leider verbrauchen optimierende DP-Algorithmen für TDs oft viele Ressourcen. Die neue Methode umgeht dieses Problem dadurch, dass die Berechnung nun in zwei Phasen erfolgt. In Phase eins werden Lösungskandidaten ohne Berücksichtigung des Optimierungskriteriums berechnet; danach werden Kandidaten durch Finden von Gegenbeispielen invalidiert. Neben einer Implementierung dieses Ansatzes - genannt D-FLAT 2 - werden Anwendungen gezeigt. Ferner wird ein neuer Algorithmus für die Berechnung von "semi-stable" Mengen (Abstrakte Argumentation) entwickelt. Ergebnisse zeigen, dass D-FLAT 2 einen großen Vorteil - im Vergleich zum einphasigen D-FLAT - mit sich bringt und die Fixed-Paramter-Tractability (FPT) Resultate bezüglich TD mit diesen kompatibel sind. Für viele Probleme tritt die Optimierung annähernd kostenlos auf, d.h. die korrespondierenden Probleme ohne Optimierung brauchen ungefähr gleich viele Ressourcen.

Many problems from the area of AI have been shown tractable for bounded tree-width. In order to put such results into practice, quite involved Dynamic Programming (DP) algorithms on Tree Decompositions (TDs) have to be designed and implemented. These algorithms typically show recurring patterns that call for tasks like subset-minimization. Especially in the world of Answer-Set Programming (ASP), we can witness such a phenomenon: In order to exploit the full expressive power of this paradigm, a particular saturation programming technique is required in order to express co-NP tests. Several approaches for relieving the user from this task have been proposed. Unfortunately, easy-to-use facilities had no analogue in the area of DP so far. In this thesis, we provide a new method for obtaining DP algorithms on TDs from simpler principles, where subset-minimization is performed automatically. For example, given a DP algorithm on TDs for Sat, i.e. the problem whether a propositional formula is satisfiable, our approach makes it possible to use this algorithm, together with simple statements on what to minimize, for finding only subset-minimal models. Making optimization implicit in this way makes the programmer-s life considerably easier. Furthermore, standard DP algorithms on TDs for such problems often suffer from a naive check for subset optimality that requires unnecessarily much space and time. Our method avoids this issue by implicitly proceeding in two stages (instead of one stage in the standard case): First we compute solution candidates without regard to optimization and then we rule out invalid candidates by trying to find counterexamples. Because of its two-phased nature, our approach can do so in an efficient way. We are not aware of any work so far that introduces similar two-phased DP algorithms on TDs along with the appropriate data structures. To underline the practical relevance of our work, we present an implementation of this two-stage algorithm called D-FLAT-2. We illustrate the simplicity of our approach by providing D-FLAT-2 encodings for several AI problems including a new algorithm for semi-stable semantics of Abstract Argumentation. Empirical results indicate a huge performance advantage of D-FLAT-2 compared to using only one stage as in D-FLAT and that the theoretical Fixed-Parameter Tractability (FPT) results w.r.t. tree-width are consistent with our experiments. Furthermore, we gathered that for our tested problems, which are FPT w.r.t. tree-width, it turns out that the optimization is almost for free, i.e. corresponding problems without optimization require about the same time and memory resources.