How to Use ACLP

Problem Representation

Within ACLP, problems can be represented directly from their declarative specification with the ability to accommodate in the representation natural structures or special features of the specific application, which can often lead to better solutions. A problem in ACLP is represented by an abductive theory consisting of a triple < P, A, IC > where:
  • P is a constraint logic program (a finite set of ECLiPSe clauses). It contains the general theory together with any specific axioms of the particular domain of our application. Due to the fact that the ACLP system has been implemented on top of the ECLiPSe language as a meta-interpreter, every predicate used in P has to be declared first as dynamic using the statement:
    :- dynamic pred_1/arity_1,...,pred_n/arity_n .
  • A is a set of abducible predicates different from the constraint predicates. The declarations of abducibles predicates have the form of ECLiPSe facts as
    abducible_predicate(predicate_name/arity).
    Currently, the system requires that abducible predicates do not contain any definition in the program P of the abductive theory representing the problem. If such partial information is available it is therefore necessary to rename the predicate into two predicates only one of which is an abducible with no definition in P. An important case where information on the abducible predicates is available is the case of re-computing a solution to a previously solved goal under new requirements. The current old solution to this goal is partial information on the abducible predicates. An example of this is the problem of rescheduling.
  • IC is a set of formulae (Integrity Constraints) over the combined language of CLP(R) and P. These integrity constraints encode the precondition requirements that must hold for each possible abducible. This set is written as ECLiPSe rules of the form
    ic :- B1,...,Bn. n >= 1.
    where:
  • at least one of the conditions B1,...,Bn has an abducible predicate,
  • the rest of the conditions can be either positive or negative literals on user-defined predicates or constraint predicates of ECLiPSe,
  • in the current implementation it is necessary that each non-abducible positive condition Bj does not depend (through P) on abducible predicates. If this is so it is then necessary to first unforld Bj in the integrity constraint until its dependence on the abducibles is made explicit in the constraint, and
  • a negative condition Bj can take the form not Aj or nott Aj (where Aj is a positive atom on a user-defined predicate). Their difference lies in the fact that the second form (nott Aj) does not actively use abduction when examining the solvability of the positive atom Aj. It uses only abducibles assumptions that have been generated from other parts of the computation.

    • The constraint predicates that can be used in the body of a program rule or an integrity constraint can be (i) arithmetic constraint predicates or (ii) logical contraint predicates . The arithmetic constraint predicates that are supported by the current ACLP implementation are:

  • T1##T2: the value of the term T1 is not equal to the value of the term T2.
  • T1#=T2: the value of the term T1 is equal to the value of the term T2.
  • T1 #< T2: the value of the term T1 is less than the value of the term T2.
  • T1#<=T2: the value of the term T1 is less than or equal to the value of the term T2.
  • T1#>T2 : the value of the term T1 is greater than the value of the term T2.
  • T1#>=T2: the value of the term T1 is greater than or equal to the value of the term T2.
    • The system also supports logical constraints such as conjunction, #/\ , and disjunction, #\/ . These simple constraints can be combined to build complex logical constraint expressions.

    Handling of the ICs by the System

    During a consistency phase for the consistent addition of a new abducible assumption, a(X) where X is now a "marked" ECLiPSe domain variable, constraints are automatically negated and set in the current constraint store. This negation of the constraints is the usual mathematical negation, e.g. the negation of the aritmetic constraint T1\#< T2 is T1\#>=T2. The negation of the logical constraint #/\ is #\/. For example, the negation of the logical constraint T1##5 #/\ T2#>2 is T1#=5 #\/ T2#<=2 .

    Negation as Failure

    Negation as failure is handled through abduction. The semantics of NAF is that of partial stable models. Effectively, all occurences of not(p) in the theory are replaced by not_p which is treated as an abducible with the canonical integrity constraint ic :- not_p, p. In the current implementation it is necessary for the user to specify explicitly both the fact that not_p is abducible by adding a statement abducible_predicate(not_p/arity) in the program as well as adding the above canonical constraint in the program. (Note if the definition of the predicate p depends on abducibles then as mentioned above we need to unfold this in the integrity constraints for these abducibles to appear explicitly in the integrity constraint).

    ACLP System Predicates

    The system predicate test/1 can be used in program P to test the existence or not of an abducible in the set of the current abducibles found so far. Its syntax is test(Abducible) .

    One example taken from the job shop scheduling problem is the following:

    working(R,T1,T2):- test(start(J,R,T)), T #> T1, T #< T2.

    where the goal working(R,T1,T2) checks if there is any job started till that point of execution on resource R between the time points T1 and T2 . The start/3 is an abducible predicate and has been defined as such by the declaration: abducible_predicate(start/3) .

    Computational Features of ACLP

    As the computation of an ACLP goal evolves the system holds two inter-related sets of information (i) the domain constraints that have been set and (ii) the abducible hypothese that have been assumed, up to the current point on the computation.

    The first set is effectively managed by the underlying ECLiPSe system whereas the second is managed explicitely by the ACLP system. Every time a new domain constraint is set the system tests using the ECLiPSe constraint handler if the new set of domain constraints is satisfiable. When a new abducible hypothesis is made the ACLP system checks the satisfaction of the integrity constraints in the user-defined abductive theory of the problem at hand. This may require new domain constraints or abductive hypothesis to be made.

    The ACLP system adopts the following search quidelines to build its solution.

  • Reuse of existing hypotheses and delay of generation of new hypotheses.
  • Least commitement on abductive hypotheses by not grounding these.
  • Depending on an evaluation of a domain constraint of how significant it is in the satisfaction of an integrity constraint, the system will or will not prohibit the possibility of generation of new abductive hypotheses to satisfy this integrity constraint.

    • In addition, in version 1 of the system whenever it is possible to use an existing abductive hypothesis to satisfy a constraint then this can prohibit the use of other ways (e.g. setting a domain constraint or generating a new abductive hypothesis) to satisfy this integrity constraint. As in CLP with ECLiPSe the order in which the integrity constraints are checked as well as the order of the conditions of an integrity constraint can sometimes affect significantly the computation of ACLP.

    Back to ACLP home page