Reboots in lazy-grounding ASP-solving

Abstract

Answer set programming (ASP) is a declarative problem solving approach from the area of knowledge representation and reasoning. It uses logical rules for the purpose of knowledge processing. The state-of-the-art solvers for answer set programs initially, before starting the solving process, perform a grounding phase that potentially leads to an exponential blowup in memory. This effect is called the grounding bottleneck. The lazy-grounding approach interleaves the grounding and solving phases to avoid this grounding bottleneck. In lazy-grounding, rules are grounded incrementally as soon as they are relevant to the solving process. So far the lazy-grounding ASP solver Alpha considers a monotonically growing set of rules obtained from grounding. This potentially leads to ground rules becoming detrimental to the search performance as they are stored and processed for longer than they remain of interest to the search. This thesis proposes a technique, called reboots, that allows the removal of ground rules obtained during the search. Reboots are defined and their correctness is proven formally. Several strategies for the decision when to perform reboots are proposed. Furthermore, reboots and proposed strategies are implemented for the Alpha solver. Experimental results show that, using this technique, larger instances can be solved and performance improvements can be achieved for some problems.