heuristic.tex

\section{Heuristic-driven Solving}
\label{sec:heuristic}
\clasp\ and \clingo\ provide means for incorporating domain-specific heuristics into ASP solving.
This allows for modifying the heuristic of the solver from within a logic program or from the command line.
A formal description can be found in \cite{gekaotroscwa13a}.

The framework is implemented as a new heuristic, named \code{Domain},
that extends the \code{Vsids} heuristics of \clasp\ 
and can be activated using option \code{--heuristic=Domain}
(cf.\ Section~\ref{subsec:clasp:tune}).
In what follows,
we first describe how to modify the solver's heuristic from within a logic program, 
then we explain how to apply modifications from the command line, 
and finally we show how to compute subset minimal answer sets with heuristics.

The following description conforms with \clingo~5.%1.1.

\subsection{Heuristic Programming}
\index{heuristic predicate}
Heuristic information is represented within a logic program my means of heuristic directives of the form
\[\code{\#heuristic }A\code{ : }B\code{. [}w\code{@}p\code{,}m\code{]}\]
where $A$ is an atom, $B$ a rule body, and $w$, $p$ and $m$ are terms.
%
The priority `\code{@$p$}' is optional.
%
Different types of heuristic information can be controlled using the modifiers 
\code{sign}, \code{level}, \code{true}, \code{false}, \code{init} and \code{factor} for $m$.
We introduce them below step by step.

\subsubsection{Heuristic modifier \code{sign}}
\index{heuristic predicate!\code{sign}}
The modifier \code{sign} allows for controlling the truth value assigned to variables subject to a choice within the solver.

The \code{Domain} heuristic associates with each atom an integer \code{sign} value, which by default is $0$.
When deciding which truth value to assign to an atom during a choice, the atom is assigned to true, if its \code{sign} value is greater than $0$. 
If the \code{sign} value is less than 0, it is assigned to false.
And if it is $0$, the sign is determined by the default sign heuristic.

In order to associate a positive sign with atom \code{a}, 
we can use the following heuristic directive:
\begin{lstlisting}[numbers=none]
#heuristic a. [1,sign] 
\end{lstlisting}
This associates a positive \code{sign} with \code{a} and 
tells the solver that upon deciding the atom \code{a}, it should be set to true.
\begin{example}
\label{example:psign}
Consider the following program:
\lstinputlisting[numbers=none]{examples/psign.lp}
\marginlabel{%
  To inspect the output, invoke:\\
  \code{\mbox{~}clingo \attach{examples/psign.lp}{psign.lp} \textbackslash\\\mbox{~}--heuristic=Domain}\\
  or alternatively:\\
  \code{\mbox{~}gringo \attach{examples/psign.lp}{psign.lp} \textbackslash\\\mbox{~}| clasp\mbox{~~~~~~~~~}\textbackslash\\\mbox{~}--heuristic=Domain}\\
}
At the start of the search, 
the solver %propagates the heuristic atom 
updates its heuristic knowledge about atom \code{a} assigning to it 
the \code{sign} value \code{1}.
Then, it has to decide on \code{a}, making it either true or false.
Following the current heuristic knowledge, 
the solver makes \code{a} true and returns the answer set 
\mbox{\{\code{a}\}}.
\end{example}

\begin{note}
The result would be the same if in the heuristic directive we used any positive integer instead of \code{1}.
\end{note}

\begin{example}
\label{example:nsign}
In the next program,
the \code{\#heuristic} directive gives \code{a} a negative sign 
and thus asserts that when deciding upon \code{a} it should be set to false:
\lstinputlisting[numbers=none]{examples/nsign.lp}
\marginlabel{%
  To inspect the output, invoke:\\
  \code{\mbox{~}clingo \attach{examples/nsign.lp}{nsign.lp} \textbackslash\\\mbox{~}--heuristic=Domain}\\
  or alternatively:\\
  \code{\mbox{~}gringo \attach{examples/nsign.lp}{nsign.lp} \textbackslash\\\mbox{~}| clasp\mbox{~~~~~~~~} \textbackslash\\\mbox{~}--heuristic=Domain}\\
}
As above,
the solver starts %with propagating the heuristic fact,
%then
updating its heuristic knowledge,
then decides on atom \code{a} making it false, and 
finally 
returns the empty answer set.% \mbox{\{ \code{\_heuristic(a,sign,-1)}\}}.
\end{example}

These two examples illustrate how the heuristic directives allow for modifying the decisions of the solver,
leading to either finding first the answer set with \code{a} or the one without it.
However, %as long as heuristic atoms appear only in the head of rules,
the program's overall answer sets remain the same. % (modulo heuristic atoms).
For example, if we ask for all answer sets in Example \ref{example:psign},
we obtain one without \code{a} and one with \code{a},
and the same happens with Example \ref{example:nsign}, 
although in this case the answer sets are computed in opposite order.

\subsubsection{Heuristic modifier \code{level}}
\index{heuristic predicate!\code{level}}

The \code{Domain} heuristic assigns to each atom a \code{level}, and it decides first upon atoms of the highest level.
The default value for each atom is \code{0},  and both positive and negative integers are valid.
\begin{example} 
\label{example:level}
In this example,  
level \code{10} is assigned to atom \code{a}:
\lstinputlisting[numbers=none]{examples/level.lp}
\marginlabel{%
  To inspect the output, invoke:\\
  \code{\mbox{~}clingo \attach{examples/level.lp}{level.lp} \textbackslash \\\mbox{~}--heuristic=Domain} \\
  or alternatively:\\
  \code{\mbox{~}gringo \attach{examples/level.lp}{level.lp} \textbackslash \\\mbox{~}| clasp\mbox{~~~~~~~~} \textbackslash\\\mbox{~}--heuristic=Domain}\\
}
The first obtained answer set is \mbox{\{\code{a}\}}.
The solver starts updating its heuristic knowledge, 
and given that the level of \code{a} is greater than that of \code{b},
it decides first on \code{a} (with positive sign) and then \code{b} is propagated to false.
If we added the directive
\begin{lstlisting}[numbers=none]
#heuristic b. [20,level] 
\end{lstlisting}
we would first obtain the answer set containing \code{b} instead of \code{a}.
This would also be the case if we replaced \code{10} by \code{-10} in the third heuristic directive.
\end{example}

\begin{note}
The \code{Domain} heuristic is an extension of the \code{Vsids} heuristic, 
so when there are many unassigned atoms with the highest level,
the heuristic decides, among them, on the one with the highest \code{Vsids} score.
\end{note}

\subsubsection{Dynamic heuristic modifications}

Heuristic directives only affect the solver when their bodies are true.
%
This allows representing dynamic heuristic modifications.
%
\begin{example}
\label{example:dynamic}
In the next program, the heuristic directive for \code{c} depends on \code{b}:
\lstinputlisting[numbers=none]{examples/dynamic.lp}
\marginlabel{%
  To inspect the output, invoke:\\
  \code{\mbox{~}clingo \attach{examples/dynamic.lp}{dynamic.lp} \textbackslash\\ \mbox{~}--heuristic=Domain}\\
  or alternatively:\\
  \code{\mbox{~}gringo \attach{examples/dynamic.lp}{dynamic.lp} \textbackslash\\ \mbox{~}| clasp\mbox{~~~~~~~~~~} \textbackslash\\ \mbox{~}--heuristic=Domain}\\
}
The first obtained answer set is \mbox{\{\code{a}\}}.
At first, the solver proceeds as in Example \ref{example:level}.
Then, after propagating \code{b} to false,
the heuristic knowledge is updated assigning the \code{sign} value \code{-1} to \code{c}.
So, when deciding upon \code{c}, it gets assigned to false.
If we added the directive 
\begin{lstlisting}[numbers=none]
#heuristic b. [20,level]
\end{lstlisting}
the first answer set would contain \code{b} and \code{c} instead of \code{a}.
\end{example}

\subsubsection{Heuristic modifiers \code{true} and  \code{false}}
\index{heuristic predicate!\code{true}}
\index{heuristic predicate!\code{false}}

The modifiers \code{true} and \code{false} allow us 
to refer at the same time to the \code{level} and the \code{sign} of an atom.
Internally, a heuristic directive with the form 
\[\code{\#heuristic }A\code{ : }B\code{. [}w\code{@}p\code{,}\code{true]}\]
becomes
\begin{align*}
\code{\#heuristic }A\code{ : }B\code{. [}&w\code{@}p\code{,}\code{level]}\\
\code{\#heuristic }A\code{ : }B\code{. [}&\code{1}\code{@}p\code{,}\code{sign]}
\end{align*}
and 
\[\code{\#heuristic }A\code{ : }B\code{. [}w\code{@}p\code{,}\code{false]}\]
becomes
\begin{align*}
\code{\#heuristic }A\code{ : }B\code{. [}&w\code{@}p\code{,}\code{level]}\\
\code{\#heuristic }A\code{ : }B\code{. [}&\code{-1}\code{@}p\code{,}\code{sign]}
\end{align*}
%
For instance, the program of Example \ref{example:dynamic}
can be rewritten as:
\begin{lstlisting}[numbers=none]
#heuristic b. [ 1,sign]
#heuristic a. [10,true]
{a;b}.
:- a, b.
{c}.
#heuristic c :     b. [ 1,sign]
#heuristic c : not b. [-1,sign]
\end{lstlisting}
In this case, the directive 
\begin{lstlisting}[numbers=none]
#heuristic a. [10,true]
\end{lstlisting}
stands for the previous
\begin{lstlisting}[numbers=none]
#heuristic a. [ 1, sign]
#heuristic a. [10,level]
\end{lstlisting}

\subsubsection{Priorities among heuristic modifications}

The \code{Domain} heuristic allows for representing priorities
between different heuristic directives that refer to the same atom.
The priority is optionally represented by a positive integer $p$ in `\code{@$p$}'.
The higher the integer, the higher the priority of the heuristic atom.
For example, the following are valid heuristic directives:
\begin{lstlisting}[numbers=none]
#heuristic c. [ 1@10,sign]
#heuristic c. [-1@20,sign]
\end{lstlisting}
With both, the \code{sign} assigned to \code{c} is \code{-1} 
(because priority \code{20} overrules \code{10}).  

\begin{example}
\label{example:priority}
Consider the following program:
\lstinputlisting[numbers=none]{examples/priority.lp}
\marginlabel{%
  To inspect the output, invoke:\\
  \code{\mbox{~}clingo \attach{examples/priority.lp}{priority.lp} \textbackslash\\ \mbox{~}--heuristic=Domain}\\
  or alternatively:\\
  \code{\mbox{~}gringo \attach{examples/priority.lp}{priority.lp} \textbackslash\\ \mbox{~}| clasp\mbox{~~~~~~~~~~~} \textbackslash\\ \mbox{~}--heuristic=Domain}\\
}
The first obtained answer set is \mbox{\{\code{a}\}}.
First the solver proceeds as in Example \ref{example:level}. 
Then, after setting \code{b} to false by propagation, 
the heuristic knowledge about \code{c} is updated.
Given that priority \code{20} is greater than \code{10},
the \code{sign} value of atom \code{c} is \code{-1}.
So, when deciding upon \code{c}, it is assigned to false.
If we added the directive
\begin{lstlisting}[numbers=none]
#heuristic c. [1@30,sign]
\end{lstlisting}
the first answer set would also contain atom \code{c}.
\end{example}

\begin{note}
If the priority is omitted then it defaults to $0$,
as with the priorities of weak constraints
(Section~\ref{subsec:gringo:optimize}).
For example,
with these directives
\begin{lstlisting}[numbers=none]
#heuristic c. [ 10,level]
#heuristic c. [5@2,level]
\end{lstlisting}
the level of \code{c} is \code{5} because $\code{2}>\code{0}$.
\end{note}

\subsubsection{Heuristic modifiers \code{init} and \code{factor}}
\index{heuristic predicate!\code{init}}
\index{heuristic predicate!\code{factor}}

The modifiers \code{init} and \code{factor} allow for modifying the scores assigned to atoms by the underlying \code{Vsids} heuristic.
Unlike the \code{level} modifier, 
\code{init} and \code{factor} allow us to bias the search without establishing a strict ranking among the atoms.

With \code{init}, we can add a value to the initial heuristic score of an atom.
For example, with
\begin{lstlisting}[numbers=none]
#heuristic a. [2,init]
\end{lstlisting}
a value of \code{2} is added to
the initial score that the heuristic assigns to atom \code{a}.
Note that as the search proceeds, the initial score of an atom decays, 
so \code{init} only affects the beginning of the search.

To bias the whole search, we can use the \code{factor} modifier
that multiplies the heuristic score of an atom by a given value.
For example, with 
\begin{lstlisting}[numbers=none]
#heuristic a. [2,factor]
\end{lstlisting}
the heuristic score for atom \code{a} is multiplied by \code{2}.

\subsubsection{Monitoring \code{domain} choices}

The \code{Domain} heuristic extends \clasp\ and \clingo's search statistics produced with command line option \code{--stats}.
After `\code{Domain:}', it prints how many decisions where made on atoms appearing inside \code{\#heuristic} directives.
%
For instance, the statistics obtained in Example \ref{example:dynamic} read as follows:
\begin{lstlisting}[numbers=none]
...
Models       : 1+
Calls        : 1
Time         : 0.003s (Solving: 0.00s ...)
CPU Time     : 0.000s

Choices      : 2        (Domain: 2)
Conflicts    : 0        
Restarts     : 0
...
\end{lstlisting}
The line about \code{Choices} tells us that two decisions were made 
and that both where made on atoms contained in \code{\#heuristic} directives.

%\begin{example}
\subsubsection{Heuristics for Blocks World Planning}
\label{example:blocks:world:heuristic}
We now apply the \code{Domain} heuristic to Blocks World Planning.  
For simplicity, we adapt the encoding of Section \ref{subsec:block:encoding} 
for one-shot solving\footnote{Heuristics may also be applied in the incremental setting of 
Section \ref{subsec:block:encoding}, but we introduce them this way for clarity.}: 
\lstinputlisting[numbers=none]{examples/blocks-heuristic.lp}
Constant \code{lasttime} bounds the plan length, and we assume it is provided by command line (for example, with option \code{-c lasttime=3}).
%fixes the maximum and one instance:
%\lstinputlisting[numbers=none]{examples/bw_ins.lp}
%
%If we execute:
%\begin{lstlisting}[numbers=none]
%$ gringo bw.lp ins | clasp \end{lstlisting}
%\clasp\ will run with \code{vsids} heuristic. Now we can try to improve the performance of the system programming the heuristic.
In this encoding, once all the values for predicate \code{move/3} are given,
the values of \code{moved/2} and \code{holds/2} are determined and may be propagated by the solver.
This suggests that deciding only on \code{move/3} may be a good strategy.
We can do that with the \code{Domain} heuristic 
adding the following heuristic directive:
%
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic move(B,L,T) : block(B),location(L),time(T). [1,level]
\end{lstlisting}
Given that the level of \code{move/3} is higher,  the solver 
decides first on atoms of that predicate,
and the values of the other predicates are propagated.

We may prefer to soften the heuristic modification to simply 
bias the search  towards the \code{move/3} predicate,
without establishing a strict preference towards it.  
For that, we can use, for example, the directive
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic move(B,L,T) : block(B),location(L),time(T). [2, init]
\end{lstlisting} 
or
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic move(B,L,T) : block(B),location(L),time(T). [2,factor]
\end{lstlisting}
or the combination of both.
The first directive adds \code{2} to the initial score of \code{move/3} atoms,
while the second multiplies the heuristic score of \code{move/3} by \code{2}.

Whenever we decide on making a \code{move/3} atom true,  
the other \code{move/3} atoms for the same \code{time/1} are determined to be false,
and can be propagated by the solver. 
So, deciding on true \code{move/3} atoms may be a good idea.
For that, we can either use the \code{true} modifier to express a strict preference
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic move(B,L,T) : block(B),location(L),time(T). [1,true]
\end{lstlisting}
or just bias the search with \code{init} and \code{sign}
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic move(B,L,T) : block(B),location(L),time(T). [2,init]
#heuristic move(B,L,T) : block(B),location(L),time(T). [1,sign]
\end{lstlisting}
or with \code{factor} and \code{sign}
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic move(B,L,T) : block(B),location(L),time(T). [2,factor]
#heuristic move(B,L,T) : block(B),location(L),time(T). [1,sign]
\end{lstlisting}

So far, we have given the same heuristic values to all \code{move/3} atoms,
but other options may be interesting. 
For example, we may prefer to decide first on earlier \code{move/3} atoms,
so that the solver performs a forward search. 
This can be represented with the following rule:
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic move(B,L,T) : block(B), location(L), time(T). 
                         [lasttime-T+1,true]
\end{lstlisting}
For \code{lasttime=3},
the rule ranks \code{move/3} atoms at time \code{1} at level \code{3},
those at time \code{2} at level \code{2}, and 
those at time \code{3} at level \code{1},
while always assigning a positive \code{sign}.
In this manner, 
the solver decides first on setting a \code{move/3} atom at time \code{1} to true, 
then one at time \code{2}, and so on.

Another strategy is to perform a backwards search on \code{move/3} from the last to the
first time instant, directed by the goals. 
For this purpose, we can use the following dynamic heuristic directive: 
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic move(B,L,T) : holds(on(B,L),T). [true,T]
\end{lstlisting}
As before, the directive can be softened using \code{sign} with \code{init} or \code{factor}.
At the start of the search, the goal's \code{holds/2} atoms are true at the last time step.
With this rule, the solver decides on a \code{move/3} atom that makes one of them true.
Then, some \code{holds/2} atoms are propagated to the previous time step,
and the process is repeated until reaching the first time instant.

We can also choose to promote atoms of the \code{holds/2} predicate.  
For example, this can be achieved with any of the following directives.
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic holds(on(B,L),T) : block(B),location(L),time(T).
                              [1,level]
#heuristic holds(on(B,L),T) : block(B),location(L),time(T).
                              [2,init]
#heuristic holds(on(B,L),T) : block(B),location(L),time(T).
                              [3,factor]
\end{lstlisting}

Another interesting alternative is the following heuristic directive,  
that proved to be very useful in practice (see \cite{gekaotroscwa13a}):
%\begin{lstlisting}[numbers=none]
\begin{lstlisting}[basicstyle=\small\ttfamily,numbers=none]
#heuristic holds(on(B,L),T-1) : holds(on(B,L),T). 
                                [lasttime-T+1,true] 
\end{lstlisting}
The idea is to make the goal's \code{holds/2} atoms persist backwards, 
one by one, from the last time step to the first one.
Note that a higher level is given to atoms at earlier time instants.
First, the solver decides on one of the goal's \code{holds/2} atoms at the last but one time step,
then it decides to make it persist to the previous situation, and so on.
Later, it makes persist backwards another \code{holds/2} atom from the goal.
With this heuristic,
the idea is not to decide on atoms that lead to much propagation (as with \code{move/3} atoms)
but rather to make correct decisions, 
given that usually the values of \code{holds/2} atoms persist by inertia.
%\end{example}


\subsection{Command Line Structure-oriented Heuristics}

The \code{Domain} heuristic also allows us to modify the heuristic of the solver from the command line.
For this, it is also activated with option \code{--heuristic=Domain}, 
but now the heuristic modifications are specified by option:
\begin{center}\lstinline{--dom-mod=<mod>[,<pick>]}\end{center}
where $\texttt{<mod>}$ ranges from \texttt{0} to \texttt{5} and specifies the modifier:
\begin{center}
\begin{tabular}{cl|cl}
\texttt{<mod>} & Modifier                    & \texttt{<mod>} & Modifier     \\
\hline
\texttt{0}     & None                        & \texttt{1}     & \texttt{level}\\
\texttt{2}     & \texttt{sign} (positive)    & \texttt{3}     & \texttt{true} \\
\texttt{4}     & \texttt{sign} (negative)    & \texttt{5}     & \texttt{false}
\end{tabular}
\end{center}
$\texttt{<pick>}$ specifies bit-wisely the atoms to which the modification is applied:
\begin{center}
\begin{tabular}{rcl}
\texttt{0}  & & Atoms only\\
\texttt{1}  & & Atoms that belong to strongly connected components \\
\texttt{2}  & & Atoms that belong to head cycle components \\ %~\cite{gekasc13a}\\
\texttt{4}  & & Atoms that appear in disjunctions\\
\texttt{8}  & & Atoms that appear in optimization statements\\
\texttt{16} & & Atoms that are shown
\end{tabular}
\end{center}
Whenever \texttt{<mod>} equals \texttt{1}, \texttt{3} or \texttt{5},
the level of the selected atoms depends on \texttt{<pick>}.
For example, with option \texttt{--dom-mod=2,8},
we apply a positive \texttt{sign} to atoms appearing in optimization statements,
and with option \texttt{--dom-mod=1,20},
we apply modifier \texttt{level} to both atoms appearing in disjunctions as well as shown atoms.
In this case, atoms satisfying both conditions
are assigned a higher level than those that are only shown,
and these get a higher level than those only appearing in optimization statements.

Compared to programmed heuristics,
the command line heuristics do not allow for applying modifiers \texttt{init} or \texttt{factor}
and cannot represent dynamic heuristics.
On the other hand, they allow us to directly refer to structural components of the program
and do not require any additional grounding.
%
When both methods are combined,
the atoms modified by the \texttt{\#heuristic} directive are not affected by the command line heuristics.

\subsection{Computing Subset Minimal Answer Sets with Heuristics}

Apart from boosting solver performance,
domain specific heuristics can also be used for computing subset minimal answer sets
(cf.\ \cite{cacacale96a,rogima10a}).
This can be achieved by assigning \texttt{false} with value \texttt{1} to the atoms to minimize. %shown atoms. % whenever they are subject to a choice in \clasp.
\begin{example}
Consider the following program:
\begin{lstlisting}[numbers=none]
1 {a(1..3)}.  a(2) :- a(3).  a(3) :- a(2).  {b(1)}.  
#show a/1.
\end{lstlisting}
Both the command line option `\texttt{--dom-mod=5,16}' as well as the addition of the heuristic directive
\begin{lstlisting}[numbers=none]
#heuristic a(1..3). [1,false]
\end{lstlisting}
guarantee that the first answer set produced is subset minimal with respect to the atoms of predicate \texttt{a/1}.
Moreover, both allow for enumerating all subset minimal solutions in conjunction with option \texttt{--enum-mod=domRec}.
In our example, we obtain the answer sets
\(
\{\texttt{a(1)}\}
\)
and
\(
\{\texttt{a(2)},\ \texttt{a(3)}\}
\).
Note that in this case solutions are projected on shown atoms.
\end{example}
It is worth mentioning that the enumeration mode \texttt{domRec} relies on solution recording and is thus prone to an exponential blow-up in space.
In practice, however, this often turns out to be superior to enumerating subset minimal model via disjunctive logic programs,
which is guaranteed to run in polynomial space.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "guide"
%%% End: