from most specific (problem instances) to most general (A* encoding).
Afterwards, we will present the routing application. State-based search, where
the problem’s solution is a path, deals with pathfinding. Therefore we focus
our evaluation on pathfinding and routing, showing the benefits of lazy-
grounding combined with heuristic search.

##### Problem Instances for Pathfinding.

Instances are defined as stated in Example 2, i.e., they consist of atoms over
the following predicates:

  * •

$\mathrm{xmin}/1$,

  * •

$\mathrm{xmax}/1$,

  * •

$\mathrm{ymin}/1$,

  * •

$\mathrm{ymax}/1$,

  * •

$\mathrm{start}/2$,

  * •

$\mathrm{goal}/2$, and

  * •

$\mathrm{obstacle}/2$.

For our experiments, we have generated instances as follows. Each instance
represents a square plane of width $w$. For each $w\in\\{5,10,\dots,500\\}$
there exists one instance, so there are 100 instances in total. The start is
located in the top-left corner, and the goal is located in the bottom-right
corner. Each square in the plane, except for the start and the goal, is an
obstacle with a probability of $0.2$. Additionally, two long vertical walls
cut through the plane, one starting at the bottom and one at the top of the
plane. The $x$-positions of these walls, as well as their lengths, are
randomly determined within reasonable ranges.

##### Problem-Specific Encoding for Pathfinding.

The problem-specific encoding defines some intermediate predicates:

  * •

$\mathrm{neighbour}/4$ defines which squares are adjacent to each other, and

  * •

$\mathrm{manhattan}/3$ defines the Manhattan distance from each square to the
goal.

For example, $\mathrm{neighbour}(4,2,3,2)$ denotes that $(4,2)$ is adjacent to
$(3,2)$, and $\mathrm{manhattan}(3,2,3)$ denotes that the Manhattan distance
from $(3,2)$ to the goal at $(1,3)$ is 3.

As input to the problem-independent A* encoding, the following predicates have
to be defined:

  * •

$\mathrm{init}/1$ defines the initial state;

  * •

$\mathrm{goal}/1$ defines the goal state;

  * •

$\mathrm{c}/4$ defines the cost function; and

  * •

$\mathrm{h}/2$ defines the heuristic evaluation function $h$ (which is here
the Manhattan distance to the goal).

Actions and transition model need not be explicitly defined because this
information is implicitly contained in $\mathrm{c}/4$.

The input to A* is realised in the problem-specific Pathfinding encoding by
the following rules:

$\displaystyle\mathrm{init(at(X,Y))}\leftarrow\;$
$\displaystyle\mathrm{start(X,Y)}.$
$\displaystyle\mathrm{goal(at(X,Y))}\leftarrow\;$
$\displaystyle\mathrm{goal(X,Y)}.$
$\displaystyle\mathrm{c(at(AtX,AtY)},\mathrm{move(X,Y)},\mathrm{at(X,Y),StepCost)}\leftarrow\;$
$\displaystyle\mathrm{neighbour(AtX,AtY,X,Y)},$
$\displaystyle\mathrm{not}~{}\mathrm{obstacle(X,Y)},$
$\displaystyle\mathrm{StepCost}=1.$
$\displaystyle\mathrm{h(at(X,Y),H)}\leftarrow\;$
$\displaystyle\mathrm{manhattan(X,Y,H)}.$

##### Problem-Independent A* Encoding.

We will now present our ASP-based A* encoding step by step. This problem-
independent encoding stays the same for any search problem to which A* is
applied.

The first step is to retrieve the information on the $\mathsf{actions}$ and
$\mathsf{result}$ functions from the problem definition, implicitly contained
in $\mathrm{c}/4$.

$\displaystyle\mathrm{result(ParentState,Action,ChildState)}\leftarrow\;$
$\displaystyle\mathrm{c(ParentState,Action,ChildState,StepCost)}.$
$\displaystyle\mathrm{action(ParentState,Action)}\leftarrow\;$
$\displaystyle\mathrm{result(ParentState,Action,ChildState)}.$

The $\mathrm{n}/4$ predicate is used to represent each node $n$ in the
searched graph by state $S$, parent state $\mathit{PS}$ (which generated $n$),
action $A$ (applied to generate $n$), and path cost $G=g(n)$. There also
exists an $\mathrm{n}/1$ predicate that is used when only the state of a node
is needed. Recall that $\mathrm{init}/1$ is defined in the problem-specific
encoding. The $\mathrm{explore}/2$ predicate will be defined further below; it
is used for state-action pairs that have already been explored.

$\displaystyle\mathrm{n(S,null,null,0)}\leftarrow\;$
$\displaystyle\mathrm{init(S)}.$
$\displaystyle\mathrm{n(S,PS,A,G)}\leftarrow\;$
$\displaystyle\mathrm{result(PS,A,S)},\mathrm{explore(PS,A)},\mathrm{g(PS,A,G)}.$
$\displaystyle\mathrm{n(S)}\leftarrow\;$ $\displaystyle\mathrm{n(S,PS,A,G)}.$

Note that if $h(n)$ is consistent, a property of graph-search is that nodes
are only explored if their smallest $g$-value was found (?). Based on this
property and the determinism of actions it follows that $\mathit{PS}$ and $A$
are uniquely identifying a tuple of $\mathrm{n}/4$.

The $f$-value for each node is the sum of the node’s $g$-value (cost from the
initial state to the node) and its $h$-value (heuristically estimated cost
from the node to the nearest goal). Recall that $\mathrm{h}/2$ is defined in
the problem-specific encoding.

$\displaystyle\mathrm{g(S,G)}\leftarrow\;$ $\displaystyle\mathrm{n(S,P,A,G)}.$
$\displaystyle\mathrm{f(S,G+H)}\leftarrow\;$
$\displaystyle\mathrm{g(S,G)},\mathrm{h(S,H)}.$

Nodes are only generated in our approach when they are explored. However,
$f(n)$ is already needed before $n$ is explored to decide which nodes to
explore. Therefore, we define $f$ also for state-action pairs.

$\displaystyle\mathrm{g(PS,A,ParentG+StepCost)}\leftarrow\;$
$\displaystyle\mathrm{g(PS,ParentG)},\mathrm{c(PS,A,S,StepCost)}.$
$\displaystyle\mathrm{h(PS,A,H)}\leftarrow\;$
$\displaystyle\mathrm{result(PS,A,S)},\mathrm{h(S,H)}.$
$\displaystyle\mathrm{f(S,A,G+H)}\leftarrow\;$
$\displaystyle\mathrm{g(S,A,G)},\mathrm{h(S,A,H)}.$

Now we can encode elements of A* (cf. Algorithm 1) as rules. There is no one-
to-one correspondence between statements in the algorithm and rules in our ASP
encodings, so we present ASP rules in a logical order.

The union of frontier and explored set is represented by
$\mathrm{frontier\\_and\\_explored\\_states}/2$. The predicate consists of
state-action pairs instead of nodes because nodes are not generated before
they are explored. Since an atom’s truth value cannot change from true to
false without backtracking, atoms of the
$\mathrm{frontier\\_and\\_explored\\_states}/2$ predicate also include nodes
that have already been removed from the frontier. These removed nodes are in
the explored set, i.e. nodes represented by $\mathrm{n}/4$ were generated. The
following rule adds an explored node’s children to
$\mathrm{frontier\\_and\\_explored\\_states}/2$:

$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(S,A)}\leftarrow\;$
$\displaystyle\mathrm{n(S)},\mathrm{action(S,A)},\mathrm{not}~{}\mathrm{goal(S)}.$

The explored set $\mathit{E}$ is already represented by predicates
$\mathrm{n}/4$ and $\mathrm{n}/1$ because atoms of these predicates represent
nodes that are only generated when explored. However, to avoid exploring the
same state repeatedly, the $\mathrm{explored\\_by\\_other\\_step}/3$ predicate
stores actions that may not be used because the resulting children have
already been explored.

