First-order logic has been applied successfully to real-world configuration problems through Answer Set Programming (ASP). To extend the application scope of ASP, lazy grounding and domain-specific heuristics were introduced. Domain-specific heuristics support the problem solver in selecting choices aiming at minimizing the search efort. Dynamic heuristics exploit the current state of the problem-solving process and assign priorities to choices. Depending on the domain, heuristics must be formulated which reason about the properties of sets of atoms. E.g., how many components are connected to a particular type of component, or what is the current sum/maximum/minimum of a physical quantity (power, voltage, current, etc.) of a particular subconfiguration? For expressing such queries, ASP ofers aggregates. The semantics of these aggregates are defined w.r.t. a complete solution. However, in dynamic heuristics, the problem solver has to reason about partial solving states. In this paper, we extend heuristics in ASP with dynamic aggregates and show their implementation as well as efectiveness.
knowledge-based configuration, answer set programming, heuristics tems interleave grounding and solving to instantiate and come the grounding bottleneck, lazy grounding ASP sys- their value cannot change during solving. For our rack configuration example, this semantics implies that the store only relevant parts of the ground program in mem- power consumption of a rack can only be determined if
The work in [6] extends existing approaches by (1) in- board assignments to a rack are not completed. ory. The second performance-related issue is tackled by modern solvers using various techniques, among which domain-specific heuristics play a central role.
namic heuristics to steer the reasoning process depending on the current state of problem-solving.
a brief introduction to ASP and lazy grounding. Section 3 fully to a variety of industrial problems [2] such as con- represented by a partial assignment of truth values to solver (e.g., backtracking search) to generate solutions. equipment, an efective heuristic for problem-solving can
knowledge representation and reasoning framework based on first-order logic that has been applied successifguration [ 3]. Current ASP solvers transform first-order descriptions of problem instances into propositional logic (called grounding) and apply a propositional problem However, applications manifested two issues with the ground-and-solve approach. The first issue is the socalled grounding bottleneck: Large problem instances cannot be grounded by modern grounders like gringo [4] in acceptable time and space. The second issue is that, even if the problem can be grounded, computation of answer sets might take considerable time, as indicated by ASP competition reports [5].
Both issues were recently addressed. First, to overtroducing dynamic heuristics and (2) their exploitation in a lazy-grounding ASP system. The ASP system extended by this approach is Alpha [7], the most actively developed lazy-grounding system available. Dynamic heuristics allow reasoning about the current problem-solving state some (but not all) atoms of a logical specification.
This reasoning may require the application of aggregation. E.g., during the configuration process of electronic say: Given the current state of problem-solving, select the most power-hungry, currently unconnected electronic board, and connect this board to the rack with minimal power consumption (i.e., the rack for which the total power consumption of all boards currently connected is minimal).
However, state-of-the-art ASP aggregates are evaluated only w.r.t. a complete assignment of truth values, i.e., only if every atom (proposition) is true or false, so that provides a driving example and introduces dynamic ag- 2.2. Semantics gregates informally. In Section 4, we present the syntax and semantics of dynamic aggregates. Section 5 shows the implementation and integration of dynamic aggregates using a query-driven approach. Finally, in Section 6, we present the results of our evaluation.
Given a program , the Herbrand universe of , denoted by , consists of all integers and of all ground terms constructible from constant symbols and function symbols appearing in . The Herbrand base of , denoted by , is the set of all ground classical atoms that can be built by combining predicates appearing in with terms from
A substitution is a mapping from variables to eleAnswer Set Programming (ASP) [1] is an approach to ments of the Herbrand universe of a program . Let declarative programming. Instead of stating how to solve be a rule, an atom, or a literal, then by we denote a problem, the programmer formulates the problem as a a rule, atom, or literal obtained by replacing each varilogic program specifying the search space and the prop- able ∈ vars() by ( ) . The function vars maps any erties of valid solutions. An ASP solver then finds models rule, atom, literal, or any other object containing vari(so-called answer sets) for this logic program, which cor- ables to the set of variables it contains. For instance, respond to solutions for the original problem. vars(a(X)) = {X} and for a rule 1 ∶ a(X) ← b(X, Y)., vars( 1) = {X, Y}. 2.1. Syntax As usual, we assume rules to be safe, which is the case for a rule if vars( ) ⊆ ⋃∈ body+() vars() , e.g., all ASP ofers a rich input language, of which we introduce variables must occur in the positive atoms of the rule, only the core concepts needed in this paper. For a com- which allows the grounding process to substitute them prehensive definition of ASP’s syntax and semantics, we with constants. refer to [8]. The (ground) instantiation of a rule equals for some
Let ⟨ , , ℱ , ⟩ define a first-order language, where substitution , which maps all variables in to ground is a set of variable symbols, is a set of constant terms. The (ground) instantiation grd( ) of a program symbols, ℱ is a set of function symbols, and is a set of is the set of all possible instantiations of the rules in [8]. predicate symbols. Function symbols may cause the Herbrand base and the
A classical atom is of the form ( 1, … , ), where ∈ full grounding of a program to be infinite. By restricted is a predicate symbol and 1, … , are terms. Each variable usage of function symbols, answer-set programs can be ∈ and each constant ∈ is a term. Furthermore, designed in a way that reasoning is decidable. for ∈ ℱ , ( 1, … , ) is a function term. ASP also allows An Herbrand interpretation for a program is a set of built-in atoms, such as equality or comparison predicates, ground classical atoms ⊆ . A ground classical atom which take arithmetic terms as arguments, e.g., X∗∗2 > 1 is true w.r.t. an interpretation , denoted ⊧ , if ∈ . where ∗∗ is the power operator. A ground literal not is true w.r.t. an interpretation ,
An answer-set program is a finite set of rules of the denoted ⊧ not , if ⊭ . A ground rule is satisfied form w.r.t. , denoted ⊧ , if its head atom is true w.r.t. (ℎ ∈ head( ) ∶ ⊧ ℎ ) whenever all body literals are true ℎ ← 1, … , , not +1 , … , not . ⟨1⟩ w.r.t. (∀ ∈ body( ) ∶ ⊧ ). An interpretation is a model of , denoted ⊧ , if ⊧ for all rules ∈ grd( ) .
Given a ground program and an interpretation , let denote the transformed program obtained from by deleting rules in which a body literal is false w.r.t. : = { ∣ ∈ , ∀ ∈ body( ) ∶ ⊧ } .
An interpretation of a program is an answer set of if it is a subset-minimal model of grd( ) , i.e., is a model of grd( ) and there exists no ′ ⊊ that is a model of grd( ) . where ℎ and 1, … , are atoms and not is negation as failure (a.k.a. default negation), which refers to the absence of information, i.e., an atom is assumed to be false as long as it is not derived by some rule. A literal is either an atom or its negation not . Given a rule of the form ⟨1⟩, head( ) = {ℎ} is called the head of , and body( ) = { 1, … , , not +1 , … , not } is called the body of . By body+( ) = { 1, … , } and body−( ) = { +1 , … , } we denote the positive and negative atoms in the body of , respectively. A rule where head( ) = ∅ , e.g., ← b., is called constraint. A rule where body( ) = ∅ , e.g., h ← ., is called fact. In facts the arrow can be omitted. A rule is ground if all its atoms are variable-free. A ground program comprises only ground rules.
An assignment over is a set of signed literals T , F , or M , where T and F express that an atom tial. is true and false, respectively, and M indicates that “must-be-true”. M means that an atom must eventually become true by derivation in a correct solution extending the current partial assignment, but no derivation has yet been found that would make the atom true. E.g., given constraint ← not b. we know that atom b must be true and has to eventually become true by derivation. Intuitively, T ∈
means that is true and justified, i.e., derived by a rule that fires under , while M ∈
only indicates that is true but potentially not derived. Let program . represents the state of the computation at step . The first element of the sequence is empty ( 0 = ∅), and every other element contains the signed literals that can be derived from the preceding partial assignment −1 in the
Since each element of a computation sequence is a partial assignment containing signed literals, and the sequence is monotonically growing, each contains atoms assigned T that will remain true in all extensions of , and atoms assigned F that will definitely remain false in = { ∣ ∈ } for ∈ { F, M, T} denote the set of atoms all extensions of . occurring with a specific sign in assignment . We assume assignments to be consistent, i.e., no negative literal may also occur positively ( F ∩ ( M ∪ T) = ∅), and every positive literal must also occur with must-be-true
Computation sequences require a normal logic program as input (i.e., rules of the form ⟨1⟩ without cardinality atoms and aggregate atoms, cf. [9, 10, 7]). Hence lazy grounding systems usually only accept normal logic ( T ⊆ M). The latter condition ensures that assign- programs or, in the case of Alpha, rewrite enhanced ASP ments are monotonically growing (w.r.t. set inclusion) in constructs like aggregates into normal rules. case an atom that was must-be-true becomes justified by a rule deriving it and hence changes to true.
A rule is said to be applicable in if {T ∣ ∈ body+( )} ⊆ and {M ∣ ∈ body−( )} ∩ = ∅, i.e., if
An assignment is complete if every atom in the Her- the positive body is satisfied and does not contradict the brand base is assigned true or false (∀ ∈ ∶ ∈ negative body. For every applicable rule in without F ∪ T). An assignment that is not complete is par- a negative body, the partial assignment is extended to
duced to extend the basic language of ASP defined in needs to know those ground rules that are applicable only
A cardinality atom is of the form lb { 1 ∶ 11, … , 1; … ; ∶ 1 , … , } ub,
where, for 1 ≤ ≤ , ∶ 1 , … , ditional literal in which (the head of the conditional literal) is a classical atom and all are literals, and lb
and ub are integer terms indicating a lower and an upper which rule to apply. Applying an applicable rule has the consequence that is extended to +1 by adding T head( ) and F for all ∈ body−( ) , i.e., all atoms of bound, respectively. If one or both of the bounds are not the negative body are assumed to be false. represents a con- choice points for the problem solver has to decide +1 by T head( ) . the current partial assignment.
Each applicable rule in with a non-empty negative body constitutes an active choice point. Given a set of ). given, their defaults are used, i.e., 0 for lb and ∞ for ub. A cardinality atom is satisfied if lb ≤ || ≤
ub holds, where is the set of head atoms in the cardinality atom that are satisfied together with their conditions (e.g., 1 , … , for
As an extension of cardinality atoms, ASP also sup- 2. ports aggregate atoms that apply aggregate functions like count or sum to sets of literals. An aggregate atom is satisfied if the value computed by the aggregate function respects the given bounds, e.g., 1 = #s u m {1 ∶ a; 2 ∶ b} is satisfied if a but not b is true.
In the following example in 0, Rule 1 is the only applicable rule. Consequently, 1 = {M x(1), T x(1)}. In 1 Rules 2 and 3 are applicable. If the solver decides to apply Rule 2 then M b(1), T b(1) and F c(1) are added to assignment 2 and therefore Rule 3 is not applicable in x(1) ← . b(1) ← x(1), not c(1). c(1) ← x(1), not b(1).
% % guessing b % guessing c
Rule 1 Rule 2
Rule 3
which may be general, i.e., designed for every ASP program [11], or they may be domain-specific, e.g., designed
Lazy grounding is an approach that interleaves the solv- for a specific problem [ 6]. ing and grounding phases, such that computations are guaranteed to yield all answer sets. The foundation for lazy grounding is known as the computation sequence [9].
A computation sequence S = ⟨ 0, 1, … , ⟩ is a sequence of partial assignments that is monotonically growing (w.r.t. set inclusion). Every element of the sequence
As an introductory example, consider the following ASP program. The idea is that for every number i ∈ {1, … , n} the solver can decide either to assert b(i) or c(i). As an example we set = 400 . Let Bs and Cs be all the /1 and /1 atoms in an answer set of the example program. We require that any answer set must fulfill the constraint ((∑b(i)∈Bs i) − (∑c(i)∈Cs i))2 ≤ 1, e.g., the diference between these two sums must be at most 1. We call this problem the Balanced Sum Problem (BSP). The example program comprises a guessing part and a part where solutions are checked. Moreover, we may specify initial facts like b(200) and b(201). In the worst case, 2398 guesses are possible. To avoid a high number of possible guesses, we can formulate heuristics that aid the solver in performing correct guesses such that backtracking is minimized. not applicable if the #s u m aggregate is evaluated under the standard declarative semantics of ASP. This semantics assumes that the truth assignments for the b/1 atoms are ifxed.
By adding the shown heuristic directives to the example program, wrong choices, which lead to backtracks, can be avoided for the depicted problem instance. The following section will present the syntax and semantics of heuristics that employ dynamic aggregates. 4. Syntax and semantics x(1..400). % guessing b(X) ← x(X), not c(X). c(X) ← x(X), not b(X). % initial imbalance b(200). b(201). % check solution sumB(Sum) ← Sum = #s u m {Y ∶ b(Y)}. sumC(Sum) ← Sum = #s u m {Y ∶ c(Y)}. % constrain diference between sums ← sumB(SB), sumC(SC), (SB − SC)∗∗2 > 1. % heuristics #h e u r i s t i c b(X) ∶ x(X), not c(X), S = #s u m {Y ∶ c(Y)},
Weight = X, Level = S. [Weight@Level] #h e u r i s t i c c(X) ∶ x(X), not b(X), S = #s u m {Y ∶ b(Y)}, Weight = X, Level = S. [Weight@Level] % initializing values from 1 to 400. In [6] domain-specific heuristics for answer set pro
gramming were proposed which allow to reason about % guessing b the current state of the problem-solving process. This % guessing c state is reflected by the latest partial assignment. Consequently, heuristic directives are evaluated w.r.t. this assignment. However, in the declarative semantics of ASP the truth value of aggregates as presented in the example (e.g., S = #s u m {Y ∶ b(Y)}) can only be determined w.r.t. a fixed set of truth assignments for atoms. In the declarative semantics of ASP assigning a truth value to S = #s u m {Y ∶ b(Y)} implies that the set of b/1 atoms which are assigned to true is fixed, i.e., rules must not be % b-heuristic applied which assert additional b/1 atoms to true.
However, in the spirit of [6] we propose to evaluate aggregates w.r.t. the latest partial assignment to evaluate % c-heuristic heuristic directives for determining the choice, i.e., which rule to apply to compute the next partial assignment.
Definition 1 (Heuristic Directive). A heuristic direc
As an example, let us consider an instantiated tive is of the form ⟨2⟩, where (0 ≤ ≤ ) are atoms and version of a heuristic for the partial assignment and are integer terms. 1 = {M b(200), T b(200), M b(201), T b(201), M x(1), T x(1), … , M x(400), T x(400)}, i.e., the partial assignment #h e u r i s t i c 0 ∶ 1, … , , comprising all initial facts which are true. For x(400) an not +1 , … , not .[ @] ⟨ 2⟩ instance of the c-heuristic (including the evaluation of the aggregate) is #h e u r i s t i c c(400) ∶ x(400), not b(400), The heuristics’ head is given by 0 and its condition by 401 = #s u m {200, 201}, [400@401]. { 1, … , , not +1 , …, not }.
Heuristic directives assign a weight and a level to a We call an atom in a heuristic directive a heuristic rule which derives an atom. In this instantiated heuristic atom. We now describe our semantics, beginning with directive, the weight is 400, and the level is 401. All other the condition under which a heuristic atom is satisfied. instantiated c-heuristics and b-heuristics have either a lower level or lower weights in case of the same level. For Definition 2 (Satisfying a Heuristic Atom). Given a performing choices, guesses are preferred with higher ground heuristic atom and a partial assignment , is levels, and higher weights are prioritized among guesses satisfied w.r.t. if ∈ T, i.e., atom a is assigned to true. with the same level. Consequently, the solver will apply The head of a heuristic directive of the form ⟨2⟩ is a rule which asserts c(400). denoted by head() = 0, its weight by weight() =
The novel concept of this paper is that aggregates if given, else 0, and its level by level() = if given, else in heuristic directives like #s u m are evaluated w.r.t. the 0. The (heuristic) condition of a heuristic directive is current assignment. For the partial assignment 1, the denoted by cond() ∶= { 1, … , , not +1 , … , not }, aggregate #s u m {Y ∶ b(Y)} in the c-heuristic is evaluated as the positive condition is cond+() ∶= { 1, … , } and the #s u m {200, 201} since 1 contains the atoms T b(200) and negative condition is cond−() ∶= { +1 , … , }. T b(201). Applying the aggregate function #s u m derives Whether a heuristic directive is satisfied depends on 401. Note, in the partial assignment 1, the c-heuristic is whether the atoms occurring in the directive are satisfied. Definition 3 (Satisfying a Heuristic Directive).
Given a ground heuristic directive and a partial assignment , cond() is satisfied w.r.t. if: every ∈ cond+() is satisfied and no ∈ cond−() is satisfied.
Definition 4 (Applicability of a Heuristic Directive). A ground heuristic directive is applicable w.r.t. a partial assignment and a ground program if: cond() is satisfied, ∃ ∈ s.t. head( ) = head() and {T ∣ ∈ body+( )} ⊆ and {M ∣ ∈ body−( )} ∩ = ∅ , and head() ∉ ( T ∪ F).
Intuitively, a heuristic directive is applicable if its condition is satisfied, there exists a currently applicable rule that can derive the atom in the heuristic directive’s head, and the atom in its head is assigned neither T nor F. If the atom in the head is assigned M, the heuristic directive is still applicable, because any atom with the non-final truth value M must be either T or F in any answer set.
What remains to be defined is the semantics of weight and level. Given a set of applicable heuristic directives, one directive with the highest weight will be chosen from the highest level.
Definition 5 (Heuristics Eligible for Choice). Given a set of applicable ground heuristic directives, the subset eligible for immediate choice is defined as maxpriority() in two steps: maxlevel() ∶= { ∣ ∈ and level() = max∈ level()} maxpriority() ∶= { ∣ ∈ maxlevel() and weight() = max∈ maxlevel() weight()} 1 , … , . The aggregate terms are treated as members of a mulitset. Duplicates are allowed.1
The result of applying is exploited to evaluate the comparison condition expressed by 1 ≺1 and ≺2 2. These conditions may be omitted. 1, 2 are terms, e.g., numbers or variables. 1 ≺1 and ≺2 2 are called guards. For the guard operator ≺ comparison operators such as =, ≠, ≤, ≥, <, > may be employed.
If in t ∶ 1 , … , of an aggregate atom the term t is a variable, then this variable must be safe. This variable is safe if it is contained in the condition or it is a global variable. A variable in a heuristic directive is global if it appears in a classical atom in cond+() or in a guard of an aggregate atom of where ≺ corresponds to =.
We allow aggregate functions like #c o u n t (the number of aggregate terms) or #s u m (sum of aggregate terms).
An aggregate atom is satisfied if the value computed by the aggregate function respects the given bounds, e.g., 1 = #s u m {1 ∶ a; 1 ∶ b} is satisfied if either a or b is true. Let us assume that the facts a(1). a(2). b(5). are given. Evaluating the aggregate atom X = #s u m {Y ∶ a(Y); Y ∶ b(Y)} will bind 8 to variable X.
After choosing a heuristic using maxpriority, a solver makes a decision on the directive’s head atom. Other solv- In search for answer sets, Alpha applies heuristics to seing procedures, e.g., deterministic propagation, are unaf- lect an active choice point. In contrast to [6], the heuristic fected by processing heuristics. In case no heuristic di- directives are transformed to Prolog queries and evalurective is applicable or multiple directives have the same ated by a Prolog interpreter. We have chosen this apmaxpriority the solver’s default heuristic (e.g., VSIDS) proach to implement the eficient evaluation of dynamic makes a choice as usual. aggregates in heuristic directives.
Aggregate atoms may be employed in the condition of Figure 1 shows the integration of Alpha with Prolog. a heuristics directive. An aggregate atom is of the form Query-driven heuristics are employed by Alpha if the - u q h flag is set. The heuristic directives are removed from 1 ≺1 { t ∶ 11, … , 1; … ; the input program and translated into internal data struct ∶ 1 , … , } ≺2 2 tures. These data structures comprise all the necessary where t corresponds to a variable, an integer, or a ground atom. We call t an aggregate term. refers to some aggregate function that is applied to the multiset of aggregate terms t that remain after evaluating the condition 1Note that this semantics difers from the ASP semantics of aggregates employed in rules. First, for our prototypical system t is a single term and not a tuple of terms for simplicity reasons. Second, we allow a multiset of aggregate terms instead of a set, i.e., we do not remove duplicates. Sets and multisets can be easily implemented. However, the removal of duplicates may introduce additional computational costs. information for evaluating the heuristic directives, such as their head atom, variables, atoms occurring inside the heuristic, and crucially, their respective Prolog query.
Thus, the heuristic directives are separately stored from the program and are all evaluated whenever a choice is made.
As an example, the following heuristic directive varying sizes, where the larger instances were challenging to ground and/or to solve. More precisely, traditional grounders excessively consumed space or time when grounding these instances, and/or solving was infeasible without domain-specific heuristics.
#h e u r i s t i c c(X) ∶ x(X), not b(X), S = #s u m {Y ∶ b(Y)}, W = S ∗ 10 + X. [W@1] is translated to the following Prolog query: x (X ), \+ b (X ), a g g r e g a t e _a l l (s u m (Y ), b (Y ), _0 ), S i s _0 , W E I G H T i s S ∗ 1 0 + X , L E V E L i s 1 , \+ c (X ).
our experiments are available online.2
Alpha was used without justification analysis [ 12] (command-line argument - d j ) and without support for negative integers in aggregates (- d n i ). Apart from that, Alpha was used in its default configuration. The JVM running Alpha was called with command-line parame
The Prolog predicate a g g r e g a t e _a l l (+T e m p l a t e , ters - X m s 1 G - X m x 2 4 G , thus initially allocating 1 GiB for ∶ G o a l , −R e s u l t ) aggregates bindings in G o a l according Java’s heap and setting the maximum heap size to 24 GiB. to T e m p l a t e . Possible template values comprise the The Prolog interpreter swi-prolog3 [13] version 9.0.4 was aggregate functions, c o u n t , s u m (X ), m a x (X ), and m i n (X ). integrated with Alpha via jpl.4 For comparison, clingo5 The variable in s u m (X ), m a x (X ), and m i n (X ) corresponds to [14] was used in version 5.6.2. the variable serving as aggregate term and is instantiated Each of the machines used to run the experiments ran by querying G o a l which contains this variable. The Ubuntu 22.04.2 LTS Linux and was equipped with two result is bound to an anonymous variable (_0 in our Intel® Xeon® E5-2650 v4 @ 2.20GHz CPUs with 12 cores. example) and exploited in the aggregates’ guards. Any Hyperthreading was disabled and the maximum CPU negated atom is preceded by the operator \+, equivalent frequency was set to 2.90GHz. Scheduling of benchmarks to not for our purposes. Finally, the negated head atom was done with slurm6 version 21.08.5. runsolver7 v3.4.1 of the heuristic directive is added to the query to exclude was used to limit time consumption to 10 minutes per already assigned head atoms. instance and memory to 32 GiB. Care was taken to avoid
During problem-solving, Alpha synchronizes the as- side efects between CPUs, e.g., by requesting exclusive signments with the database of the Prolog system. Every access to an entire machine for each benchmark. atom assigned as true by Alpha is inserted in the Prolog All solvers were configured to search for the first database. If such atoms are removed from the assignment, answer set of each problem instance. Finding one or the corresponding facts are retracted from the Prolog only a few solutions is often suficient in industrial use database. Atoms assigned to false or must-be-true by cases since solving large instances can be challenging Alpha are not considered since the heuristic directives [3]. Therefore, the domain-specific heuristics used in are evaluated on atoms assigned to true. the experiments are designed to help the solver find one
The current implementation of Alpha sources and answer set that is “good enough”, even though it may binaries which implement query-driven heuristics can not be optimal. be found on https://github.com/tilmanni/Alpha/tree/ domspec_heuristics_extended_prolog.
query-driven heuristics by creating heuristics for two example domains and applying the extended Alpha system. The two concrete domains under investigation were the Partner Units Problem (PUP) and the Balanced Sum Problem (BSP) introduced in Section 3. 2https://github.com/tilmanni/Alpha/tree/domspec_heuristics_
These two problems are abstracted variants of typical extended_prolog/Evaluation configuration (sub)problems experienced in more than 3https://www.swi-prolog.org/ 25 years of applying AI technology in the automated con- 4https://jpl7.org/ ifguration of electronic systems [ 3]. To put ASP systems 5https://potassco.org/clingo/ 6https://slurm.schedmd.com/ under stress, we used problem encodings and instances of 7https://github.com/utpalbora/runsolver The Partner Units Problem (PUP) [15] is an abstracted version of industrial configuration problems. In particular, PUP deals with configuring parts of railway safety systems. This problem is a benchmark problem for ASP systems since its challenges for grounding and solving. to a dotted rectangle (i.e., a zone) is connected by an edge in . Note that there is no edge between a door surrounded by a rectangle and the zone corresponding to this rectangle.
We say a unit is connected to a sensor/zone if the sensor/zone is in . Two units are connected if they are adjacent. Connections correspond to physical connections in an assembled configuration.
Figure 2 shows an example of a PUP instance. The bipartite graph comprises six sensors and six zones. Each of the three units can be adjacent to at most two other units, and each unit can contain at most two sensors and two zones. Connections of sensors, zones, and units that satisfy all PUP requirements are presented in Figure 2. Encodings and instances. To show the application and efectiveness of query-driven heuristics, we focus on the PUP instances employed in the ASP competition [5].
Domain-specific heuristics allow exploiting knowledge about properties of classes of problem instances. We The atom assignable_sensor_unit(S, U) is true if a senconcentrate on the double and double-variant classes sor is ready to be assigned, i.e., if a sensor is connected to of PUP instances. For these instances, domain-specific a zone in the input graph and this zone is connected heuristics were formulated. to a unit. The atom sensor_blocked_on_unit(S, U) is
Figure 3 shows the basic structure of the double in- true if sensor cannot be connected to unit U. The stances. There are two rows of rooms connected by doors. variable Deg_sensor_dyn is assigned to the number Each room corresponds to a zone, and each door repre- of zones connected to sensor S in the input graph sents a sensor. For each room and the doors of this room, and which are already assigned to a unit. The atom there is an edge in the bipartite graph , i.e., the zone zone2sensor(Z, S) encodes the edges of the input graph and its doors are connected through an edge. The dou- (i.e., connections between zones and sensors). Values ble instances’ sizes vary depending on the number of of the variable Deg_sensor_dyn express the number of columns of rooms. The structure depicted in Figure 3 constraints put on placing sensor S. We prefer conshows three columns of rooms. The bipartite graphs necting sensors to units with a higher number of conof the double-variant instances comprise the nodes and straints. The atom num_forbidden_places_of_sens(S, N) edges of the double instances. However, each dotted represents the number of connections to units that are not rectangle represents an additional zone (i.e., the dotted possible for for a given set of connections between senrectangle clusters rooms). Each door (i.e., a sensor) next sors, zones, and units (e.g., the configuration in a specific 105 s e s s e fgu104 o r e b um103 N 1 2 3 4 5 6 7 8 9 10
Number of instances (b) Number of guesses 1 2 3 4 5 6 7 8 9 10
Number of instances partial assignment). Rules compute diferent numbers One curve was drawn for each solver configuration: depending on the connections. We prefer connecting sen- Alpha with query-driven evaluation of domain-specific sors to units with a higher number of forbidden places heuristics (qh-alpha), and clingo with (h-clingo) and with(i.e., connections). The variable Assigned_sensors_unit out domain-specific heuristics. counts the number of sensors connected to unit U. The Figure 5 shows the results for the double-variant invariable Direct_con_zones counts the number of zones stances in exactly the same way. that are connected to unit U and which are connected to Alpha was used with encodings and heuristics desensor S in the input graph. All these numbers are added signed to achieve a good performance as described above. with diferent weights resulting in the final weight of the clingo was used with the “new” encoding from the Fifth heuristic directive expressing the priority to connect S ASP competition8 [17]. h-clingo used the domain-specific and U. The design of the heuristic directive follows the heuristics devised in previous work [6]. Both systems principle of preferring assignments of connections that used the same sets of problem instances, which consisted are most constrained in the spirit of heuristics of heuris- of 10 instances of the “double” class (with a number of tics for constraint satisfaction problems (CSPs) such as units ranging between 20 and 200), and 6 instances of the “fail-first” or “degree” [ 16]. “double-variants” class (with 30–180 units).
The second heuristic for assigning zones to units in Substantial diferences can be observed. The curves double PUP instances can be formulated shorter than the for qh-alpha reach farthest to the right, meaning that presented one. We prefer assignments of zones to units Alpha with query-driven heuristics solved the highest U, where the number of connected zones to U is high, number of instances (all 10 double, 5 of 6 double-variants). and the number of possible connections for sensors to U clingo needed more time and thus solved fewer instances. and its adjacent units is large. Apparently, the domain-specific heuristics used with hclingo were not useful for solving the double-variants Results. Figure 4 shows performance data for experi- instances. ments with the double PUP instances. Cactus plots were created in the usual way. In Figure 4c, the x-axis gives the 6.3. Case Study 2: The Balanced Sum number of instances solved within real (i.e., wall-clock) Problem (BSP) time, given on the y-axis. Similarly, Figure 4b shows the number of guesses needed and Figure 4d shows the The second evaluation case deals with the BSP. In conmemory consumed to solve the instances. In all plots, figuring, sub-problems arise where quantities such as data points are sorted by y-values. Figure 4a contains a power consumption should be equally distributed. legend with all solver configurations. The number of instances solved by each system is shown next to its name (in parentheses).
Encodings.2C_Instance_Sets Encodings and instances. As the encoding of the Since heuristics in the non-dynamic semantics are not problem, we use the ASP code introduced in Section 3. known for this problem, clingo was only used without To strain the problem-solving, we increment the num- domain-specific heuristics. A hundred instances with ber of x/1 atoms and adapt the constant in the rules for ∈ {10, 20, … , 990, 1000} were used for the experiments. sumB/1 and sumC/1. In the BSP experiments, qh-alpha greatly outperformed clingo, showing the benefits of domain-specific Results. Results obtained for BSP are shown in Fig- heuristics evaluated in a query-driven way within a lazyure 6, which was generated in the same way as for grounding ASP solver. While qh-alpha solved all 100 inPUP (cf. Section 6.2). clingo was used with the encod- stances within at most 2.33 minutes per instance, clingo ing presented in Section 3, while Alpha used an alter- reaches the grounding bottleneck very quickly and is not native representation of the sum constraints that the able to solve instances larger than = 140 . lazy-grounding system could evaluate more eficiently.
lating domain-specific heuristics to speed up problemsolving. We have introduced dynamic aggregates, allowing us to reason about the current problem-solving state.
E.g., we can reason about second-order properties of this state, such as the number of atoms with specific properties or summing quantities over sets of atoms or computing the maximum/minimum of such quantities. We have provided the prototypical implementation qh-alpha by integrating Prolog with the lazy-grounding system Alpha.
This system was evaluated on two problems related to configuration, i.e., the double and double variant cases of the well-known Partner Units Problem, and the Balanced Sum Problem. However, dynamic aggregates are a general concept that knowledge engineers can apply to other problem domains. The evaluation shows that dynamic aggregates employed in domain-specific heuristics can considerably improve solving performance.
In future work, we plan to develop further the prototypical implementation to incorporate standard semantics of aggregate elements and terms. Additionally, exploring incorporating sign set semantics in query-driven heuristics would further enhance expressiveness. Eforts should also be made to utilize query-driven and regular domainspecific heuristics concurrently. Finally, we recommend evaluating the feasibility of applying the query-driven approach to specific aggregates in normal rules as an alternative to resource-intensive normalization. of Lecture Notes in Computer Science, Springer, 2011, pp. 345–351. [5] M. Gebser, M. Maratea, F. Ricca, The seventh answer set programming competition: Design and results, Theory Pract. Log. Program. 20 (2020) 176–204. [6] R. Comploi-Taupe, G. Friedrich, K. Schekotihin,
A. Weinzierl, Domain-specific heuristics in answer set programming: A declarative non-monotonic approach, J. Artif. Intell. Res. 76 (2023) 59–114. [7] A. Weinzierl, Blending lazy-grounding and CDNL search for answer-set solving, in: LPNMR, volume 10377 of Lecture Notes in Computer Science, Springer, 2017, pp. 191–204. [8] 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. [9] L. Liu, E. Pontelli, T. C. Son, M. Truszczynski, Logic programs with abstract constraint atoms: The role of computations, in: ICLP, volume 4670 of Lecture Notes in Computer Science, Springer, 2007, pp.
286–301. [10] C. Lefèvre, C. Béatrix, I. Stéphan, L. Garcia, AS
PeRiX, a first-order forward chaining approach for answer set computing, Theory Pract. Log. Program.
17 (2017) 266–310. [11] M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang,
S. Malik, Chaf: Engineering an eficient SAT solver, in: DAC, ACM, 2001, pp. 530–535. [12] B. Bogaerts, A. Weinzierl, Exploiting justifications for lazy grounding of answer set programs, in:
IJCAI, ijcai.org, 2018, pp. 1737–1745. [13] J. Wielemaker, T. Schrijvers, M. Triska, T. Lager,
Swi-prolog, Theory Pract. Log. Program. 12 (2012) 67–96. doi:1 0 . 1 0 1 7 / S 1 4 7 1 0 6 8 4 1 1 0 0 0 4 9 4 . [14] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub,
Multi-shot ASP solving with clingo, Theory Pract.
Log. Program. 19 (2019) 27–82. [15] E. C. Teppan, Solving the partner units configuration problem with heuristic constraint answer set [1] M. Gebser, R. Kaminski, B. Kaufmann, M. Lin- programming, in: Configuration Workshop, 2016, dauer, M. Ostrowski, J. Romero, T. Schaub, S. Thiele, pp. 61–68.
P. Wanko, Potassco guide version 2.2.0, 2019. [16] S. J. Russell, P. Norvig, Artificial Intelligence – A URL: https://github.com/potassco/guide/releases/ Modern Approach, Fourth Edition, Pearson Educatag/v2.2.0. tion, 2022. [2] A. A. Falkner, G. Friedrich, K. Schekotihin, R. Taupe, [17] F. Calimeri, M. Gebser, M. Maratea, F. Ricca, Design E. C. Teppan, Industrial applications of answer set and results of the fith answer set programming programming, Künstliche Intell. 32 (2018) 165–176. competition, Artif. Intell. 231 (2016) 151–181. doi:1 0 . [3] A. A. Falkner, G. Friedrich, A. Haselböck, G. Schen- 1 0 1 6 / j . a r t i n t . 2 0 1 5 . 0 9 . 0 0 8 . ner, H. Schreiner, Twenty-five years of successful application of constraint technologies at Siemens,
AI Magazine 37 (2016) 67–80. [4] M. Gebser, R. Kaminski, A. König, T. Schaub, Advances in gringo series 3, in: LPNMR, volume 6645