## Overview

`hclasp` provides a general declarative framework to incorporate domain-specific heuristics into ASP solving.
It extends `clasp` allowing to program the heuristic of the solver directly from the ASP code.

For a formal description of `hclasp`, please read our paper.

For a detailed description of `hclasp` implementation,
please read the system README.

Here we explain how to install the system, we give a short tutorial on how does hclasp work, followed by an example on the Blocks World, and we describe some of our experiments.

### Contents

## Installation

`hclasp` source code and precompiled linux binaries are available here.

To compile the system, please run the configure file and follow the instructions that will appear in the screen.

`hclasp` can be run with grounders Gringo or
lparse as front-ends.

## Tutorial

`hclasp` defines a new heuristic, named `domain`,
that modifies `vsids` heuristics of `clasp` allowing to program it from the ASP code.

To switch to `clasp` normal behavior, simply select another heuristic from command line,
for example, with `--heu=vsids` or `--heu=berkmin`.

Next we present some examples to explain how does `hclasp` work.

#### Positive sign

In `hclasp` the heuristic information is represented by the predicate `_heuristic`.
For example, the atom `_heuristic(a,sign,1)` tells `hclasp` that
when deciding on atom `a` it should be given a positive sign,
ie. it should be set to true.
We start with the following logic program `example1` and the `gringo` + `hclasp` execution:

When searching for an answer set, `hclasp` first propagates the heuristic atom
and next updates its heuristic knowledge about atom `a`.
Then it has to decide on `a` making it either true or false.
Following the current heuristic knowledge,
`hclasp` makes `a` true and finally returns the answer set `{_heuristic(a,sign,1),a}`.

#### Negative sign

In the next program `example2` the `heuristic` fact
asserts that when deciding on atom `a`
it should be given a negative sign, ie. it should be set to false:

`hclasp` propagates the heuristic fact and updates its heuristic knowledge,
decides on atom `a` making it false
and finally returns the answer set { `_heuristic(a,sign,-1)`}.

These two examples illustrate that the heuristic atoms modify `hclasp` decisions,
leading the solver to find first either the answer set with `a` (in `example1`)
or the answer set without it (in `example2`).
However, as long as heuristic atoms appear only in the head of the rules,
the answer sets of the program remain the same (modulo heuristic atoms).
For example, if we ask for all answer sets of `example1`
we get one without `a` and one with `a`,
and the same happens with `example2`:

#### Showing the heuristic information

For the heuristic atoms to take effect, they and their contained atoms must be
made visible to `hclasp`.
For example, if we add to `example2` the lines:

then `hclasp` knows nothing about the heuristic atom, and operates as `clasp` would do normally
with `vsids` heuristic.
The same would happen if instead we added:

because `hclasp` would know nothing about the atom `a` contained inside the heuristic atom.

#### Level

`hclasp` assigns to each atom a level,
and it decides on atoms of the highest possible level.
The default value for each atom is `0`,
and both positive and negative integers are valid.
Let's see the program `example3`, where level `10` is assigned to atom `a`:

`hclasp` propagates the heuristic facts, and given that the level of `a`
becomes greater than the level of `b`,
`hclasp` decides on it (with positive sign) and finally `b` is propagated to false.
If, for example, we added the fact `_heuristic(b,level,20)`,
the answer set would contain `b` instead of `a`.
This would also be the case if we used `_heuristic(a,level,-10)`
instead of `_heuristic(a,level,10)`.

#### Dynamic heuristic atoms

Heuristic atoms can be used as any other atoms of the logic program,
and they only affect the heuristic of the solver when they are true.
Let's see `example4`, where the heuristic atoms for `c` depend on `b`:

In this case first `hclasp` proceeds as in `example3`.
Then after propagating that b is false,
the heuristic fact `_heuristic(c,sign,-1)` is propagated,
so when deciding on `c`, it is assigned to false.
If we extended the program adding the fact `_heuristic(b,level,20)`, the answer set
would contain `b` and `c` instead of `a`.

#### True and false

The modifiers `true` and `false`
allow to refer at the same time to the level and the sign of an atom.
Internally,
for the `true` and `false` heuristic atoms,
`hclasp` defines new `level` and `sign` heuristic atoms
following these rules:

