Inductive Learning of Declarative Domain-Specific Heuristics for ASP
This addresses the need for automated support in ASP to reduce reliance on expert knowledge, though it is incremental as it builds on existing ILP methods for a specific domain.
The paper tackles the manual invention of domain-specific heuristics in Answer Set Programming (ASP) by introducing an automatic learning approach using Inductive Logic Programming (ILP), which improves solving performance and solution quality for larger problem instances.
Domain-specific heuristics are a crucial technique for the efficient solving of problems that are large or computationally hard. Answer Set Programming (ASP) systems support declarative specifications of domain-specific heuristics to improve solving performance. However, such heuristics must be invented manually so far. Inventing domain-specific heuristics for answer-set programs requires expertise with the domain under consideration and familiarity with ASP syntax, semantics, and solving technology. The process of inventing useful heuristics would highly profit from automatic support. This paper presents a novel approach to the automatic learning of such heuristics. We use Inductive Logic Programming (ILP) to learn declarative domain-specific heuristics from examples stemming from (near-)optimal answer sets of small but representative problem instances. Our experimental results indicate that the learned heuristics can improve solving performance and solution quality when solving larger, harder instances of the same problem.