 |
 |
Constraint
Programming
within
CLIPS |
|
 |
|
Michel
Futtersack
|
|
Jean-Marc
Labat
|
CRIP5
Paris Descartes University
Paris FRANCE
|
|
LIP6
Pierre et Marie Curie University
Paris FRANCE
|
CCP is a generic knowledge base
which enables CLIPS to solve CSPs (Constraint Satisfaction Problems).
CCP is composed of three modules. The MAIN module contains the
top level loop including the I/O rules. The SEARCH module implements
a classical Chronological Backtrack algorithm. The PROPAGATION
module implements the Forward Checking algorithm.
CCP has been extensively tested with well known puzzles as N-queens,
graph colouring, crosswords, etc.
To implement any particular problem, the users only need to declare
each variable with its domain and they have to define specific
domain description and rules of propagation. So that all specific
knowledge is encapsulated in the PROPAGATION module.
CCP is a generic tool that can be embedded in a knowledge based
system like a work horse for local CSPs solving. CCP is compact,
since it contains only a dozen rules. Moreover, CCP can be seen
as a pedagogical tool illustrating many advanced features of CLIPS
(logical dependencies, forall, exists conditional elements, the
built function and a control strategy based on the focus stack)
1. Introduction
2. Basic Algorithms for Solving CSPs
2.1 Chronological Backtracking
2.2 Improving Backtracking with Heuristics and
with Forward Checking
2.3 Example : the 4-queens Problem
3. Presentation of CCP
3.1 the MAIN Module
3.2 the SEARCH Module
3.3 the PROPAG Module
4. Concluding
Remarks
5. References
CLIPS Sources
Appendix A Solving
5-queens with only one rule
Appendix B CCP's
Code
Appendix C Examples of Problems Solved by CCP
Download CCP's Code & Documentation
in RTF format
Download CCP's code and Documentation in Postscript format
An interesting discussion about CCP by Johan Lindberg
JESS Sources
CCP's Code
The Seat problem
| 1. Introduction |
 |