$\displaystyle\mathrm{explored\\_by\\_other\\_step(S,PS,A)}\leftarrow\;$
$\displaystyle\mathrm{n(S,PS^{\prime},A^{\prime},G)},\mathrm{result(PS,A,S)},\mathrm{PS}^{\prime}\neq\mathrm{PS}.$
$\displaystyle\mathrm{explored\\_by\\_other\\_step(S,PS,A)}\leftarrow\;$
$\displaystyle\mathrm{n(S,PS^{\prime},A^{\prime},G)},\mathrm{result(PS,A,S)},\mathrm{A^{\prime}}\neq\mathrm{A}.$

When a child state is already explored, the corresponding state-action pair is
still added to the frontier but marked as suboptimal.

$\displaystyle\mathrm{suboptimal\\_step(PS,A)}\leftarrow\;$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(PS,A)},\mathrm{result(PS,A,S)},$
$\displaystyle\mathrm{explored\\_by\\_other\\_step(S,PS,A)}.$

Similarly, when a cheaper path to a child state is discovered, the existing
state-action pair in the frontier is marked as suboptimal.

$\displaystyle\mathrm{suboptimal\\_step(PS,A)}\leftarrow\;$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(PS,A)},\mathrm{result(PS,A,S)},$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(PS^{\prime},A^{\prime})},\mathrm{result(PS^{\prime},A^{\prime},S)},$
$\displaystyle\mathrm{f(PS,A,F)},\mathrm{f(PS^{\prime},A^{\prime},F^{\prime})},\mathrm{F}>\mathrm{F^{\prime}}.$

The following two rules are here to recognise when a goal state is explored.

$\displaystyle\mathrm{goal\\_found(S)}\leftarrow\;$
$\displaystyle\mathrm{n(S)},\mathrm{goal(S)}.$
$\displaystyle\mathrm{goal\\_found}\leftarrow\;$
$\displaystyle\mathrm{goal\\_found(S)}.$

A found goal is not accepted if a node with a lower $f$-value is still on the
frontier. This restriction ensures optimality of found solutions even without
heuristic directives.202020Using the heuristics presented below, the problem
can be solved without backtracking, which means that constraints are not
needed when using these heuristics. We still include constraints in the
encoding to render it a correct declarative problem specification when viewed
without heuristics.

$\displaystyle\leftarrow\;$
$\displaystyle\mathrm{goal\\_found(S)},\mathrm{explore(PS,A)},\mathrm{result(PS,A,S)},\mathrm{f(S,F)},$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(S^{\prime},A^{\prime})},$
$\displaystyle\mathrm{not}~{}\mathrm{explore(S^{\prime},A^{\prime})},\mathrm{not}~{}\mathrm{suboptimal\\_step(S^{\prime},A^{\prime})},$
$\displaystyle\mathrm{f(S^{\prime},A^{\prime},F^{\prime})},\mathrm{F^{\prime}}<\mathrm{F}.$

The encoding contains a single choice rule, which realises choosing a leaf
node from the frontier. Without heuristic directives, which will be defined
later, this rule does not differentiate between nodes in the frontier.

$\displaystyle\\{~{}\mathrm{explore(S,A)}~{}\\}\leftarrow\;$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(S,A)},\mathrm{not}~{}\mathrm{suboptimal\\_step(S,A)}.$

Note that by the consistency property of $h(n)$ nodes in graph-search are only
selected for exploration if the minimum $g$-value for this node was found. We
assure this property by the heuristic formulated for $\mathrm{explore/2}$ (see
below). $S,A$ tuples of the frontier with smallest $f$-value are explored
first. Consequently, if there are two distinct state/action pairs $(s,a)$ and
$(s^{\prime},a^{\prime})$ which were not explored and which lead to the same
successor state, then our heuristic will select the state/action pair for
exploaration which is on an optimal path.

Failure is derived when the frontier is empty, and no goal has been found. Our
encoding of A* is always satisfiable. An answer set contains a solution if the
search problem has a solution, and an answer set contains the
$\mathrm{failure}$ atom if there is no solution. We have decided this way
because the alternative, having a constraint that $\mathrm{goal\\_found}$ must
be true in an answer set, makes solving performance deteriorate sharply for
instances without a solution.

$\displaystyle\mathrm{frontier\\_nonempty}\leftarrow\;$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(S,A)},$
$\displaystyle\mathrm{not}~{}\mathrm{suboptimal\\_step(S,A)},\mathrm{not}~{}\mathrm{explore(S,A)}.$
$\displaystyle\mathrm{failure}\leftarrow\;$
$\displaystyle\mathrm{not}~{}\mathrm{frontier\\_nonempty},\mathrm{not}~{}\mathrm{goal\\_found}.$
$\displaystyle\leftarrow\;$
$\displaystyle\mathrm{not}~{}\mathrm{failure},\mathrm{not}~{}\mathrm{goal\\_found}.$

When the goal has been found, the path from the initial state to the goal
state can be computed along with corresponding path costs.

$\displaystyle\mathrm{path\\_to\\_goal(PS,A,S)}\leftarrow\;$
$\displaystyle\mathrm{explore(PS,A)},\mathrm{result(PS,A,S)},\mathrm{goal\\_found(S)}.$
$\displaystyle\mathrm{path\\_to\\_goal(PS,A,S)}\leftarrow\;$
$\displaystyle\mathrm{explore(PS,A)},\mathrm{result(PS,A,S)},\mathrm{path\\_to\\_goal(S,A^{\prime},S^{\prime})}.$
$\displaystyle\mathrm{cost\\_to\\_goal(G)}\leftarrow\;$
$\displaystyle\mathrm{goal\\_found(GoalState)},\mathrm{g(GoalState,G)}.$

This subsequent computation is necessary because A* may choose to apply more
than one action on the same state if one of those actions turns out to lead to
a more costly path to the goal. Our approach does not need backtracking, so
the answer set includes all $\mathrm{explore}/2$ atoms tried, and we need to
reconstruct the path that leads to the goal.

The result computed by A* is encoded by the predicates

  * •

$\mathrm{path\\_to\\_goal}/3$,

  * •

$\mathrm{cost\\_to\\_goal}/1$, and

  * •

$\mathrm{failure}/0$,

so an answer set solver can be instructed to display only atoms of those
predicates in an answer set. For Alpha, this can be done with the command-line
arguments \--filter path_to_goal --filter cost_to_goal --filter failure.

Of course, our A* encoding also needs heuristic directives to work correctly.
Without heuristics, the encoding would just search arbitrarily through the
state-space and ignore the $f$-value of nodes. Therefore, our primary
heuristic directive prefers to choose those nodes from the frontier whose
$f$-value is the lowest.