For instance, `example4` can be rewritten as:

In this case the fact `_heuristic(a,true,10)` stands for the previous facts
`_heuristic(a,level,10)` and `heuristic(a,sign,1)`.

#### Priorities between heuristic atoms

`hclasp` allows to represent priorities between different heuristic atoms
that refer to the same atom.
The priority is represented by a positive integer as a fourth term.
The higher the integer, the higher the priority of the heuristic atom.
For example, `_heuristic(c,sign,1,10)` and `_heuristic(c,sign,-1,20)` are valid heuristic atoms.
If both are true, then the sign assigned to `c` is `-1` (because `20>10`).
Let's see `example5`:

First `hclasp` proceeds as in `example3`.
Then after propagating that b is false,
the heuristic atom `_heuristic(c,sign,-1,20)` is propagated,
and given that `20>10` the sign for atom `c` is `-1`,
so when deciding on `c`, it is assigned to false.
If, for example, we added the fact `_heuristic(c,sign,1,30)` to the program, the answer set would contain atom `c`.

Whenever we use only three terms for a heuristic atom, the priority assigned
to it is the absolute value of the modifiers value.
For example, if `_heuristic(c,level,-10)` and `_heuristic(c,level,5)` were true,
then as `abs(-10)>abs(5)`
the level of `c` would be `-10`.

#### Init and factor

The modifiers `init` and `factor`
allow to modify the score that clasp heuristic assigns to each atom.
Compared to the `level` modifier, `init` and `factor` allow
to bias the search without stablishing a strict ranking among the atoms.

With `init` we can add a value to the initial heuristic score of an atom.
For example, if `_heuristic(a,init,2)` is true, then a value of `2` is added to
the initial score that the heuristic assigns to atom `a`.
Note that as the search proceeds, the initial score of an atom decays,
so `init` only affects the beginning of the search.

To bias the whole search we can use the `factor` modifier,
that multiplies for a value the heuristic score of an atom.
For example, if `_heuristic(a,factor,2)` is true, then the heuristic score for atom `a`
is multiplied by `2`.

#### Domain choices

With command line option `--stats` we can see some statistics of `hclasp` search.
The statistics are the same as those generated by `clasp`, but with one addition:
after the word `Domain` we can see how many decisions where made on atoms that appear
inside an heuristic atom.
This information may give us some insight about the performed search.
For instance, this is part of the output of `example5` with option `--stats`:

The line about `Choices` tells us that
two decisions were made, and that both where made on atoms contained in heuristic atoms.

## Example: The Blocks World

We apply `hclasp` to answer set planning in the Blocks World.
We begin with a basic encoding `bw.lp` of the problem:

and one instance `ins` (the Sussman anomaly):

If we execute:

`hclasp` will run as `clasp` with `vsids` heuristic.
Now can try to improve the performance of the system programming the heuristic.

In `bw.lp` once all the values for predicate `move` are given,
the values of `on` and `non` are determined and may be propagated by `hclasp`.
This suggests that deciding only on `move` may be a good strategy.
We can do that with `hclasp` adding the following simple heuristic rule to a file `heur.lp`:

and executing:

Given that the level of `move` is higher,
`hclasp` will decide first on atoms of that predicate,
and the values of the other predicates will be propagated.

We may prefer to soften the heuristic modification to simply bias the search
towards `move` predicate, without stablishing a strict preference towards it.
For that we can use, for example, the rule:

or the combination of both.
The first rule adds `2` to the initial score of `move` atoms,
while the second multiplies the heuristic score of `move` by `2`.

Whenever we decide on a true `move` atom,
the other `move` atoms for the same `time` are determined to be false,
and can be propagated by `hclasp`.
So deciding on true `move` atoms may be a good idea.
For that we can either use the `true` modifier to express a strict preference:

or just bias the search with `init` and `sign`:

or with `factor` and `sign`:

So far we have given the same heuristic values to all `move` atoms,
but other options may be interesting.
For example, we may prefer to decide first on earlier `move` atoms,
so that `hclasp` performs a forward search.
This can be represented with the following rule:

For `lasttime=3` the rule gives level `3` to `move` atoms of time `1`,
level `2` to those of time `2` and level `1` to those of time `3`,
assigning always a positive sign.
In this manner, `hclasp` will decide first on a true `move` atom of time `1`, then on one of time `2`,
and so on.