A wide variety of problems can
be described as Constraint Satisfaction Problems (CSPs) : time
table, cross-words, graph colouring, job shop scheduling, SAT
problems. Combinatorial optimization such as the assignment problem,
the Vehicle Routing Problem or the Knapsack Problem can be also
considered as CSP problems by transforming Max f(x) (respectively
Min) into f(x) > B (resp f(x) < B) where B is a given value,
high (resp low) enough to produce a good solution.
The CSP framework also offers a sound basis for representing and
solving decision problems without uncertainty [Schiex et al, 95].
All of these problems are at least NP-complete (see [Reeves, 93])
and huge instances require a large amount of computational resources.
This is the reason why all these problems are very important in
the field of Artificial Intelligence, with much research centered
on the discovery of new algorithms for CSPs .
But, the algorithms for solving CSPs are more often than not black
boxes. They do not enable you to solve problems needing Human
Computer Interaction. The most typical example is time-table for
schools. At least in France, there is no commercial software available
to satisfy teachers: in most cases, time tables are still hand-made.
It appears that, for some CSPs, it seems better to use knowledge
based systems.
The resolution of CSPs needs a mechanism of hypothesis generation
with backtracking when an impasse occurs (to be described later
in details). Our project stems from a knowledge base proposed
by [Laurière, 86] using an inference engine called SNARK
in which a function "REVENIR-SUR" directly implements
the backtrack mecanism. We do not have such a feature within CLIPS
(which is very costly since all the firings must be registered)
but we used instead the logical conditional element.
Of course, one can object that an inference engine using variables
realizes this mecanism before firing a rule. Such is the case
of the RETE algorithm [Forgy, 82] which implements the instantiation
of variables with backtrack when an impasse occurs. For example,
consider the well known puzzle in which there are five houses,
each of a different color, inhabited by men of different nationalities,
with different pets, drinks, and cigarettes. Given the initial
set of conditions, it must be determined which attributes are
assigned to each man. It can be solved with only one rule in which
each variable is represented by a conditional element (see the
Zebra knowledge base proposed within CLIPS 6.0). However, this
approach is very costly in terms of memory and solving N-queens
with twenty or more queens is impossible on a PC with 32 Mo using
the same way (see the rule in Appendix A) So, the aim of this
paper is to present the knowledge base we have designed using
CLIPS to go beyond this limit.
In the next section, we present the classical Chronological Backtrack
algorithm with a heuristic method to choose the next variable
to instantiate [Laurière, 78] and with Forward Checking
algorithm since [Haralick et al, 80] has proved that it is the
most efficient algorithm, at least for binary CSPs. Then, in Section
3, we present CCP (CCP stand for CLIPS Constraint Programming)
our generic knowledge base and the PROPAG module which is specific
to each problem. In Section 4, we conclude by introducing future
work using CCP.
2. Basic algorithms for solving
CSPs
| 2.1 Chronological
Backtracking |
|
The basic algorithm used tosolve
CSPs is called Chronological Backtracking (CB). CB is a constructive
algorithm [Minton et al, 92], since it builds up a solution variable
by variable. The iterative process is decomposed into two steps.
First CB chooses a variable (called the current-hypothesis) and
instantiates it to the first possible value from its domain. Then
CB checks the constraints whose all variables are instantiated.
If one constraint fails, the algorithm backtracks. The previous
instantiation of the current-hypothesis is undone and, if it is
possible, replaced with another value (backtrack on the value).
If all the values of the current-hypothesis have been tested,
the algorithm backtracks to the previous instantiated variable
(backtrack on the variable). If the set of possible values is
empty for this variable, the algorithm backtracks again until
an instantiated variable with a non empty set of possible values
is found. This process continues until all the variables have
been successfully instantiated, which means a solution has been
found, or until all possible combinations of instantiations have
been tried out without success.
| 2.2 Improving
backtracking with heuristics and with Forward Checking algorithm |
|
The drawbacks of the simple CB approach are obvious and well-known
and many improvements are possible. In our knowledge-based approach,
we have introduced two classical improvements. First, we use a
standard heuristic to choose the next variable to instantiate.
The heuristic consists to choose the variable with the smallest
remaining domain at each iteration of the algorithm. This is known
as "first fail principle". The second improvement adds
to the chronological backtrack a look-ahead scheme which attempts
to detect impasses as early as possible in the search. The aim
is to eliminate, in the domains of variables yet to be instantiated,
the values that are not consistent with the current instantiation.
This is called the propagation phase, since the new instantiation
gives new information on the current solution being constructed.
At least, three algorithms exist doing this kind of job: Forward
Checking, Partial Look-Ahead, Full Look-Ahead. We have retained
Forward Checking, known to be the best compromise between the
time spended on filtering the domains and the speed-up achieved
by avoiding useless instantiations. Forward checking filters the
domains of not instantiated variables which are directly linked
to the current-hypothesis by a constraint. Of course, when a backtrack
occurs, the inferences made during the propagation must be retracted.
| 2.3 Example:
4-queens problem. |
|
Consider the classical 4-queens problem which consists to set
4 queens on a 4x4 in such a way that no one queen can capture
another. It is obvious that you have to set only one queen per
row (and per column). So, it is possible defining the problem
as setting a queen on each row where the place is defined by the
number of the column.
We obtain the following formulation:
Four variables Q1, Q2, Q3, Q4 where the number indicates the number
of the row
The starting domain of each variable is D = {1, 2, 3, 4}
The constraints between Qi and Qj are [if v(Di) is the value of
the variable Di]:
i-j # v(Di) -v(Dj) (no two queens on the same positive diagonal)
i-j # v(Dj) -v(Di) (no two queens on the same negative diagonal)
v(Di) # v(Dj) (no two queens on the same column).
The search tree (see Figure 1) shows the process until the first
solution is found. At the beginning (state 0), the board is empty.
At state 1, Q1 is the first current-hypothesis with 1 as value.
The Forward-Checking algorithm eliminates for Q2, Q3, Q4 the marked
squares. At state 3, it is worth noticing two points: As there
is no choice for Q3, since its domain only contains one value,
Q3 is not marked as a hypothesis. After the propagation of Q3
value, the domain of Q4 becomes empty. This denotes an impasse
and the search algorithm backtracks to the current hypothesis
which is Q2. Since there exists another value for Q2, it is a
backtrack on the value. At state 5, there is another impasse.
But this time, there is no another value possible for Q2, so it
is a backtrack on the previous instantiated variable, Q1. And
so on, until the first solution is found. One can notice that
on the hypothesis made at the state 6, there is no more hypothesis
until the solution is found.
In this example, the number of generated states is only 8. A simple
enumerative algorithm would have generated 77 states and Chronological
Backtracking without Forward-Checking, 31 states. More generally,
the number of nodes is dramatically reduced using Chronological
Backtracking with the "first fail" heuristic and Forward
Checking.
In Figure 1, a cross indicates a value retracted by the Forward
Checking algorithm. A gray square indicates a value which has
previously produced an impasse. Note that in the state 4, Q4 is
instantiated but it could have been Q3. The agenda contains two
activations of the rule forced-instantiation (see Section 3.2)
one with Q3 and one with Q4. No strategy exists for deciding which
one must fire first, so CLIPS chooses.
3. Presentation of CCP
CCP is composed of three modules: the MAIN module, the SEARCH
module and the PROPAGATION module. We will see that the MAIN module
and the SEARCH module are completely independent of the particular
problem. So, we put them into CCP.clp, a file that the users should
not change. They should just load it before the file containing
the PROPAG module which contains templates, facts and rules specific
to the users problem.
| 3.1 The MAIN
module |
|
Three deftemplates are defined
into this module. The first one, called pb, describes the current
state of the problem and has three slots. The slot state describes
the state of the problem with the six following possible values
: start, in-progress, new-depth, choice-var, solved and blocked.
The slot level represents the number of recursive calls made by
the chronological backtrack during the search. At each new hypothesis,
a fact issued from pb template is duplicated with the slot level
incremented by one. This slot level allows us to backtrack on
the variable when it is necessary. The last slot is current-hypothesis
whose value is the variable chosen as an hypothesis at the current
level of the search.
The second template, called var, describes every variable of the
problem. The users must generate with this template all the variables
describing their problem. Since these facts are the only ones
which depend on the particular problem, we have decided that it
is better for the users to define their variables in the PROPAG
module, although the template is defined in the MAIN module. The
advantage we see is the users have nothing to introduce in the
MAIN module nor in the SEARCH module. The template contains four
slots which are name for the name of the variable, level for the
level in the stack (so, it has the same value that level in pb),
possible-values for the list of possible values remaining in the
domain at each level and value giving the value for an instantiated
variable. For example, you can see in Figure 2 the facts corresponding
to the templates pb and var at level 0 and 1 corresponding to
the state 0 and state 1 in Figure 1.
The third template solution is useful to count the number of solutions
and to register each solution into a mulislot var-val which is
a list containing each variable and its value (we tried initially
to construct a list of lists into the multislot var-val but it
does not seem possible with CLIPS).
The MAIN module contains five rules which are all independent
of the particular problem.
In the first rule, the users are asked if they want all the solutions
or if they prefer be asked after each found solution. We use the
build function to add the rule corresponding to the users choice.
Of course, using the build function is not necessary but it spares
one rule and it is a very simple but not trivial illustration
of the build function.
The second rule is a metarule which constructs the focus stack
when the problem is in progress. This value means that all the
propagations are made and that the problem is not solved, nor
blocked. So, it is necessary to make a new hypothesis. The rule
changes the value from in-progress to new-depth.
The third rule registers a new solution when it occurs.
Figure 1: The tree developped until the first solution is found
(using Chronological Backtracking with Forward-Checking)
The fourth rule stops the search
(no another solution or even no solution at all). This is the
case when the value of the slot state is blocked and the value
of the slot level is zero into the fact pb because no more backtrack
is possible (there is no another value in the domain of the first
variable chosen as current-hypothesis).
The final rule of this module prints the solution (default printing
method). If the users desire a customized printing we propose
them to define it in the PROPAG module.
|
(level-search 0)
- (pb (state start) (level 0) (current-hypothesis
no))
(var (name x4) (level 0) (possible-values 1 2 3 4) (value nil))
(var (name x3) (level 0) (possible-values 1 2 3 4) (value nil))
(var (name x2) (level 0) (possible-values 1 2 3 4) (value nil))
(var (name x1) (level 0) (possible-values 1 2 3 4) (value nil))
(level-search 1)
(pb (state in-progress) (level 1) (current-hypothesis x1))
(var (name x1) (level 1) (possible-values 2 3 4) (value 1))
(var (name x4) (level 1) (possible-values 2 3) (value nil))
(var (name x3) (level 1) (possible-values 2 4) (value nil))
(var (name x2) (level 1) (possible-values 3 4) (value nil))
|
Figure 2 : Facts corresponding
to the templates pb and var
| 3.2 The SEARCH
module |
|
This module contains only rules
but it imports templates defined in MAIN. These six rules implement
the Chronological Backtrack with the "first fail" heuristic.
When the slot state of the fact pb at the current level is new-depth,
a new hypothesis must be made.
The first rule creates a new level of search. This means two new
facts: if the current level is ?n, a new ordered fact (level-search
(+ ?n 1)) is asserted and a fact pb is duplicated with the value
(+ ?n 1) for the slot level and the value choice-var for the slot
state.
This value activates the rule named choice-var-val which chooses
as current-hypothesis the most constrained variable (i.e. one
among those whose domain is the most reduced) and chooses as value
the first available in the domain. We will improve this choice
in the future, mainly by interacting with the users who can indicate
a good choice, using human properties as experience, social knowledge
or physical perception. After the instantiation of the current-hypothesis,
the propagation of this new information must be made immediately.
So the rule ends by focusing on the PROPAG module, which will
be described after the SEARCH module.
The three following rules of the SEARCH module analyse the result
of the PROPAG module according to the number of values remaining
in the domain of not yet instantiated variables. If the domain
of a not yet instantiated variable contains only one element,
there is no choice and the rule named forced-instantiation fires.
Notice that a forced instantiation does not generate a new level
in the stack but it is necessary to return immediately to the
PROPAG module. Even this rule must not be fired twice before returning
into the PROPAG module, since it can produce an erroneous instantiation.
For example, one can see in the state 2 of the Figure 1 that the
rule forced-instantiation can fire twice, once with Q3, once with
Q4. Of course, this does not produce a solution. When the domain
of at least one variable is empty, backtracking is necessary,
since the partial instantiation cannot produce a solution. Two
cases are possible. If there is another possible value into the
domain of the current-hypothesis, the current instantiation is
undone and the following value is chosen by the rule named backtrack-on-value.
To be consistent with this change of value, it is necessary to
retract all the inferences made by the PROPAG module. This is
made by means of the CLIPSís logical conditional element
feature which provides a truth maintenance capability. We obtain
the deletion of the facts var at the current level by retracting
the ordered fact (level-search ?n) (and reasserting it in the
same rule). In addition, the value of the slot state is changed
from blocked to in-progress and, as there is a new value for the
current hypothesis, it is necessary to return immediately in the
PROPAG module.The last case arrives when there is no further possible
value into the domain of the current-hypothesis. In such a case,
the rule named backtrack-on-variable fires. All the facts of the
current level must be deleted and the current level becomes the
previous one. One can notice that the value of the slot state
at the previous level must be blocked because the value of the
variable instantiated at this level must be changed. Moreover,
it is possible that several backtracks on variable must be made
consecutively. And, in all cases, after the rule backtrack-on-variable
fires, the rule backtrack-on-value must fire. For example, it
is the case in Figure 1 after the state 5. The current hypothesis
is Q2, (Q4 has a forced instantiation), the problem is blocked
and there is no more value for Q2. So the rule backtrack-on-variable
fires and just after the rule backtrack-on-value fires with Q1
(see Figure 3).
f-18 (level-search 1)
f-20 (variable (name x1) (level 1) (possible-values 2 3 4) (value
1))
f-27 (pb (state new-depth) (level 1) (current-hypothesis x1))
f-36 (level-search 2)
f-37 (variable (name x2) (level 2) (possible-values) (value 4))
f-41 (variable (name x4) (level 2) (possible-values) (value 3))
; x4 has a forced instantiation
f-42 (variable (name x3) (level 2) (possible-values) (value
nil))
f-43 (pb (state blocked) (level 2) (current-hypothesis x2))
; the rule "backtrack-on-variable" fires
f-18 (level-search 1)
f-20 (variable (name x1) (level 1) (possible-values 2 3 4) (value
1))
f-24 (variable (name x4) (level 1) (possible-values 2 3) (value
nil))
f-25 (variable (name x3) (level 1) (possible-values 2 4) (value
nil))
f-26 (variable (name x2) (level 1) (possible-values 3 4) (value
nil))
f-44 (pb (state blocked) (level 1) (current-hypothesis x1))
; the rule "backtrack-on-value" fires
f-45 (level-search 1)
f-46 (variable (name x1) (level 1) (possible-values 3 4) (value
2))
f-47 (pb (state in-progress) (level 1) (current-hypothesis x1)) |
Figure 3 : Some facts
showing the backtracking mecanism
The fourth rule stops the search (no another solution or even
no solution at all). This is the case when the value of the slot
state is blocked and the value of the slot level is zero into
the fact pb because no more backtrack is possible (there is no
another value in the domain of the first variable chosen as current-hypothesis).
The final rule of this module prints the solution (default printing
method). If the users desire a customized printing we propose
them to define it in the PROPAG module.
| 3.3 The PROPAG
module |
|
As we remarked above this module
contains all the specific templates, facts and rules necessary
for a particular problem. First the users must create within the
template var the facts list containing all the variables describing
the problem. Two slots must be fill in: the slot name and the
multislot possible-values. After this necessary declaration, the
users have to define all the constraints they want to deal with.
We have noted that in all the problems we have treated, we have
to define some new templates in order to describe how the variables
interact. For example, in the N-queens problem we define a template
queen with the slot name (in order to make the link with the facts
issued from var) and the slot row because the number which suffixes
the value of the slot name indicates the number of the row (see
Figure 4)
(deffacts chessboard
(queen (name x1) (row 1))
(queen (name x2) (row 2))
(queen (name x3) (row 3))
(queen (name x4) (row 4))) |
Figure 4 : Facts issued
from the template queen
(defrule PROPAG::propagation-2
; if the queen ?x is placed in the ?n1 row and the ?v column
then remove
; from the list of possible values of the queen ?y all the values
; corresponding to the same diagonal
(logical (level-search ?n))
(not (level-search ?n1&:(> ?n1 ?n)))
(variable (name ?x) (value ?v&~nil) (level ?n))
(queen (name ?x) (row ?n1))
(queen (name ?y) (row ?n2))
?f <- (variable (name ?y) (value nil) (level ?m)
(possible-values $?liste&:(member$ (- ?v (- ?n1 ?n2)) ?liste)))
(not (variable (name ?y) (level ?m1&:(> ?m1 ?m))))
=>
(bind ?var (member$ (- ?v (- ?n1 ?n2)) ?liste))
(if (= ?m ?n) then (modify ?f (possible-values (delete$ ?liste
?var ?var)))
else (duplicate ?f (level ?n) (possible-values (delete$ ?liste
?var ?var)))))
?var ?var))))) |
Figure 5 : A rule of the PROPAG module for the N-queens
Of course, the propagation rules are very particular. But only
the LHS are specific, because the conditional elements describes
the constraints. The RHS of these rules are all the same, since
there is always one single action which deletes a value into the
domain of a not yet instantiated variable. In order to limit the
size of the fact-list, one can note that, when a new level is
created in the stack of hypothesis, we do not duplicate the variables.
We duplicate them only when a change occurs, i.e. the variable
is the current-hypothesis or the variable is concerned by the
propagation. This appears in our rules in the PROPAG module since
in the RHS we need an "if then else" function. If it
is the first reduction of its domain at the current level, then
we need to duplicate the variable, otherwise we have just to modify
it. (see Figure 5).
| 4 Concluding
remarks |
|
Of course, the performance of
this knowledge base cannot be compared with the specialized CSPs
algorithms in terms of time efficiency. However, we had two ideas
in mind while developping this knowledge base.
First, from a pedagogical point of view, one can use CCP to explain
the mecanism of Chronological Backtracking with Forward Checking
and the "first fail" heuristic. Another pedagogical
point of view is the use of many advanced features of CLIPS: the
build function, a control strategy based on the management of
the focus stack, the forall, exists and overall the logical conditional
element.
Secondly, and this is the most important point, we would embed
CCP into a larger knowledge base, since we have noted that, in
some cases, solving a problem needs exploring hypotheses locally.
Moreover, even with pure CSPs, the use of a knowledge based system
must be very efficient, particulary in order to introduce interaction
between the human and the computer during the solving process.
| References |
|
[Forgy, 82] C. L. Forgy: "Rete: a Fast Algorithm for the
Many Pattern/Many Object Pattern Match Problem", AI 19-1,
17-37, 1982
[Haralick et al, 80] R. M. Haralick, G. L. Elliott : "Increasing
Tree Search Efficiency for Constraint Satisfaction Problems",
Artificial Intelligence (14) 263-313, 1980
[Laurière, 78] J.-L. Laurière: "A Language
and a Program for Stating and Solving Combinatorial Problems",
Artificial Intelligence (10) 29-117, 1978
[Laurière, 86] J.-L. Laurière: "Un langage
déclaratif: SNARK", Revue Technique et Science informatiques,
vol 5, n°3, 141-171, 1986
[Minton et al, 92] S. Minton, M. Johnston, A. Philips and P. Laird:
"Minimizing Conflicts: a Heuristic Repair Method for Constraint
Satisfaction and Scheduling Problems", Artificial Intelligence
(58) 161-205, 1992
[Reeves, 93] C. Reeves: Modern Heuristic Techniques for Combinatorial
Problems, Blackwell, 1993
[Schiex et al, 95] T. Shiex, H. Fargier, G. Verfaillie: "Valued
Constraint Satisfaction Problems: Hard and Easy Problems",
Proceedings of IJCAI 95, 631-637, 1995