$\displaystyle\mathtt{\\#heuristic}\ \mathrm{explore(PS,A)}:\;$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(PS,A)},$
$\displaystyle\mathrm{not}~{}\mathrm{suboptimal\\_step(PS,A)},$
$\displaystyle\mathrm{f(PS,A,PathCost)},\mathrm{not}~{}\mathbf{T}\
\mathrm{goal\\_found}.\;[-\mathrm{PathCost}@3]$

A second heuristic directive closes unassigned choice points when the goal is
found.

$\displaystyle\mathtt{\\#heuristic}\ \mathbf{F}\ \mathrm{explore(PS,A)}:\;$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(PS,A)},$
$\displaystyle\mathbf{T}\ \mathrm{goal\\_found}.\;[1@2]$

The heuristics we created for Alpha cannot be used with clingo due to the
usage of $\mathbf{T}$ and default negation. To assess the performance of
clingo, we have also created an encoding omitting unsupported literals in
heuristic conditions. Furthermore, an Alpha encoding with heuristics without
our novel features, compliant with those employed by clingo, has been created.

##### Generating States on Demand.

In many practical domains, the number of states is vast, thus prohibiting the
upfront generation of all states. For example, in the well-known 8-puzzle,
$181,440$ distinct states are reachable. While this is a manageable number,
the corresponding number for the 15-puzzle is already about $10^{13}$ (?).

Since only a small fraction of all states is usually explored by A* (depending
on the quality of the heuristic function), a crucial memory-saving feature is
to generate only the states that A* needs. Our approach can generate states on
demand using the interface between problem-specific encoding and A* encoding
bidirectionally instead of just passing information from the problem-specific
encoding to A*.

As described above, predicates $\mathrm{init}/1$, $\mathrm{goal}/1$,
$\mathrm{c}/4$, and $\mathrm{h}/2$ are defined in the problem-specific
encoding and accessed by the A* encoding. In the other direction, the problem-
specific encoding can access the
$\mathrm{frontier\\_and\\_explored\\_states}/2$ predicate defined in the
problem-independent A* encoding to generate states on demand, for example, by
introducing a new $\mathrm{state}/1$ predicate:

$\displaystyle\mathrm{state(InitState)}\leftarrow\;$
$\displaystyle\mathrm{init(InitState)}.$
$\displaystyle\mathrm{state(GoalState)}\leftarrow\;$
$\displaystyle\mathrm{goal(GoalState)}.$
$\displaystyle\mathrm{state(ChildState)}\leftarrow\;$
$\displaystyle\mathrm{frontier\\_and\\_explored\\_states(ParentState,Action)},$
$\displaystyle\mathrm{result(ParentState,Action,ChildState)}.$

This new $\mathrm{state}/1$ predicate can then be used in the body of rules
deriving $\mathrm{c}/4$ and $\mathrm{h}/2$ to derive also information on step
cost and heuristic values only on-demand, utilising lazy grounding. Deriving
this information on-demand is not possible with ground-and-solve.

##### Real-World Routing.

To test our A* encoding on real world routing problems, we obtained a graph
representation of the walkable street network for the first district of
Vienna, Austria, from OpenStreetMap,212121https://www.openstreetmap.org
employing the OSMnx Python library (?).222222https://github.com/gboeing/osmnx
We then pre-processed the graph by consolidating intersections (merging nodes
located within 15m of each other) and removing parallel edges. Figure 9 shows
the resulting graph, which contains 462 nodes and 1632 edges.

Figure 9: Vienna’s first district

We have generated 100 instances, each consisting of the following atoms:

  * •

1632 atoms of the predicate $\mathrm{edge}/3$, in which the first two
arguments denote two nodes connected by an edge and the third argument denotes
the length of the edge in meters,

  * •

$106,953$ atoms232323Since the graph contains $n=462$ nodes, there are
$\frac{n\cdot(n+1)}{2}=106,953$ unique pairs of nodes including reflexive
pairs. of the predicate $\mathrm{distance}/3$, in which the first two
arguments denote nodes and the third argument denotes the euclidean distance
between them in meters,

  * •

one atom of the predicate $\mathrm{origin}/1$ denoting the origin node of the
route to be computed, and

  * •

one atom of the predicate $\mathrm{destination}/1$ denoting the destination
node of the route to be computed.

The set of $\mathrm{edge}/3$ and $\mathrm{distance}/3$ atoms encodes the
street network graph and is the same in each of the 100 instances. Origin and
destination nodes, however, have been chosen randomly for each instance.

The problem-specific encoding for street network routing then consists of only
the following five rules:

$\displaystyle\mathrm{init(at(N))}\leftarrow\;$
$\displaystyle\mathrm{origin(N)}.$
$\displaystyle\mathrm{goal(at(N))}\leftarrow\;$
$\displaystyle\mathrm{destination(N)}.$
$\displaystyle\mathrm{c(at(X),move(Y),at(Y),Length)}\leftarrow\;$
$\displaystyle\mathrm{edge(X,Y,Length)}.$
$\displaystyle\mathrm{h(at(X),Distance)}\leftarrow\;$
$\displaystyle\mathrm{destination(Y),distance(X,Y,Distance)}.$
$\displaystyle\mathrm{distance(Y,X,Distance)}\leftarrow\;$
$\displaystyle\mathrm{distance(X,Y,Distance)}.$

####  6.4.3 Results

alpha ($\displaystyle k_{\mathrm{co}}=0$) (13)alpha ($\displaystyle
k_{\mathrm{co}}=\infty$) (12)dlv2 (8)h-alpha ($\displaystyle
k_{\mathrm{co}}=0$) (72)h-alpha ($\displaystyle k_{\mathrm{co}}=\infty$)
(20)h-alpha (with h-clingo heuristics, $\displaystyle k_{\mathrm{co}}=0$)
(69)h-alpha (with h-clingo heuristics, $\displaystyle k_{\mathrm{co}}=\infty$)
(19)clingo (8)h-clingo (10)

(a) Solver configurations, with numbers of solved instances

$\displaystyle{0}$$\displaystyle{8}$$\displaystyle{16}$$\displaystyle{24}$$\displaystyle{32}$$\displaystyle{40}$$\displaystyle{48}$$\displaystyle{56}$$\displaystyle{64}$$\displaystyle{72}$Number
of
instances$\displaystyle{10^{0}}$$\displaystyle{10^{1}}$$\displaystyle{10^{2}}$$\displaystyle{10^{3}}$$\displaystyle{10^{4}}$$\displaystyle{10^{5}}$$\displaystyle{10^{6}}$Number
of guesses

(b) Number of guesses

$\displaystyle{0}$$\displaystyle{8}$$\displaystyle{16}$$\displaystyle{24}$$\displaystyle{32}$$\displaystyle{40}$$\displaystyle{48}$$\displaystyle{56}$$\displaystyle{64}$$\displaystyle{72}$Number
of
instances$\displaystyle{0}$$\displaystyle{2}$$\displaystyle{4}$$\displaystyle{6}$$\displaystyle{8}$$\displaystyle{10}$$\displaystyle{12}$$\displaystyle{14}$Real
time (minutes)

(c) Time consumption

$\displaystyle{0}$$\displaystyle{8}$$\displaystyle{16}$$\displaystyle{24}$$\displaystyle{32}$$\displaystyle{40}$$\displaystyle{48}$$\displaystyle{56}$$\displaystyle{64}$$\displaystyle{72}$Number
of
instances$\displaystyle{0}$$\displaystyle{4}$$\displaystyle{8}$$\displaystyle{12}$$\displaystyle{16}$$\displaystyle{20}$$\displaystyle{24}$$\displaystyle{28}$$\displaystyle{32}$$\displaystyle{36}$Memory
(GiB)

(d) Memory consumption

Figure 10: Resource consumption for solving each Pathfinding instance with A*

alpha ($\displaystyle k_{\mathrm{co}}=0$) (2)alpha ($\displaystyle
k_{\mathrm{co}}=\infty$) (2)dlv2 (0)h-alpha ($\displaystyle
k_{\mathrm{co}}=0$) (99)h-alpha ($\displaystyle k_{\mathrm{co}}=\infty$)
(99)h-alpha (with h-clingo heuristics, $\displaystyle k_{\mathrm{co}}=0$)
(99)h-alpha (with h-clingo heuristics, $\displaystyle k_{\mathrm{co}}=\infty$)
(99)clingo (0)h-clingo (0)

(a) Solver configurations, with numbers of solved instances

$\displaystyle{0}$$\displaystyle{15}$$\displaystyle{30}$$\displaystyle{45}$$\displaystyle{60}$$\displaystyle{75}$$\displaystyle{90}$Number
of instances$\displaystyle{10^{1}}$$\displaystyle{10^{2}}$Number of guesses

(b) Number of guesses

$\displaystyle{0}$$\displaystyle{15}$$\displaystyle{30}$$\displaystyle{45}$$\displaystyle{60}$$\displaystyle{75}$$\displaystyle{90}$Number
of
instances$\displaystyle{0.1}$$\displaystyle{0.2}$$\displaystyle{0.3}$$\displaystyle{0.4}$$\displaystyle{0.5}$$\displaystyle{0.6}$$\displaystyle{0.7}$$\displaystyle{0.8}$Real
time (minutes)

(c) Time consumption

$\displaystyle{0}$$\displaystyle{15}$$\displaystyle{30}$$\displaystyle{45}$$\displaystyle{60}$$\displaystyle{75}$$\displaystyle{90}$Number
of
instances$\displaystyle{2}$$\displaystyle{3}$$\displaystyle{4}$$\displaystyle{5}$$\displaystyle{6}$$\displaystyle{7}$$\displaystyle{8}$Memory
(GiB)

(d) Memory consumption

Figure 11: Resource consumption for solving each Routing instance with A*

Cactus plots for Pathfinding with A* (Figure 10) and Routing with A* (Figure
11) were generated in the same way as for HRP (cf. Section 6.2.4).

In the case of Pathfinding (Figure 10), Alpha with domain-specific heuristics
(h-alpha) solved the highest number of instances (72 out of 100). Like with
HRP, this performance could only be achieved when grounding constraints
strictly ($k_{\mathrm{co}}=0$), while permissive grounding of constraints
($k_{\mathrm{co}}=\infty$) resulted in lower performance, solving only 20
instances. Performance of Alpha with h-clingo-like heuristics was a bit lower.

On the other extreme, Alpha without domain-specific heuristics could solve
only 13 of the 100 instances.

The systems dlv2, clingo, and h-clingo performed somewhere in between those
extremes. Of the 72 instances solved by h-alpha, 18 are unsatisfiable, and of
the 10 instances solved by h-clingo, 9 are unsatisfiable. The largest instance
solved by h-alpha had a width of 400, and the largest instance for which
h-clingo could derive failure had a width of 470. Note that our heuristics are
designed to find solutions, not to efficiently prove unsatisfiability.

In the Routing domain (Figure 11), Alpha with domain-specific heuristics
(h-alpha) solved 99 of the 100 instances, while Alpha without domain-specific
heuristics could solve only two instances, and the other systems solved no
instances at all. Alpha with h-clingo-like heuristics solved the same number
of instances, but consumed more time and memory in doing so.

For each of the 8 Pathfinding instances solved by clingo, the system spent
between 88% and 100% of total solving time in grounding, on average 95%. When
using domain-specific heuristics, h-clingo solved 10 Pathfinding instances and
spent between 96% and 100% in grounding, on average more than 99% of overall
time. dlv2 solved 8 instances and spent between 15% and 55% of total solving
time in grounding, on average 43%. Neither clingo nor h-clingo nor dlv2
finished grounding for any of the Routing instances.

Note some peculiarities in Figures 10 and 11: In Figure 10(b), there is a
vertical line for clingo and dlv2. This is because for seven instances, these
two systems were able to derive failure without doing any guesses. Figure
11(b), on the other hand, shows a horizontal line for h-alpha with h-clingo
heuristics. This is because these heuristics do not represent A* correctly and
try to visit all 461 non-start nodes in almost every instance. In Figure
11(b), all lines for $k_{\mathrm{co}}=\infty$ are hidden by their respective
$k_{\mathrm{co}}=0$ counterparts because numbers of guesses coincide.

###  6.5 Discussion

Our results show that we have extended the application area of ASP. By
combining our novel approach to domain-specific heuristics with lazy-grounding
answer set solving, we could solve large-scale problem instances that are out
of reach for conventional ASP systems. This finding supports our initial
hypothesis that both lazy grounding and domain-specific heuristics are crucial
for solving large-scale industrial problems.

Our approach extends the one by ? (?), the first extension of ASP’s input
language by a declarative framework for domain-specific heuristics. ? (?) have
provided the first experimental evidence that such an approach can improve ASP
solving performance and also reported grounding issues with some instances.

Our advancement consists of novel syntax and semantics for heuristic
directives that make it possible to reason about the current partial
assignment, facilitating heuristics based on what has or has _not yet_ been
decided by the solver. Although the approach by ? (?) has worked very well on
planning problems, it seems that more flexibility in the definition of
heuristics, supported by the novel features of our approach, is necessary to
represent heuristics for other kinds of problems.

Our results undeniably show that domain-specific heuristics improve solving
performance for the domains under consideration. This is not only true for
Alpha but also for clingo. However, domain-specific heuristics usually
increase clingo’s memory consumption, thus exacerbating the grounding
bottleneck from which ground-and-solve systems such as clingo are suffering.
Domain-specific heuristics for dlv2 were out of scope because dlv2 does not
support the declarative specification of heuristics.

However, we do not claim that heuristics based on partial assignments are
always beneficial. Our findings cannot reject the possibility that h-clingo
might outperform h-alpha when other encodings or other heuristics are used
since there might be encoding optimisations that we have not thought of. We
even observed this situation with most competition instances of the Partner
Units Problem in our experiments. Still, we are confident that our approach’s
novel features make the specification of practical heuristics more intuitive
and effortless. Furthermore, in our experiments, Alpha usually performed worse
when employing clingo-like heuristics without our novel features.

Results for HRP (Figure 4) and A* (Figures 10 and 11) indicate that permissive
grounding (cf. ?), i.e., providing the solver with more nogoods representing
ground constraints than necessary, can be counterproductive when domain-
specific heuristics are used. We conjecture the reason for this to be that
suitable domain-specific heuristics can assist the solver even better than
additional constraints while avoiding the overhead of additional nogoods (in
terms of space consumption and propagation efforts). This assumption is
supported by the considerable increase in Alpha’s memory consumption when
grounding constraints permissively in those domains.

Closer investigation of this issue revealed that in both HRP and A*, one
single constraint was the source of the performance deterioration. In HRP, the
full and very large grounding for one specific constraint was produced before
the solver had even made a single choice. In A*, many ground nogoods were
produced for one constraint not necessary to find the optimal solution when
domain-specific heuristics are used.

The Partner Units Problem (PUP) proved more challenging for our approach than
the other domains under consideration. While the combination of lazy grounding
and domain-specific heuristics was able to solve large instances that are out
of reach of ground-and-solve systems, hard competition instances can be solved
by ground-and-solve systems even without domain-specific heuristics. In these
cases, domain-specific heuristics in Alpha did more harm than good, because
they caused a significant overhead and they are obviously not effective when
the full grounding and efficient solving techniques are available. However,
finding efficient encodings or heuristics for PUP is out of scope of this
paper. Future work should investigate whether another combination of encoding
and heuristic directives can help to solve instances that are both large and
hard to solve.

To sum up, domain-specific heuristics implemented in our novel framework,
combined with strict lazy grounding by Alpha, outperformed all other tested
systems when applied to large instances of the House Reconfiguration Problem,
the Partner Units Problem, and A* used with two different search problems.
Applications to other domains should be easy to put into practice and belong
to future work.

##  7 Conclusions and Future Work

We have proposed novel syntax and semantics for declarative domain-specific
heuristics in ASP that can depend non-monotonically on the partial assignment
maintained during solving. Furthermore, we have demonstrated how to integrate
our approach in a lazy-grounding ASP system and presented experimental results
obtained with the lazy-grounding solver Alpha.

Our semantics has proven beneficial for several practical application domains,
advancing the work by ? (?). In experiments, our implementation exhibited
convincing time and memory consumption behaviour. Thus, we extended the
application area of ASP by solving large problem instances that conventional
ASP systems could not solve.

Our approach’s suitability to implement other practice-oriented heuristics
should be assessed by the community. Some real-world domain-specific
heuristics will require extensions of our approach, such as by supporting
randomness and restarts. Furthermore, adopting ideas like init and factor
modifiers from clingo, and investigating the special role of aggregates in
heuristic conditions should be addressed in future work. An adaption to
ground-and-solve systems like clingo (?) or dlv2 (?) should be investigated,
also addressing the question of how heuristics interact with non-head-cycle-
free disjunction.

Thinking more broadly, the question of how to generate domain-specific
heuristics automatically is of great importance since, currently, such
heuristics have to be invented by humans familiar with the domain (and partly
also with solving technology).

Acknowledgments

This work has been conducted in the scope of the research project DynaCon
(FFG-PNr.: 861263), which was funded by the Austrian Federal Ministry for
Climate Action, Environment, Energy, Mobility, Innovation and Technology (BMK)
under the program “ICT of the Future” (via the project _DynaCon_ , FFG-PNr.:
861263) between 2017 and 2020.242424See https://iktderzukunft.at/en/ for more
information. This research was also supported by the Academy of Finland,
project 251170, and by EU ECSEL Joint Undertaking under grant agreement no.
737459 (project Productive4.0).

We are thankful to Peter Schüller for his contributions to our earlier
conference paper on this topic, Martin Gebser for proofreading this article,
Andreas Falkner for his comments on an earlier version of this paper, Stephen
Cummings for language editing, and the anonymous reviewers of ICLP 2019 and
the Journal of Artificial Intelligence Research for their helpful reviews.

##  A Proofs

###### Proof sketch for Lemma 2.

Since heads of heuristic directives are unaffected by the transformation, it
suffices to show that $\mathsf{\mathsf{cond}}(d)$ is satisfied iff $\exists
d^{\prime}\in\mathsf{tf{}}(d)$ s.t. $\mathsf{\mathsf{cond}}(d^{\prime})$ is
satisfied (cf. Definitions 3 and 4). Furthermore, it suffices to consider the
conditions under which the affected heuristic atoms are satisfied (cf.
Definition 2).

Case $\langle$8e$\rangle$ is trivial.

For $\langle$8a$\rangle$ and $\langle$8d$\rangle$, $\mathsf{tf{}}(d)$ maps $d$
to two new directives, i.e.,
$\mathsf{tf{}}(d)=\\{d^{\prime},d^{\prime\prime}\\}$ and $d^{\prime}\neq
d^{\prime\prime}$. Let $s~{}a$ be the heuristic atom in
$\mathsf{\mathsf{cond}}(d)$ affected by the transformation. In both cases,
$\langle$8a$\rangle$ and $\langle$8d$\rangle$, $s~{}a$ is removed from
$\mathsf{\mathsf{cond}}(d)$, one atom is added to (the positive or negative
part of) $\mathsf{\mathsf{cond}}(d^{\prime})$, and one atom is added to (the
positive or negative part of) $\mathsf{\mathsf{cond}}(d^{\prime\prime})$. Let
us call these new atoms $s^{\prime}~{}a$ and $s^{\prime\prime}~{}a$.

For $\langle$8a$\rangle$, all atoms mentioned occur in the positive part of
the condition, i.e., $s~{}a\in\mathsf{\mathsf{cond}^{+}}(d)$,
$s^{\prime}~{}a\in\mathsf{\mathsf{cond}^{+}}(d^{\prime})$, and
$s^{\prime\prime}~{}a\in\mathsf{\mathsf{cond}^{+}}(d^{\prime\prime})$. So we
now have to show that $s~{}a$ is satisfied iff $s^{\prime}~{}a$ is satisfied
or $s^{\prime\prime}~{}a$ is satisfied. For example, if
$s=\mathbf{F}\mathbf{M}$, then $s^{\prime}=\mathbf{M}$ and
$s^{\prime\prime}=\mathbf{F}$. Since a heuristic atom $s~{}a$ is satisfied
w.r.t. an assignment $A$ iff $\mathsf{truth}_{A}(a)\in s$ (cf. Definition 2),
it is obvious that $\mathbf{F}\mathbf{M}~{}a$ is satisfied iff
$\mathbf{M}~{}a$ is satisfied or $\mathbf{F}~{}a$ is satisfied.

The other cases can be shown in a similar way. ∎

###### Proof of Lemma 3.

“$\Rightarrow$”: Let $\mathsf{truth}_{A}(h)=\mathbf{T}$, resp.
$\mathsf{truth}_{A}(h)=\mathbf{M}$, and note that Alpha is only guessing the
truth value of an atom if that atom represents an applicable rule, i.e., it is
of the form $\beta(r,\sigma)$ (cf. Section 5.3 and ? (?)). Since $h$ is not of
such a form, Alpha therefore only assigns $h$ to $\mathbf{T}$, respectively
$\mathbf{M}$, if it is propagated. Observe that all nogoods from
$\langle$15$\rangle$-$\langle$20$\rangle$ are such that the heuristic atom
only appears with negative polarity in it, i.e., $h$ appears as
$\mathbf{F}h\in ng$. Furthermore, since there are no other nogoods that
contain $h$, the only way for $\mathsf{truth}_{A}(h)=\mathbf{T}$, respectively
$\mathsf{truth}_{A}(h)=\mathbf{M}$, to hold is by $ng$ being unit in
$A^{\prime}=A\setminus\\{\mathbf{T}h,\mathbf{M}h\\}$.

Notice that the polarity of $h$ is negative in all nogoods. Since Alpha does
not guess on $h$, it is impossible for $ng$ to be involved in a conflict, as
$h$ is unassigned until $ng$ is unit and then $h$ will be assigned such that
$ng$ is not violated and by that all other nogoods containing $h$ can no
longer become violated. This implies that $ng$ also is never directly involved
in the mechanics of conflict-driven learning, hence learning will not create
additional nogoods that contain $h$.

“$\Leftarrow$”: Let one nogood $ng$ of the form
$\langle$15$\rangle$-$\langle$20$\rangle$ be unit w.r.t.
$A^{\prime}=A\setminus\\{\mathbf{T}h,\mathbf{M}h\\}$, then unit propagation on
$ng$ will lead to an extended assignment where $h$ is assigned $\mathbf{T}$,
respectively $\mathbf{M}$, i.e.,
$\mathsf{prop}(ng,A^{\prime})=\\{\mathbf{T},\mathbf{M}\\}$, respectively
$\mathsf{prop}(ng,A^{\prime})=\\{\mathbf{M}\\}$, and the resulting assignment
$A$ is such that $\mathsf{truth}_{A}(h)=\mathbf{T}$, respectively
$\mathsf{truth}_{A}(h)=\mathbf{M}$, holds.

∎

###### Proof of Lemma 4.

“$\Rightarrow$”: Let $\mathsf{\mathsf{cond}}(d)$ be satisfied w.r.t. $A$ and
$P$, i.e., every $ha\in\mathsf{\mathsf{cond}^{+}}(d)$ is satisfied and no
$ha\in\mathsf{\mathsf{cond}^{-}}(d)$ is satisfied. We have to show that $d$ is
solving-satisfied w.r.t. $A^{\Delta_{P}}$, i.e., all of the following hold:

  1. (1)

$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnT}(d))=\mathbf{T}$,

  2. (2)

