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.