Novel techniques for circumventing the ASP Bottleneck

Abstract

Symbolische künstliche Intelligenz ist exakt und zuverlässig. Allerdings verhindern sogenannte combinatorial Explosions das Lösen vieler Industrieprobleme. In dem Logikprogrammierparadigma Answer Set Programming (ASP), kommt dieses Phänomen der combinatorial Explosions häufig in der Grounding Phase vor. Grounding, also das Ersetzen von Variablen durch ihre Domäne, führt zu einem exponentiell größeren Programm. Dieses Problem wird auch Grounding Bottleneck genannt.Die hier vorliegende Diplomarbeit zeichnet sich durch zwei primäre Beiträge zur Lösung des Grounding Bottlenecks aus: (i) Die effektive Kombination zwischen Body-decoupled Grounding (BDG) und (traditionellem) semi-naivem Grounding, und (ii) durch die Weiterentwicklung des BDG-Ansatzes für normale und zyklische Regeln.Im Detail sind die Beiträge wie folgt: (1) Wir führen Hybrid Grounding ein, welches die freie (manuelle) Aufteilung eines Programmes in einen durch traditionelle Techniken und einen durch BDG gegroundeten Teil ermöglicht. (2) Weiters präsentieren wir automated Hybrid Grounding, welches die manuelle Aufteilung unter Verwendung von Heuristiken automatisiert. (3) Auch stellen wir eine verbesserte BDG-Reduktion für normale ASP-Programme vor, welche die Grounding-Zeit von Domänengröße hoch 2 mal Arität (2 * a) auf Domänengröße hoch 1 mal Arität plus 1 (a + 1) reduziert. (4) Schließlich demonstrieren wir durch Lazy-BDG das effektive Grounden von zyklischen Programmen. Hierbei wird der Aufwand, der in der BDG-Grounding Phase anfällt, auf die Lösungsphase über Propagatoren verschoben.Unsere Ergebnisse für (1) und (2) zeigen, dass BDG effizient implementiert und auf eine Weise verwendet werden kann, die orthogonal zu traditionellem Grounding ist. Dies führt zu einer Groundingmethode, die bei schwer lösbaren Problemen weder Effizienzeinbußen noch -steigerungen bewirkt, bei schwer zu grundierenden Problemen jedoch Zugewinne verbuchen kann. Weiterhinzeigen unsere Experimente zu (3) und (4), dass diese Ansätze sehr vielversprechend sind, da wir sowohl traditionelle Grounder, als auch die bisherige BDG-Methode übertreffen.

Symbolic Artificial Intelligence is known for its reliability and exactness. Unfortunately, many symbolic approaches suffer from combinatorial explosions that render industry problems unsolvable. This is especially prevalent in the grounding phase of the logic-programming paradigm Answer Set Programming (ASP). Grounding, replacing variables with their domain, yields an exponentially larger program, the so-called grounding bottleneck. Body-decoupled grounding(BDG), a state-of-the-art method for easing the grounding bottleneck, achieves good results on grounding-heavy scenarios. However, it lacks interoperability with other state-of-the-art methods like semi-naive grounding and performs poorly on normal and non-tight ASP programs.We tackle the challenges of BDG by (i) enabling the interoperability of BDG with semi-naive grounding, by introducing hybrid grounding and automated hybrid grounding, and (ii) advancing the BDG approach for normal and non-tight rules with FastFound and Lazy-BDG.In more detail, we introduce hybrid grounding, which enables the free (manual) partitioning of a program into a part grounded by traditional techniques and a part grounded by BDG. Next, with automated hybrid grounding, we developed heuristics for automatically deciding when a usage of BDG is appropriate. We implemented this approach in our prototype newground3, which we compared experimentally to gringo and idlv. While on solving-heavy benchmarks, the difference in solved instances is less than 1%, newground3 manages to increase the number of solved instances by about 35% on grounding-heavy benchmarks. This leads us to conclude that BDG can be used orthogonally to traditional grounders.Furthermore, we improve the BDG reduction with FastFound, a method that enables a reduction in grounding size from being exponential in 2 times the arity (2 * a) to only being exponential 1 times the arity plus one (a + 1). Lazy-BDG enables the effective grounding of non-tight programs by shifting effort spent in the grounding phase to the solving phase using propagators. Further, we demonstrate the usefulness of FastFound and Lazy-BDG by implementing them in our prototype newground3 and beating both the original BDG formulation and the state-of-the-art grounders gringo and idlv on synthetic benchmarks.