$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnMT}(d))\in\\{\mathbf{M},\mathbf{T}\\}$,

  3. (3)

$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnF}(d))=\mathbf{T}$,

  4. (4)

$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffT}(d))\neq\mathbf{T}$,

  5. (5)

$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffMT}(d))\notin\\{\mathbf{M},\mathbf{T}\\}$,
and

  6. (6)

$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffF}(d))\neq\mathbf{T}$.

(1) Since every $ha\in\mathsf{\mathsf{cond}^{+}}(d)$ is satisfied, it holds by
Definition 2 that $\mathsf{truth}_{A}(\mathsf{atom}(ha))$ $\in$
$\mathsf{signs}(ha)$. This specifically implies for every
$a\in\mathsf{atom}(\mathsf{\mathsf{cond}^{+}}(d)|_{\mathbf{T}})$ that
$\mathsf{truth}_{A}(a)=\mathbf{T}$. Hence, the nogood $g$ of the form
$\langle$15$\rangle$ is unit w.r.t. $A$, i.e.,
$\mathbf{T}~{}\mathrm{HeuOnT}(d)\in\mathsf{prop}(g,A)$ and consequently
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnT}(d))=\mathbf{T}$.
(2) The proof is analogeous to (1) relying on the nogood of the form
$\langle$16$\rangle$ to show that
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnMT}(d))\in\\{\mathbf{M},\mathbf{T}\\}$.
(3) The proof is analogeous to (1) relying on the nogood of the form
$\langle$17$\rangle$ to show that
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnF}(d))=\mathbf{T}$.
(4) Since no $ha\in\mathsf{\mathsf{cond}^{-}}(d)$ is satisfied w.r.t. $A$, it
holds for every $\mathbf{T}a\in\mathsf{\mathsf{cond}^{-}}(d)$ that
$\mathsf{truth}_{A}(a)\neq\mathbf{T}$. Consequently, no nogood of the form
$\langle$18$\rangle$ is unit w.r.t. $A$. From Lemma 3 it then follows that
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffT}(d))\neq\mathbf{T}$.
(5) The proof is analogeous to (4) relying on the nogood(s) of the form
$\langle$19$\rangle$ and Lemma 3 to show that
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffMT}(d))\notin\\{\mathbf{M},\mathbf{T}\\}$.
(6) The proof is analogeous to (4) relying on the nogood(s) of the form
$\langle$20$\rangle$ and Lemma 3 to show that
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffF}(d))\neq\mathbf{T}$.

