Domain-specific heuristics are a crucial technique for the eficient 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 ifrst step in this direction. 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 improve solving performance and solution quality when solving larger, harder problem instances.
Answer Set Programming (ASP) [
Therefore, state-of-the-art ASP systems ofer ways to integrate domain-specific heuristics
in the solving process. An extension for wasp [
However, such heuristics must be invented manually so far. Human domain experts and ASP experts are needed to invent suitable domain-specific heuristics. This paper presents a first step toward the automatic learning of declarative heuristics.
Our core idea is to 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. These heuristics can then be used to improve solving performance and solution quality for larger, harder problem instances. Our experimental results are promising, indicating that this goal can be achieved. t3 t1 t2 t4 t5
After covering preliminaries in Section 2, we present our main contribution in Section 3. Section 4 presents experimental results, and Section 5 describes related work. Section 6 concludes the paper by giving an outlook on future work.
In this section, we introduce a running example and cover preliminaries on domain-specific
heuristics in ASP and inductive learning in ASP. We assume familiarity with ASP and refer to
[
Formally, HRP is defined as a modification of the House Configuration Problem (HCP) [13]. Definition 1 (HCP). The input for the House Configuration Problem (HCP) is given by four sets of constants , , , and representing persons, things, cabinets, and rooms, respectively, and an ownership relation PT ⊆ × between persons and things.
The task is to find an assignment of things to cabinets TC ⊆ × and cabinets to rooms CR ⊆ × such that: (1) each thing is stored in a cabinet; (2) a cabinet contains at most five things; (3) every cabinet is placed in a room; (4) a room contains at most four cabinets; and (5) a room may only contain cabinets storing things of one person.
Definition 2 (HRP). The input for the House Reconfiguration Problem (HRP) is given by an HCP instance = ⟨, , , , ⟩, a legacy configuration ⟨TC ′, CR′⟩, and a set of things ′ ⊆ that are defined as “long” (all other things are “short”).
The task is then to find an assignment of things to cabinets TC ⊆ × and cabinets to rooms CR ⊆ × , that satisfies all requirements of HCP as well as the following ones: (1) a cabinet is either small or high; (2) a long thing can only be put into a high cabinet; (3) a small cabinet occupies 1 and a high cabinet 2 of 4 slots available in a room; (4) all legacy cabinets are small.
The sample HRP instance shown in Fig. 1 comprises two cabinets, two rooms, five things belonging to person p1, and one thing belonging to person p2. A legacy configuration is empty,
and all things are small. In a solution, the first person’s things are placed in cabinet c1 in the ifrst room, and the thing of the second person is in cabinet c2 in the second room. For this sample instance, a solution of HRP corresponds to a solution of HCP [13].
Instances consist of facts over the following predicates: cabinetDomainNew/1 defines potential cabinets, and roomDomainNew/1 defines potential rooms; thingLong/1 defines which things are long; and legacyConfig/1 defines all the other data in the legacy configuration, e.g., legacyConfig(personTOthing(p1,t1)) defines that person p1 owns thing t1, and legacyConfig(roomTOcabinet(r1,c1)) specifies one tuple in the legacy assignment of cabinets to rooms.
The main two choice rules guessing the assignment of things to cabinets and the assignment of cabinets to rooms look as follows: { cabinetTOthing(C,T) } :- cabinetDomain(C), thing(T).
{ roomTOcabinet(R,C) } :- roomDomain(R), cabinet(C).
To define the domains of cabinets and rooms as the union of existing objects and newly available identifiers, the encoding also contains the following rules: cabinetDomain(C) :- cabinetDomainNew(C).
roomDomain(R) :- roomDomainNew(R).
Instances may optionally include atoms of various predicates to define costs for specific actions such as placing a thing in a cabinet, placing a cabinet in a room, reusing an existing placement of a thing in a cabinet, reusing an existing placement of a cabinet in a room, removing a thing from a cabinet, removing a cabinet from a room, etc. These costs are then determined based on the diference between solution ⟨TC , CR⟩ and legacy configuration ⟨TC ′, CR′⟩. A weak constraint in the encoding instructs the solver to minimise the costs.
Each available instance belongs to one of four instance classes [15, 16]: Empty (“ec”, empty legacy configuration); long (“lt”, some things are long); new room (“nr”, some cabinets have to be reallocated to new rooms); and swap (“ss”, only one person and a specific pattern of legacy configuration).
To solve large instances of industrial problems, employing an ASP solver out-of-the-box may not be suficient. Sophisticated encodings or solver tuning methods (such as portfolio solving) are common ways to deal with this issue.
Domain-specific heuristics are another way to speed-up answer set solving. They were even
needed to achieve breakthroughs in solving industrial configuration problems with ASP [
Several approaches have been proposed to embed heuristic knowledge into the ASP solving
process. hwasp [
A declarative approach to formulating domain-specific heuristics in ASP is provided by
clingo,2 supporting #heuristic directives [
In the syntax for (non-ground) heuristic directives in clingo (1), ha is an atom, hB is a
conjunction of literals representing the heuristic body, and , , and are terms [
A new approach implemented in the lazy-grounding ASP system Alpha, based on the clingo
approach, has introduced novel semantics for heuristic directives aimed at non-monotonic
heuristics [
Inductive Logic Programming (ILP) is an approach to learning a program that explains a set of examples given some background knowledge. ilasp [17, 18] is a system capable of learning Answer Set Programs, including normal rules, choice rules, and hard and weak constraints.
ilasp operates on a learning task, which consists of three components [17]: The background knowledge (an ASP program already known before learning), the mode bias (that expresses which ASP programs can be learned), and the examples (which specify properties the learned program must satisfy). When the properties specified by a particular example in are satisfied, the example is said to be covered.
ilasp finds a program (often called a hypothesis) such that ∪ covers every example in (or, if the examples are considered noisy, such that the total penalty of non-covered examples is minimised) [17]. is an element of the search space defined by . 2.3.1. Mode Bias The mode bias consists of a set of mode declarations. There are several types of mode declarations [19], two of which we will use in this paper: #modeh and #modeb specify what the heads and bodies of learned rules may look like, respectively. A placeholder is a term var(t) or const(t) for some constant term t. Such placeholders can be replaced by any variable or constant (respectively) of type t.
As a simple example, Listing 1 shows part of the mode bias for a learning task for the HRP.
#modeh(cabinetTOthing(var(cabinet),var(thing))). #modeb(cabinetDomainNew(var(cabinet))). #modeb(thing(var(thing))).
The first mode declaration specifies that the binary predicate cabinetTOthing can be used in the head of rules and that its terms are of variable types cabinet and thing (in this order). The other two mode declarations specify which predicates can occur in the bodies of learned rules. Note that the same terms may be used in learned rules wherever the same term types are used.
Thus, the rule space defined by the mode bias given in Listing 1 consists of the following rule: cabinetTOthing(V1,V2) :- cabinetDomainNew(V1), thing(V2). 2.3.2. Examples A positive example is given by a #pos statement, and a negative example by a #neg statement [17, 19]. Each example consists of several components, the following of which are relevant for this paper:3 A set of ground atoms called inclusions, a set of ground atoms called exclusions, and an optional set of rules (usually just facts) called context.
A positive example is covered if there exists at least one answer set for ∪ that contains all of the inclusions and none of the exclusions. A negative example states that there must not exist an answer set that contains all of its inclusions and none of its exclusions [17, 19].
The context is the problem instance to which the inclusions and exclusions refer (considering the usual distinction between unvarying problem encoding and problem instances specified by facts) [17, 19].
Listing 2 shows a simplified example for HRP stating that cabinetTOthing(1,2) shall be true for the problem instance in which cabinetDomainNew(1) and thing(2) are true.
Listing 2: A simplified example in a learning task for HRP #pos( { cabinetTOthing(1,2) }, % inclusions { }, % exclusions { cabinetDomainNew(1). thing(2). } % context ). 3. Inductive Learning of Domain-Specific Heuristics This section presents the main contribution of this paper—our approach to the inductive learning of domain-specific heuristics for ASP.
The basic idea is to solve a small but representative instance of a problem, use the resulting answer set as a positive example for inductive learning, learn a set of definite rules, and transform the learned rules into declarative heuristic directives in the form of Eq. (1) presented in Section 2.2. These heuristics can then be used to speed up solving larger/harder instances of the same problem.
The rule space for ilasp is defined as follows in our approach: 3So far, we do not use example identifiers, ordering examples, and noisy examples.
• All predicates appearing in the heads of choice rules4 can be used in the heads of learned rules (#modeh). • All (other) predicates appearing in the original program can be used in the bodies of learned rules (#modeb). • The same variable type is used several times, wherever a variable denotes the same real-world concept.
The background knowledge is the original program without any instance.5 Choice rules were not included, however, because we observed that ilasp only learns anything in our example domain when choice rules are not part of the background knowledge. We presume this is because we need to abstract away from the complete problem specification a bit to learn part of the missing information. Constraints were also not included because the rules we want to learn don’t have to satisfy all constraints of the program. When used as heuristics, it sufices for them to give a general indication of what decisions might be useful during solving, even if some of these decisions will have to be backtracked.
As a positive example for learning, one answer set for a small but representative problem instance is used. In case the underlying problem is an optimisation problem (like the HRP described in Section 2.1), we propose to use a (near-)optimal answer set for this process. The (yet unproven) hypothesis is that learning from better answer sets yields better heuristics.
We use context-dependent examples; the context is given by the problem instance. The set of inclusions corresponds to the whole answer set, and the set of exclusions is empty.
Let us re-consider the running example from Section 2.1, the House Reconfiguration Problem
(HRP). The smallest instance is called “ec-0001-house-t0100”; it is an HCP instance (i.e., it
does not contain a legacy configuration) 6 and contains 100 things distributed among 20 persons.
A near-optimal7 answer set for this instance was computed by clingo [
We built a learning task for this simple instance as described at the beginning of Section 3. The entire mode bias is shown in Listing 3. Some predicates that we did not expect to be useful were not included in the mode bias to keep the search space in a feasible range and thus improve ilasp’s solving performance. Some other predicates were removed since they led to learning rules that did not make sense in the domain context. 4More strictly speaking, the head of a choice rule contains a collection of choice elements, each of the form : 1, . . . , [20]. The predicates used for are the ones that can be used in the heads of learned rules. 5Rules involving aggregates had to be removed because they are not supported by ilasp. See https://doc.ilasp.com/ specification/background.html for details on the syntax for the background knowledge. 6Since an HCP instance is not representative of HRP instances with non-empty legacy configuration, future work should address learning from small instances of non-HCP instance classes. 7clingo v. 5.4.0, which was used in its default configuration (i.e., with no parameters apart from file names) computed an answer set with optimisation value 120, but was not able to prove optimality within several days of search.
Listing 3: Full mode bias for HRP as used for our experiments #modeh(cabinet(var(cabinet))). #modeh(room(var(room))). #modeh(cabinetTOthing(var(cabinet),var(thing))). #modeh(roomTOcabinet(var(room),var(cabinet))). #modeh(cabinetHigh(var(cabinet))). #modeh(cabinetSmall(var(cabinet))). #modeb(cabinetDomainNew(var(cabinet))). #modeb(roomDomainNew(var(room))). #modeb(cabinetDomain(var(cabinet))). #modeb(roomDomain(var(room))). #modeb(thing(var(thing))). #modeb(personTOthing(var(person),var(thing))). #modeb(legacyConfig(person(var(person)))). #modeb(legacyConfig(thing(var(thing)))). #modeb(legacyConfig(personTOthing(var(person),var(thing)))). #modeb(thingShort(var(thing))). #modeb(person(var(person))). #modeb(personTOroom(var(person),var(room))).
ilasp was used with arguments --version=2i --no-constraints --no-aggregates, i.e., with version 2i of the learning algorithm and omitting constraints and aggregates (choice rules) from the search space. We chose version 2i instead of version 4 for performance reasons. ilasp 2i needed approximately 4 minutes to solve the full learning task on the author’s personal computer, while ilasp 4 needed over 12 minutes and yielded a slightly diferent result. 8 As an alternative approach, ilasp 4 was able to solve the learning task within seconds when we cut down the instance by removing parts of the facts while still keeping the general structure of the instance.
The following rules form the learned hypothesis:9 cabinetSmall(V1) :- cabinetDomainNew(V1). cabinetTOthing(V1,V2) :- cabinetDomain(V1),
legacyConfig(personTOthing(V3,V2)).
roomTOcabinet(V1,V2) :- cabinetDomain(V2), roomDomain(V1).
As a next step, we transformed these rules to heuristics in the form of Eq. (1) manually by using the head of each rule as ha and the body as hB . Since the heads of the heuristics shall eventually become true, we use the modifier true. And since we don’t have any information on prioritising the heuristics at this point, all get the same weight 1. This is the result: #heuristic cabinetSmall(V1) :
cabinetDomainNew(V1). [1,true] #heuristic cabinetTOthing(V1,V2) :
cabinetDomain(V1), legacyConfig(personTOthing(V3,V2)). [1,true] #heuristic roomTOcabinet(V1,V2) :
cabinetDomain(V2), roomDomain(V1). [1,true]
8When using ilasp 4 instead of ilasp 2i, the third rule in the learned hypothesis contains the atom
roomDomainNew(V1) instead of roomDomain(V1).
9Note that in ilasp’s output, body literals are separated by semicolons instead of the usual commas, which is valid
gringo syntax [
The learned heuristics instruct the solver to try and create as many small cabinets as possible and to try all possible cabinet-to-thing and room-to-cabinet assignments.
Our construction of the mode bias was a bit ad hoc, as described above, aiming at a feasible size of the search space and learning reasonable rules. Finding a meaningful, consistent way to derive the mode bias is subject of future work.
We also want to explore if and how yet unused features of ilasp can be helpful in our approach. This includes learning non-normal rules and weak constraints, multiple examples, exclusions, noise, and using built-in predicates such as arithmetic comparisons in #modeb.
Potential extensions of our approach that should be addressed include assigning variable types automatically and determining diferent weights and priorities for the learned heuristic directives.
To test the efects of the learned heuristics, we used clingo to solve all available HRP instances (94 in number) with and without the learned heuristics. The HRP instances stem from previous experiments [13, 14]. These instances were generated in the pattern of the original instances [15]. This pattern represents four diferent reconfiguration scenarios encountered in practice, and the instances are abstracted real-world instances. Our instances are considerably larger than the original ones, though (ranging up to 800 things, while the original instances used at most 280 things).
Each of the machines used to run the experiments was equipped with two Intel® Xeon® E52650 v4 @ 2.20GHz CPUs with 12 cores. Furthermore, each machine had 251 GiB of memory and ran Ubuntu 16.04.1 LTS Linux. Scheduling of benchmarks was done with HTCondor™ together with the ABC Benchmarking System [21].10 pyrunlim11 was used to limit time consumption to 10 minutes per instance, memory to 40 GiB, and swapping to 0. Care was taken to avoid side efects between CPUs, e.g., by requesting exclusive access to an entire machine for each benchmark from HTCondor.
clingo was instructed to search for the optimal answer set in its default configuration, given an encoding including a weak constraint. Since the system operated only on a single encoding containing the learned heuristics, the parameter --heu=Domain was used to achieve one configuration in which clingo used the domain-specific heuristics (and one in which it did not). After 10 minutes per instance, search was aborted and the optimisation value of the best solution found so far was recorded.
Table 1 shows the achieved optimisation values and the relative improvement when using the learned heuristics for all 36 instances that could be solved with or without domain-specific heuristics. For the other 58 instances, no answer set could be found either way; therefore, they are not included in the table. 10http://research.cs.wisc.edu/htcondor, https://github.com/credl/abcbenchmarking 11https://alviano.com/software/pyrunlim/
The first column shows the instance identifier. The first two characters of each identifier refer to one of the four instance classes of the HRP (cf. Section 2.1). The numeric part of the identifier increases with increasing instance size.
The second and third columns contain the achieved optimisation values without and with learned heuristics, respectively. The symbol ∞ is used when no answer set could be found within the time limit of 10 minutes.
The fourth column shows the change in the optimisation value when using the learned heuristics relative to solving without domain-specific heuristics. A positive percentage signifies an improvement, and negative values indicate a deterioration. The value 100% is used in cases where an answer set could be found only when using heuristics12 and the value −∞ is used when an answer set could be found only without heuristics.
The learned heuristics seem to have positive efects even though they are (still) straightfor12The rationale for this is that the optimisation value of a minimisation problem can be considered infinitely high when no solution is found, and that dividing an infinitely high value by an infinitely high value approaches 1. ward. The average cost improvement over all instances (excluding those where no answer set could be found when using heuristics) is 38%. However, improvement varies strongly between diferent instances. Furthermore, results are sensitive to the chosen time-out. For example, we observed stronger improvements (on fewer solved instances) when experimenting with a time-out of three minutes instead of ten.
Besides our experiments with clingo, we also experimented with the lazy-grounding ASP
system Alpha [
Balduccini [22] has also presented an approach to learning domain-specific heuristics ofline from representative instances. The basic idea, which is very diferent to our approach, is to record which choices are made in the path of a search tree that led to a solution and to use this information to compute probabilities for decisions on ground atoms. These probabilities are then used while solving other problem instances to reduce the likelihood of backtracks. The approach is restricted to DPLL-style solvers like smodels [23], and extending it to CDCL-based systems like clingo is mentioned as future work.
A similar approach is aimed at configuration problems encoded as constraint satisfaction problems (CSPs) [24].
We have proposed a novel approach to inductively learning declarative specifications of domainspecific heuristics for ASP from answer sets of small but representative instances. Our approach employs the inductive learning system ilasp. Utilising an example representing a significant real-world configuration problem, we have demonstrated that simple heuristics can easily be learned.
Experimental results are promising: Some instances could be solved only using the learned heuristics, and solution quality improved considerably on average.
The fact that so far, we have only learned very simple heuristics and those already led to significant improvements is encouraging. Future work will show whether our method can be extended to learn more complex heuristics that can improve solving performance and solution quality even further.
The author is grateful to Mark Law for helping with using ilasp, and to the TU Wien for providing access to computational resources for running the experiments. 13Human-made heuristics, however, enable Alpha to solve up to 59 of these instances [13, 14]. 2019, volume 306 of EPTCS, 2019, pp. 22–35. doi:10.4204/EPTCS.306.9. [13] R. Taupe, G. Friedrich, K. Schekotihin, A. Weinzierl, Solving configuration problems with ASP and declarative domain-specific heuristics, in: M. Aldanondo, A. A. Falkner, A. Felfernig, M. Stettinger (Eds.), Proceedings of the 23rd International Configuration Workshop (CWS/Conf WS 2021), Vienna, Austria, 16-17 September, 2021, volume 2945 of CEUR Workshop Proceedings, CEUR-WS.org, 2021, pp. 13–20. URL: http://ceur-ws.org/ Vol-2945/21-RT-Conf WS21_paper_4.pdf. [14] R. Comploi-Taupe, Speeding Up Lazy-Grounding Answer Set Solving, Ph.D. thesis, AlpenAdria-Universität Klagenfurt, 2021. URL: https://digital.obvsg.at/urn/urn:nbn:at:at-ubk: 1-41351. [15] G. Friedrich, A. Ryabokon, A. A. Falkner, A. Haselböck, G. Schenner, H. Schreiner, (Re)configuration using answer set programming, in: K. M. Shchekotykhin, D. Jannach, M. Zanker (Eds.), Proceedings of the IJCAI 2011 Workshop on Configuration, Barcelona, Spain, July 16, 2011, volume 755 of CEUR Workshop Proceedings, CEUR-WS.org, 2011, pp. 17–24. URL: http://ceur-ws.org/Vol-755/paper03.pdf. [16] A. Ryabokon, Knowledge-based (Re)configuration of Complex Products and Services, Ph.D. thesis, Alpen-Adria-Universität Klagenfurt, 2015. URL: http://netlibrary.aau.at/urn:nbn:at: at-ubk:1-26431. [17] M. Law, A. Russo, K. Broda, The ILASP system for inductive learning of answer set programs, CoRR abs/2005.00904 (2020). arXiv:2005.00904. [18] M. Law, Conflict-driven inductive logic programming, Theory and Practice of Logic
Programming (2022). doi:10.1017/S1471068422000011. [19] ILASP Limited, The ILASP manual, 2022. URL: https://doc.ilasp.com/. [20] F. Calimeri, W. Faber, M. Gebser, G. Ianni, R. Kaminski, T. Krennwallner, N. Leone, M. Maratea, F. Ricca, T. Schaub, ASP-Core-2 input language format, Theory Pract.
Log. Program. 20 (2020) 294–309. doi:10.1017/S1471068419000450. [21] C. Redl, Automated benchmarking of KR-systems, in: S. Bistarelli, A. Formisano, M. Maratea (Eds.), Proceedings of the 23rd RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion 2016 (RCRA 2016), Genova, Italy, November 28, 2016, volume 1745 of CEUR Workshop Proceedings, CEUR-WS.org, 2016, pp. 45–56. URL: http://ceur-ws.org/Vol-1745/paper4.pdf. [22] M. Balduccini, Learning and using domain-specific heuristics in ASP solvers, AI Commun.
24 (2011) 147–164. doi:10.3233/AIC-2011-0493. [23] T. Syrjänen, I. Niemelä, The smodels system, in: T. Eiter, W. Faber, M. Truszczynski (Eds.), Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings, volume 2173 of Lecture Notes in Computer Science, Springer, 2001, pp. 434–438. doi:10.1007/3-540-45402-0_38. [24] D. Jannach, Toward automatically learned search heuristics for CSP-encoded configuration problems – results from an initial experimental analysis, in: Configuration Workshop, 2013, pp. 9–13.