Another strategy is to perform a backwards search on `move` from the last to the first time instant directed by the goals.
We can use the next dynamic heuristic rule:

As before, the rule can be softened using `sign` with `init` or `factor`.
At the start of the search the goal `on` atoms will be true in the last time instant,
and with this rule `hclasp` will decide on a true `move` atom that will make one of them true.
Then some `on` atoms will be propagated to the previous time instant,
and the process is repeated until reaching the first time instant.

We can also choose to promote the `on` predicate.
For example, with any of these rules or with a combination of them:

Another interesting alternative is the following heuristic rule, that proved to be very good in our experiments (more on this below):

The idea is to make the goal `on` atoms persist backwards, one by one, from the last time instant to the first.
Note that a higher level is given to atoms at earlier time instants.
First `hclasp` will decide on one goal `on` atom of the last but one instant,
then it will decide to make it persist in the previous situation, and so on.
Later, it will make persist backwards another goal `on` atom.
With this heuristic the idea is not to decide on atoms that lead to many propagations (as with `move` atoms)
but rather to make correct decisions (given that most of the times the value of `on` will persist by inertia).

## Experiments

We have performed an empirical evaluation of `hclasp` in three different settings.
In the first, we studied single static heuristic modifications for ASP planning problems.
In the second, we solved abductive problems with optimization statements,
and in the third we solved PDDL planning problems translated to ASP.

### Experiments with static heuristic modifications

In this setting we focus on well-known ASP planning benchmarks in order to contrast heuristic modifications on comparable problems.
The benchmarks are Labyrinth, Sokoban, and Hanoi Tower, each comprising 32 instances from the third ASP competition.
We experiment with 38 heuristic modifications,
promoting the choice of actions and fluents via the heuristic modifiers
`factor` (1,2,4,8,16),
`init` (2,4,8,16),
`level` (1,-1),
`sign` (1,-1),
as well as attributing values to `factor`, `init`, and `level`
by ascending and descending time points.

No single heuristic modification improved over `vsids` heuristic in all benchmarks,
but for all benchmarks there were some heuristic modifications that clearly improved `vsids` performance.

The encodings and the instances can be found here, and the results here.

### Experiments on abductive problems with optimization

We performed experiments on three different problems using abduction in combination with a minimize statement to minimize the number of abducibles.
We considered benchmarks of Circuit Diagnosis, Metabolic Network Expansion and Transcriptional Network Repair.
To supporting minimization,
we assign false to the abducibles (`sign=-1`)
and gradually increase the bias of their choice by imposing `factor` 2, 4, 8 or 16,
or we enforce it via a level modifier (`level=1`).

In this setting the performance of `hclasp` clearly improved over `vsids` heuristic.
For example, using `sign=-1` and `level=1` the timeouts where reduced from 115 to 83 in Circuit Diagnosis, from 100 to 0 in Metabolic Network Expansion, and from 140 to 1 in Transcriptional Network Repair problems.

For Circuit Diagnosis the encodings and the instances can be found here, and the results here.

For Metabolic Network Expansion the encodings and the instances can be found here, and the results here.

For Transcriptional Network Repair the encodings and the instances can be found here, and the results here.

### Experiments on PDDL planning

For PDDL planning we selected 20 instances from the STRIPS domains of the 2000 and 2002 planning competitions. We translated these PDDL instances into ASP facts via plasp and used a simple planning encoding with 15 different plan lengths (5, 10, ..., 75). We applied the heuristic rule that makes the fluents persist backwards in time, in this case refering to both positive and negative truth values:

_heuristic(holds(F,T-1),true, lasttime-T+1) :- holds(F,T). _heuristic(holds(F,T-1),false,lasttime-T+1) :- not holds(F,T), fluent(F), time(T).

The performance of `hclasp` for this setting was excellent,
finding 427 more plans than `vsids` and doing 347 less timeouts (out of 3000 instances).

The encodings and the instances can be found here, and the results here.

## Help

`hclasp` is part of Potassco, the Potsdam
Answer Set Solving Collection, hosted at Sourceforge.

For any comments, just drop us a message!