From the above follows that $d$ is solving-satisfied w.r.t. $A^{\Delta_{P}}$.

“$\Leftarrow$”: Let $d$ be solving-satisfied w.r.t. $A^{\Delta_{P}}$, i.e.,
(1) $\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnT}(d))=\mathbf{T}$,
(2)
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnMT}(d))\in\\{\mathbf{M},\mathbf{T}\\}$,
(3) $\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnF}(d))=\mathbf{T}$,
(4) $\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffT}(d))\neq\mathbf{T}$,  (5)
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffMT}(d))\notin\\{\mathbf{M},\mathbf{T}\\}$,
and
(6) $\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffF}(d))\neq\mathbf{T}$.
From Lemma 3 and
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOnT}(d))=\mathbf{T}$ it directly
follows that the nogood of the form $\langle$15$\rangle$ is unit w.r.t. $A$.
Since $A$ is deductively consistent with $P$ it holds for every
$a\in\mathsf{atom}(\mathsf{\mathsf{cond}^{+}}(d)|_{\mathbf{T}})$ that
$\mathsf{truth}_{A}(a)=\mathbf{T}$ and consequently, that every
$ha\in\mathsf{\mathsf{cond}^{+}}(d)|_{\mathbf{T}}$ is satisfied w.r.t. $A$. By
an analogeous argument it also follows that that every
$ha\in\mathsf{\mathsf{cond}^{+}}(d)|_{\mathbf{M}\mathbf{T}}$ is satisfied
w.r.t. $A$ and that every $ha\in\mathsf{\mathsf{cond}^{+}}(d)|_{\mathbf{F}}$
is satisfied w.r.t. $A$.

