hclasp
declarative programming of clasp heuristics

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:

_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}.

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:

_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

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:

#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.

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:

_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).

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:

_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.

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:

_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).

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:

_heuristic(b,sign,1).
_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 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:

$ 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.


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:

time(1..lasttime).                                                                                                                                                                                         
location(B) :- block(B).                                                                                            
location(table).                                                                                                    
                                                                                                                    
1 { move(B,L,T) : block(B) : location(L) } 1 :- time(T).                                           
                                                                                                                    
on(B,L,T)   :- move(B,L,T).                                                                             
non(B,L1,T) :- on(B,L,T), L!=L1, location(L1). 
on(B,L,T+1) :- on(B,L,T), not non(B,L,T+1), T < lasttime.                                                                                                                                                                             

:- move(B1,B2,T), on(B3,B2,T-1), block(B2).                                                                 
:- move(B1, L,T), on(B2,B1,T-1).                                                                             

and one instance ins (the Sussman anomaly):

#const lasttime=3.
block(a). block(b). block(c).
on(b,table,0). 
on(c,a,0).
on(a,table,0).

:- not on(a,b,lasttime).
:- not on(b,c,lasttime).
:- not on(c,table,lasttime).

If we execute:

$ gringo bw.lp ins | hclasp

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:

_heuristic(move(B,L,T),level,1)  :- block(B), location(L), time(T).

and executing:

$ gringo bw.lp ins heur.lp | hclasp

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:

_heuristic(move(B,L,T),init,2) :- block(B), location(L), time(T).
or:
_heuristic(move(B,L,T),factor,2) :- block(B), location(L), time(T).

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:

_heuristic(move(B,L,T),true,1) :- block(B), location(L), time(T).

or just bias the search with init and sign:

_heuristic(move(B,L,T),init,2) :- block(B), location(L), time(T).
_heuristic(move(B,L,T),sign,1) :- block(B), location(L), time(T).

or with factor and sign:

_heuristic(move(B,L,T),factor,2) :- block(B), location(L), time(T).
_heuristic(move(B,L,T),sign,1)   :- block(B), location(L), time(T).


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:

_heuristic(move(B,L,T),true,lasttime-T+1) :- block(B), location(L), time(T).

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:

_heuristic(move(B,L,T),true,T) :- on(B,L,T).

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:

_heuristic(on(B,L,T),level,1)  :- block(B), location(L), time(T).
_heuristic(on(B,L,T),init,2)   :- block(B), location(L), time(T).
_heuristic(on(B,L,T),factor,3) :- block(B), location(L), time(T).

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

_heuristic(on(B,L,T-1),true, lasttime-T+1) :- on(B,L,T).

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.

For a more detailed description of the experiments and the results, please read the Experiments section of our paper.


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!


SourceForge.net Logo Valid XHTML 1.0 Strict Valid CSS!