hclasp: Declarative Programming of clasp Heuristics

**Warning: this project is no longer maintained. hclasp functionality became
part of clasp**

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 Gebser, M., Kaufmann, B., Romero, J., Otero, R., Schaub, T., & Wanko, P. (2013). Domain-Specific Heuristics in Answer Set Programming. In *AAAI*. AAAI Press.

The source code and precompiled linux binaries are available at sourceforge.

hclasp can be run with grounders gringo or lparse.

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’s normal behavior, simply select another heuristic from the
command line, for example, with `--heu=vsids`

or `--heu=berkmin`

.

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

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:

```
$ cat example1
_heuristic(a,sign,1).
{a}.
$ gringo example1 | hclasp
...
Answer: 1
_heuristic(a,sign,1) a
```

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 }`

.

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:

```
$ cat example2
_heuristic(a,sign,-1).
{a}.
$ gringo example2 | hclasp
...
Answer: 1
_heuristic(a,sign,-1)
```

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`

:

```
$ gringo example2 | hclasp 0
...
Answer: 1
_heuristic(a,sign,-1)
Answer: 2
_heuristic(a,sign,-1) a
```

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

```
#hide.
#show a.
```

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

```
#hide.
#show _heuristic.
```

because hclasp would know nothing about the atom `a`

contained inside the
heuristic atom.

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`

:

```
$ cat example3
_heuristic(a,sign,1).
_heuristic(b,sign,1).
_heuristic(a,level,10).
{a,b}.
:- a, b.
$ gringo example3 | hclasp
...
_heuristic(a,sign,1) _heuristic(b,sign,1)
_heuristic(a,level,10) 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)`

.

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`

:

```
$ cat example4
_heuristic(a,sign,1).
_heuristic(b,sign,1).
_heuristic(a,level,10).
{a,b}.
:- a, b.
{c}.
_heuristic(c,sign,1) :- b.
_heuristic(c,sign,-1) :- not b.
$ gringo example4 | hclasp
...
_heuristic(a,sign,1) _heuristic(b,sign,1)
_heuristic(a,level,10) a
_heuristic(c,sign,-1)
```

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`

.

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:

```
_heuristic(X,level,Y) :- _heuristic(X,true,Y).
_heuristic(X,sign,1) :- _heuristic(X,true,Y).
_heuristic(X,level,Y) :- _heuristic(X,false,Y).
_heuristic(X,sign,-1) :- _heuristic(X,false,Y).
```

For instance, `example4`

can be rewritten as

```
_heuristic(b,sign,1).
_heuristic(a,true,10).
{a,b}.
:- a, b.
{c}.
_heuristic(c,sign,1) :- b.
_heuristic(c,sign,-1) :- not b.
```

In this case the fact `_heuristic(a,true,10)`

stands for the previous facts
`_heuristic(a,level,10)`

and `heuristic(a,sign,1)`

.
</p>

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`

:

```
$ cat example5
_heuristic(a,true,10).
{a,b}.
:- a, b.
{c}.
_heuristic(c,sign,1,10 ).
_heuristic(c,sign,-1,20) :- not b.
$ gringo example5 | hclasp
...
_heuristic(b,sign,1) _heuristic(a,true,10)
_heuristic(c,sign,1,10) a
_heuristic(c,sign,-1,20)
```

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
|-10|>5 the level of `c`

would be -10.

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.

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`

:

```
$ gringo example5 | hclasp --stats
...
Models : 1+
Time : 0.000s (Solving: 0.00s ...)
CPU Time : 0.000s
Choices : 2 (Domain: 2)
Conflicts : 0
Restarts : 0
...
```

The line about `Choices`

tells us that two decisions were made, and that both
where made on atoms contained in heuristic atoms.

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.

For a more detailed description of the experiments and the results, please read
the Experiments section of Gebser, M., Kaufmann, B., Romero, J., Otero, R., Schaub, T., & Wanko, P. (2013). Domain-Specific Heuristics in Answer Set Programming. In *AAAI*. AAAI Press..

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, instances and results can be found here

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.

The encodings, instances and results can be found here.

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, instances and results can be found here.