Likewise, from
$\mathsf{truth}_{A^{\Delta_{P}}}(\mathrm{HeuOffT}(d))\neq\mathbf{T}$, Lemma 3,
and every nogood $g$ of the form $\langle$18$\rangle$ it also follows that
$\mathbf{T}a\in\mathsf{\mathsf{cond}^{-}}(d)$ is not assigned true w.r.t. $A$,
i.e., $\mathsf{truth}_{A}(a)\neq\mathbf{T}$. By Definition 2 it therefore
follows that no
$a\in\mathsf{atom}(\mathsf{\mathsf{cond}^{-}}(d)|_{\mathbf{T}})$ is satisfied
w.r.t. $A$. By analogeous arguments it also follows that no
$a\in\mathsf{atom}(\mathsf{\mathsf{cond}^{-}}(d)|_{\mathbf{M}\mathbf{T}})$ and
no $a\in\mathsf{atom}(\mathsf{\mathsf{cond}^{-}}(d)|_{\mathbf{F}})$ is
satisfied w.r.t. $A$, i.e., no
$ha\in\mathsf{atom}(\mathsf{\mathsf{cond}^{-}}(d))$ is satisfied w.r.t. $A$.

Since every $ha\in\mathsf{\mathsf{cond}^{+}}(d)$ is satisfied w.r.t. $A$ and
no $ha\in\mathsf{\mathsf{cond}^{-}}(d)$ is satisfied w.r.t. $A$, it follows
that $\mathsf{\mathsf{cond}}(d)$ is satisfied w.r.t. $A$.

∎

## References

  * Adrian et al. Adrian, W. T., Alviano, M., Calimeri, F., Cuteri, B., Dodaro, C., Faber, W., Fuscà, D., Leone, N., Manna, M., Perri, S., Ricca, F., Veltri, P., and Zangari, J. (2018).  The ASP system DLV: advancements and applications.  Künstliche Intell., 32(2-3), 177–179.
  * Alviano et al. Alviano, M., Amendola, G., Dodaro, C., Leone, N., Maratea, M., and Ricca, F. (2019).  Evaluation of disjunctive programs in WASP.  In Balduccini, M., Lierler, Y., and Woltran, S. (Eds.), Logic Programming and Nonmonotonic Reasoning - 15th International Conference, LPNMR 2019, Philadelphia, PA, USA, June 3-7, 2019, Proceedings, Vol. 11481 of Lecture Notes in Computer Science, pp. 241–255. Springer.
  * Alviano et al. Alviano, M., Calimeri, F., Dodaro, C., Fuscà, D., Leone, N., Perri, S., Ricca, F., Veltri, P., and Zangari, J. (2017).  The ASP system DLV2.  In Balduccini, M., and Janhunen, T. (Eds.), Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR 2017, Espoo, Finland, July 3-6, 2017, Proceedings, Vol. 10377 of Lecture Notes in Computer Science, pp. 215–221. Springer.
  * Alviano et al. Alviano, M., Calimeri, F., Faber, W., Ianni, G., and Leone, N. (2011).  Function symbols in ASP: Overview and perspectives.  In Brewka, G., Marek, V., and Truszczyǹski, M. (Eds.), Nonmonotonic Reasoning at 30, Vol. 31 of Studies in Logic, pp. 1–24. College Publications.
  * Arias et al. Arias, J., Carro, M., Salazar, E., Marple, K., and Gupta, G. (2018).  Constraint answer set programming without grounding.  Theory Pract. Log. Program., 18(3-4), 337–354.
  * Baral Baral, C. (2003).  Knowledge Representation, Reasoning and Declarative Problem Solving.  Cambridge University Press.
  * Ben-Eliyahu and Dechter Ben-Eliyahu, R., and Dechter, R. (1994).  Propositional semantics for disjunctive logic programs.  Ann. Math. Artif. Intell., 12(1-2), 53–87.
  * Boeing Boeing, G. (2017).  OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks.  Comput. Environ. Urban Syst., 65, 126–139.
  * Bogaerts and Weinzierl Bogaerts, B., and Weinzierl, A. (2018).  Exploiting justifications for lazy grounding of answer set programs.  In Lang, J. (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pp. 1737–1745. ijcai.org.
  * Bomanson et al. Bomanson, J., Janhunen, T., and Weinzierl, A. (2019).  Enhancing lazy grounding with lazy normalization in answer-set programming.  In AAAI, pp. 2694–2702. AAAI Press.
  * Cabalar et al. Cabalar, P., Rey, M., and Vidal, C. (2019).  A complete planner for temporal answer set programming.  In Oliveira, P. M., Novais, P., and Reis, L. P. (Eds.), Progress in Artificial Intelligence, 19th EPIA Conference on Artificial Intelligence, EPIA 2019, Vila Real, Portugal, September 3-6, 2019, Proceedings, Part II, Vol. 11805 of Lecture Notes in Computer Science, pp. 520–525. Springer.
  * Calimeri et al. Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Maratea, M., Ricca, F., and Schaub, T. (2020).  ASP-Core-2 input language format.  Theory Pract. Log. Program., 20(2), 294–309.
  * Calimeri et al. Calimeri, F., Fuscà, D., Perri, S., and Zangari, J. (2017).  I-DLV: the new intelligent grounder of DLV.  Intelligenza Artificiale, 11(1), 5–20.
  * Calimeri et al. Calimeri, F., Gebser, M., Maratea, M., and Ricca, F. (2016).  Design and results of the fifth answer set programming competition.  Artif. Intell., 231, 151–181.
  * Calimeri et al. Calimeri, F., Ianni, G., and Ricca, F. (2014).  The third open answer set programming competition.  Theory Pract. Log. Program., 14(1), 117–135.
  * Cat et al. Cat, B. D., Denecker, M., Bruynooghe, M., and Stuckey, P. J. (2015).  Lazy model expansion: Interleaving grounding with search.  J. Artif. Intell. Res., 52, 235–286.
  * Dantsin et al. Dantsin, E., Eiter, T., Gottlob, G., and Voronkov, A. (1997).  Complexity and expressive power of logic programming.  In Computational Complexity Conference, pp. 82–101. IEEE Computer Society.
  * Dao-Tran et al. Dao-Tran, M., Eiter, T., Fink, M., Weidinger, G., and Weinzierl, A. (2012).  Omiga : An open minded grounding on-the-fly answer set solver.  In del Cerro, L. F., Herzig, A., and Mengin, J. (Eds.), Logics in Artificial Intelligence - 13th European Conference, JELIA 2012, Toulouse, France, September 26-28, 2012. Proceedings, Vol. 7519 of Lecture Notes in Computer Science, pp. 480–483. Springer.
  * Dodaro et al. Dodaro, C., Galatà, G., Khan, M. K., Maratea, M., and Porro, I. (2019).  An asp-based solution for operating room scheduling with beds management.  In Fodor, P., Montali, M., Calvanese, D., and Roman, D. (Eds.), Rules and Reasoning - Third International Joint Conference, RuleML+RR 2019, Bolzano, Italy, September 16-19, 2019, Proceedings, Vol. 11784 of Lecture Notes in Computer Science, pp. 67–81. Springer.
  * Dodaro et al. Dodaro, C., Gasteiger, P., Leone, N., Musitsch, B., Ricca, F., and Schekotihin, K. (2016).  Combining answer set programming and domain heuristics for solving hard industrial problems (application paper).  Theory Pract. Log. Program., 16(5-6), 653–669.
  * Eiter et al. Eiter, T., Faber, W., Fink, M., and Woltran, S. (2007).  Complexity results for answer set programming with bounded predicate arities and implications.  Ann. Math. Artif. Intell., 51(2-4), 123–165.
  * Eiter et al. Eiter, T., Faber, W., Leone, N., Pfeifer, G., and Polleres, A. (2003).  A logic programming approach to knowledge-state planning, II: the dlv${}^{\mbox{k}}$ system.  Artif. Intell., 144(1-2), 157–211.
  * Erdem et al. Erdem, E., Gelfond, M., and Leone, N. (2016).  Applications of answer set programming.  AI Magazine, 37(3), 53–68.
  * Faber et al. Faber, W., Leone, N., and Perri, S. (2012).  The intelligent grounder of DLV.  In Correct Reasoning, Vol. 7265 of Lecture Notes in Computer Science, pp. 247–264. Springer.
  * Faber et al. Faber, W., Leone, N., and Pfeifer, G. (1999).  Pushing goal derivation in DLP computations.  In Gelfond, M., Leone, N., and Pfeifer, G. (Eds.), Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR’99, El Paso, Texas, USA, December 2-4, 1999, Proceedings, Vol. 1730 of Lecture Notes in Computer Science, pp. 177–191. Springer.
  * Faber et al. Faber, W., Pfeifer, G., and Leone, N. (2011).  Semantics and complexity of recursive aggregates in answer set programming.  Artif. Intell., 175(1), 278–298.
  * Falkner et al. Falkner, A. A., Friedrich, G., Haselböck, A., Schenner, G., and Schreiner, H. (2016).  Twenty-five years of successful application of constraint technologies at Siemens.  AI Magazine, 37(4), 67–80.
  * Falkner et al. Falkner, A. A., Friedrich, G., Schekotihin, K., Taupe, R., and Teppan, E. C. (2018).  Industrial applications of answer set programming.  Künstliche Intell., 32(2-3), 165–176.
  * Ferraris et al. Ferraris, P., Lee, J., and Lifschitz, V. (2011).  Stable models and circumscription.  Artif. Intell., 175(1), 236–263.
  * Friedrich et al. Friedrich, G., Ryabokon, A., Falkner, A. A., Haselböck, A., Schenner, G., and Schreiner, H. (2011).  (re)configuration using answer set programming.  In Shchekotykhin, K. M., Jannach, D., and Zanker, M. (Eds.), Proceedings of the IJCAI 2011 Workshop on Configuration, Barcelona, Spain, July 16, 2011, Vol. 755 of CEUR Workshop Proceedings, pp. 17–24. CEUR-WS.org.
  * Gebser et al. Gebser, M., Kaminski, R., Kaufmann, B., Lindauer, M., Ostrowski, M., Romero, J., Schaub, T., Thiele, S., and Wanko, P. (2019).  Potassco guide version 2.2.0.  Retrieved from https://github.com/potassco/guide/releases/tag/v2.2.0.
  * Gebser et al. Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. (2012).  Answer Set Solving in Practice.  Morgan and Claypool Publishers.
  * Gebser et al. Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. (2019).  Multi-shot ASP solving with clingo.  Theory Pract. Log. Program., 19(1), 27–82.
  * Gebser et al. Gebser, M., Kaminski, R., König, A., and Schaub, T. (2011).  Advances in _gringo_ series 3.  In Delgrande, J. P., and Faber, W. (Eds.), Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, Vol. 6645 of Lecture Notes in Computer Science, pp. 345–351. Springer.
  * Gebser et al. Gebser, M., Kaufmann, B., Romero, J., Otero, R., Schaub, T., and Wanko, P. (2013).  Domain-specific heuristics in answer set programming.  In desJardins, M., and Littman, M. L. (Eds.), Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA. AAAI Press.
  * Gebser et al. Gebser, M., Kaufmann, B., and Schaub, T. (2012).  Conflict-driven answer set solving: From theory to practice.  Artif. Intell., 187, 52–89.
  * Gebser et al. Gebser, M., Leone, N., Maratea, M., Perri, S., Ricca, F., and Schaub, T. (2018).  Evaluation techniques and systems for answer set programming: a survey.  In Lang, J. (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pp. 5450–5456. ijcai.org.
  * Gebser et al. Gebser, M., Maratea, M., and Ricca, F. (2017).  The sixth answer set programming competition.  J. Artif. Intell. Res., 60, 41–95.
  * Gebser et al. Gebser, M., Maratea, M., and Ricca, F. (2020).  The seventh answer set programming competition: Design and results.  Theory Pract. Log. Program., 20(2), 176–204.
  * Gebser et al. Gebser, M., Obermeier, P., Schaub, T., Ratsch-Heitmann, M., and Runge, M. (2018).  Routing driverless transport vehicles in car assembly with answer set programming.  Theory Pract. Log. Program., 18(3-4), 520–534.
  * Gelfond and Kahl Gelfond, M., and Kahl, Y. (2014).  Knowledge Representation, Reasoning, and the Design of Intelligent Agents: The Answer-Set Programming Approach.  Cambridge University Press.
  * Hart et al. Hart, P. E., Nilsson, N. J., and Raphael, B. (1968).  A formal basis for the heuristic determination of minimum cost paths.  IEEE Trans. Syst. Sci. Cybern., 4(2), 100–107.
  * Hoos et al. Hoos, H. H., Lindauer, M., and Schaub, T. (2014).  claspfolio 2: Advances in algorithm selection for answer set programming.  Theory Pract. Log. Program., 14(4-5), 569–585.
  * Kaufmann et al. Kaufmann, B., Leone, N., Perri, S., and Schaub, T. (2016).  Grounding and solving in answer set programming.  AI Magazine, 37(3), 25–32.
  * Lefèvre et al. Lefèvre, C., Béatrix, C., Stéphan, I., and Garcia, L. (2017).  ASPeRiX, a first-order forward chaining approach for answer set computing.  Theory Pract. Log. Program., 17(3), 266–310.
  * Lefèvre and Nicolas Lefèvre, C., and Nicolas, P. (2009).  A first order forward chaining approach for answer set computing.  In Erdem, E., Lin, F., and Schaub, T. (Eds.), Logic Programming and Nonmonotonic Reasoning, 10th International Conference, LPNMR 2009, Potsdam, Germany, September 14-18, 2009. Proceedings, Vol. 5753 of Lecture Notes in Computer Science, pp. 196–208. Springer.
  * Leone et al. Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., and Scarcello, F. (2006).  The DLV system for knowledge representation and reasoning.  ACM Trans. Comput. Log., 7(3), 499–562.
  * Leone and Ricca Leone, N., and Ricca, F. (2015).  Answer set programming: A tour from the basics to advanced development tools and industrial applications.  In Faber, W., and Paschke, A. (Eds.), Reasoning Web, Vol. 9203 of Lecture Notes in Computer Science, pp. 308–326. Springer.
  * Leutgeb and Weinzierl Leutgeb, L., and Weinzierl, A. (2017).  Techniques for efficient lazy-grounding ASP solving.  In Seipel, D., Hanus, M., and Abreu, S. (Eds.), Declarative Programming and Knowledge Management - Conference on Declarative Programming, DECLARE 2017, Unifying INAP, WFLP, and WLP, Würzburg, Germany, September 19-22, 2017, Revised Selected Papers, Vol. 10997 of Lecture Notes in Computer Science, pp. 132–148. Springer.
  * Lifschitz Lifschitz, V. (2019).  Answer Set Programming.  Springer.
  * Lintao Zhang et al. Lintao Zhang, Madigan, C. F., Moskewicz, M. H., and Malik, S. (2001).  Efficient conflict driven learning in a boolean satisfiability solver.  In IEEE/ACM International Conference on Computer Aided Design, ICCAD 2001, IEEE/ACM Digest of Technical Papers, pp. 279–285. IEEE.
  * Liu et al. Liu, L., Pontelli, E., Son, T. C., and Truszczynski, M. (2007).  Logic programs with abstract constraint atoms: The role of computations.  In Dahl, V., and Niemelä, I. (Eds.), Logic Programming, 23rd International Conference, ICLP 2007, Porto, Portugal, September 8-13, 2007, Proceedings, Vol. 4670 of Lecture Notes in Computer Science, pp. 286–301. Springer.
  * Maratea et al. Maratea, M., Pulina, L., and Ricca, F. (2015).  Advances in multi-engine ASP solving.  In Gavanelli, M., Lamma, E., and Riguzzi, F. (Eds.), AI*IA 2015, Advances in Artificial Intelligence - XIVth International Conference of the Italian Association for Artificial Intelligence, Ferrara, Italy, September 23-25, 2015, Proceedings, Vol. 9336 of Lecture Notes in Computer Science, pp. 179–190. Springer.
  * Marple et al. Marple, K., Salazar, E., and Gupta, G. (2017).  Computing stable models of normal logic programs without grounding.  CoRR, abs/1709.00501.
  * Moskewicz et al. Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., and Malik, S. (2001).  Chaff: Engineering an efficient SAT solver.  In Proceedings of the 38th Design Automation Conference, DAC 2001, Las Vegas, NV, USA, June 18-22, 2001, pp. 530–535. ACM.
  * Palù et al. Palù, A. D., Dovier, A., Pontelli, E., and Rossi, G. (2009).  GASP: answer set programming with lazy grounding.  Fundam. Inform., 96(3).
  * Pearl Pearl, J. (1984).  Heuristics - intelligent search strategies for computer problem solving.  Addison-Wesley series in artificial intelligence. Addison-Wesley.
  * Redl Redl, C. (2016).  Automated benchmarking of KR-systems.  In Bistarelli, S., Formisano, A., and Maratea, M. (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, Vol. 1745 of CEUR Workshop Proceedings, pp. 45–56. CEUR-WS.org.
  * Ricca et al. Ricca, F., Grasso, G., Alviano, M., Manna, M., Lio, V., Iiritano, S., and Leone, N. (2012).  Team-building with answer set programming in the Gioia-Tauro seaport.  TPLP, 12(3), 361–381.
  * Russell and Norvig Russell, S. J., and Norvig, P. (2010).  Artificial Intelligence - A Modern Approach, Third International Edition.  Pearson Education.
  * Silva et al. Silva, J. P. M., Lynce, I., and Malik, S. (2009).  Conflict-driven clause learning SAT solvers.  In Handbook of Satisfiability, pp. 131–153. IOS Press.
  * Taupe et al. Taupe, R., Schekotihin, K., Schüller, P., Weinzierl, A., and Friedrich, G. (2019a).  Exploiting partial knowledge in declarative domain-specific heuristics for ASP.  In Bogaerts, B., Erdem, E., Fodor, P., Formisano, A., Ianni, G., Inclezan, D., Vidal, G., Villanueva, A., Vos, M. D., and Yang, F. (Eds.), Proceedings 35th International Conference on Logic Programming (Technical Communications), ICLP 2019 Technical Communications, Las Cruces, NM, USA, September 20-25, 2019, Vol. 306 of EPTCS, pp. 22–35.
  * Taupe et al. Taupe, R., Weinzierl, A., and Friedrich, G. (2019b).  Degrees of laziness in grounding - effects of lazy-grounding strategies on ASP solving.  In Balduccini, M., Lierler, Y., and Woltran, S. (Eds.), Logic Programming and Nonmonotonic Reasoning - 15th International Conference, LPNMR 2019, Philadelphia, PA, USA, June 3-7, 2019, Proceedings, Vol. 11481 of Lecture Notes in Computer Science, pp. 298–311. Springer.
  * Teppan Teppan, E. C. (2016).  Solving the partner units configuration problem with heuristic constraint answer set programming.  In Configuration Workshop, pp. 61–68.
  * Teppan and Friedrich Teppan, E. C., and Friedrich, G. (2016).  Heuristic constraint answer set programming.  In Kaminka, G. A., Fox, M., Bouquet, P., Hüllermeier, E., Dignum, V., Dignum, F., and van Harmelen, F. (Eds.), ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, Vol. 285 of Frontiers in Artificial Intelligence and Applications, pp. 1692–1693. IOS Press.
  * Teppan et al. Teppan, E. C., Friedrich, G., and Falkner, A. A. (2012).  Quickpup: A heuristic backtracking algorithm for the partner units configuration problem.  In Fromherz, M. P. J., and Muñoz-Avila, H. (Eds.), Proceedings of the Twenty-Fourth Conference on Innovative Applications of Artificial Intelligence, July 22-26, 2012, Toronto, Canada. AAAI.
  * Teppan et al. Teppan, E. C., Friedrich, G., and Gottlob, G. (2016).  Tractability frontiers of the partner units configuration problem.  J. Comput. Syst. Sci., 82(5), 739–755.
  * Weinzierl Weinzierl, A. (2017).  Blending lazy-grounding and CDNL search for answer-set solving.  In Balduccini, M., and Janhunen, T. (Eds.), Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR 2017, Espoo, Finland, July 3-6, 2017, Proceedings, Vol. 10377 of Lecture Notes in Computer Science, pp. 191–204. Springer.