Christian Bessière
email: bessiere@crim.crim.fr

Arc-Consistency in Dynamic Constraint Satisfaction Problems

Constraint satisfaction problems (CSPs) provide a model often used in Artificial Intelligence. Since the problem of the existence of a solution in a CSP is an NP-complete task, many filtering techniques have been developed for CSPs. The most used filtering techniques are those achieving arc-consistency. Nevertheless, many reasoning problems in AI need to be expressed in a dynamic environment and almost all the techniques already developed to solve CSPs deal only with static CSPs. So, in this paper, we first define what we call a dynamic CSP, and then, give an algorithm achieving arc-consistency in a dynamic CSP. The performances of the algorithm proposed here and of the best algorithm achieving arc-consistency in static CSPs are compared on randomly generated dynamic CSPs. The results show there is an advantage to use our specific algorithm for dynamic CSPs in almost all the cases tested.

Introduction

Constraint satisfaction problems (CSPs) provide a simple and good framework to encode systems of constraints and are widely used for expressing static problems. Nevertheless, many problems in Artificial Intelligence involve reasoning in dynamic environments. To give only one example, in a design process, the designer may add constraints to specify further the problem, or relax constraints when there are no more solutions (see the system to design peptide synthesis plans: SYNTHIA [START_REF] Janssen | Problèmes de Conception : une Approche basée sur la Satisfaction de Contraintes. 9èmes Journées Internationales d[END_REF]). In those cases we need to check if there still exist solutions in the CSP every time a constraint has been added or removed.

Proving the existence of solutions or finding a solution in a CSP are NP-complete tasks. So a filtering step is often applied to CSPs before searching solutions. The most used filtering algorithms are those achieving arcconsistency. All arc-consistency algorithms are written for static CSPs. So, if we add or retract constraints in a CSP and achieve arc-consistency after each modification with one of these algorithms, we will probably do many times almost the same work.

So, in this paper we define a Dynamic CSP (DCSP) ( [Dechter & Dechter 1988], [START_REF] Janssen | Problèmes de Conception : une Approche basée sur la Satisfaction de Contraintes. 9èmes Journées Internationales d[END_REF]) as a sequence of static CSPs each resulting from the addition or retraction of a constraint in the preceding one. We propose an algorithm to maintain arc-consistency in DCSPs which outperforms those written for static CSPs.

The paper is organized as follows. Section 2 presents the CSP model (2.1) and defines what we call a Dynamic CSP (2.2). Arc-consistency filtering method is introduced and the best algorithm achieving it (AC-4 in [START_REF] Mohr | Arc and Path Consistency Revisited[END_REF]) is described (2.3). Why this algorithm is not optimal in DCSPs is underlined in 2.4. Section 3 presents a new method which adapts the idea of AC-4 to reach better performances on DCSPs. In section 4, a comparison of the performances of the two algorithms on randomly generated DCSPs is given. Section 5 contains a summary and some final remarks.

Definitions and preliminaries

Constraint Satisfaction Problems

A static constraint satisfaction problem (CSP) (X, dom, c, R) involves a set of n variables, X = {i, j,...}, each taking value in its respective domain, dom(i), dom(j),..., elements of dom, and a set of constraints c . Each constraint C p in c involves a subset {i 1 ,..., i q } of X and is labeled by a relation R p of R , subset of the Cartesian product dom(i 1 ) x...x dom(i q ), that specifies which values of the variables are compatible with each other. A binary constraint satisfaction problem is one in which all the constraints are binary, i.e., involve two variables. A binary CSP can be associated with a constraint-graph in which nodes represent variables and edges connect those pairs of variables for which constraints are given. In that case, the relation associated with the edge {i, j} can be denoted R ij . Consider, for instance, the CSP presented in figure 1 (modified from [START_REF] Mackworth | Consistency in Networks of Relations[END_REF]). Each node represents a variable whose values are explicitly indicated, and each edge is labeled with the set of value-pairs permitted by the constraint between the variables it connects (non-oriented edges are equality constraints and oriented ones are a strict lexicographic order along the arrows).

(b,b) (c,c) (d,d) (b,b) (c,c) (d,d) (b,b) (c,c) (d,d) (a,b) (a,c) (a,d) (c,d) (b,c) (b,d) (c,
A solution of a CSP is an assignment of values to all the variables such that all the constraints are satisfied. The task, in a CSP, is to find one, or all the solutions.

We now only consider binary CSPs for clarity, but the results presented here can easily be applied to general CSPs [START_REF] Bessière | Using CSPs to encode TMSs[END_REF]].

Dynamic Constraint Satisfaction Problems

A dynamic constraint satisfaction problem (DCSP) p is a sequence of static CSPs p (0) ,..., p (α) , p (α+1) ,..., each resulting from a change in the preceding one imposed by "the outside world". This change can be a restriction (a new constraint is imposed on a pair of variables) or a relaxation (a constraint that was present in the CSP is removed because it is no longer interesting or because the current CSP has no solution).

So, if we have p (α) =(X, dom, c (α) , R), we will have p (α+1) =(X, dom, c (α+1) , R) where c (α+1) =c (α) ± C , C being a constraint. p (0) =(X, dom, ∅, R).

Arc-consistency

The task of finding solutions in a CSP has been treated by several authors, and since the problem is NP-complete, some of them have suggested that a preprocessing or filtering step be applied before the search (or backtracking) procedures. Then, consistency algorithms were proposed ( [START_REF] Montanari | Networks of Constraints: Fundamental Properties and Applications to Picture Processing[END_REF]], [START_REF] Mackworth | Consistency in Networks of Relations[END_REF]], [START_REF] Freuder | Synthesizing Constraint Expressions[END_REF]], [START_REF] Dechter | Network-Based Heuristics for Constraint-Satisfaction Problems[END_REF]). These algorithms do not solve a CSP completely but they eliminate once and for all local inconsistencies that cannot participate in any solutions. These inconsistencies would otherwise have been repeatedly discovered by most backtracking procedures. A k-consistency algorithm removes all inconsistencies involving all subsets of size k of the n variables [START_REF] Freuder | Synthesizing Constraint Expressions[END_REF]]. In fact, the most widely used consistency algorithms are those achieving 2-consistency (or arcconsistency). Arc-consistency checks the consistency of values for each couple of nodes linked by a constraint and removes the values that cannot satisfy this local condition (see figure 2). It is very simple to implement and has a good efficiency. The upper bound time complexity of the best algorithm achieving arc-consistency (AC-4 in [START_REF] Mohr | Arc and Path Consistency Revisited[END_REF]) is O(ed 2 ) with e the number of constraints and d the maximal number of values in the domain of a variable .

(b,b) (c,c) (d,d) (b,b) (c,c) (d,d) (b,b) (c,c) (d,d) (a,b) (a,c) (a,d) (c,d) (b,c) (b,d) (c,
Arc-consistency can be seen as based on the notion of support. A value a for the variable i is viable if there exists at least one value that "supports" it at each variable j. The Mohr's and Henderson's algorithm, AC-4, makes this support evident by assigning a counter to each arc-value pair. Such pairs are denoted [(i, j), a] and indicate the arc from i to j with value a at node i. The edge {i, j} between i and j may be replaced by the two directed arcs (i, j) and (j, i) as they are treated separately by the algorithm (but we still have R ij = R ji -1 ). The counters are designed by counter [(i, j), a] and indicate the number of j values that support the value a for i in the constraint { i, j}. In addition, for each value b at node j , the set S jb is constructed where S jb ={(i, a) / b at node j supports a at node i}, that is, if b is eliminated at node j, then counters at [(i, j), a] must be decremented for each (i, a) supported by (j, b). This algorithm uses too, a table, M , to keep track of which values have been deleted from which nodes, and a list, List, to control the propagation of deletions along the constraints. List is initialized with all values (i, a) having at least one counter equal to zero. These values are removed from M. During the propagation phase, the algorithm takes values (j, b) in List, removes one at each counter counter [(i, j), a] for all (i, a) in S jb , and when a counter [(i, j), a] becomes equal to zero, it deletes (i, a) from M and puts it in List. The algorithm stops when List is empty. That means all values in M have non empty supports on all the constraints. So, the CSP is arcconsistent. And it is the maximal arc-consistent domain.

Arc-consistency in DCSPs

Mohr's and Henderson's algorithm, AC-4, can be used in DCSPs. It keeps all its goods properties when we do a restriction, starting filtering from the current arc-consistent domain and pruning a new value when one of its counters has become zero (i.e. the value has no support on a constraint) after addition of constraints. But, when we remove a constraint (making a relaxation), AC-4 cannot find which value must be put back and which one must not: as it has "forgotten" the reason why a value has been removed, it cannot make the opposite propagation it has done during restrictions. So, we have to start filtering from the initial domain.

A new method

Introduction

As we have seen above, AC-4 does not have good properties (incrementality) for processing relaxations. So, in this section, we propose DnAC-4, a new arc-consistency algorithm for DCSPs. In DnAC-4 we extend AC-4 by recording some informations during restrictions while keeping its good properties. Then, DnAC-4 remains incremental for relaxations. More precisely, during a restriction, for every value deleted, we keep track of the constraint origin of the deletion as the "justification" of the value deleted. The justification is the first constraint on which the value is without support. During a relaxation, with the help of justifications we can incrementaly add to the current domain values that belong to the new maximal arcconsistent domain. But we need to be careful because after the relaxation, the system must be in the same state as if the algorithm had started with the initial CSP p (0) , and had done only restrictions with all the new set of constraints: the new domain must be the maximal arc-consistent domain and the set of justifications of removed values must remain well-founded. Well-founded means that every value removed is justified by a non-cyclic chain of justifications (see figure 2: (2,c) deletion justified by the constraint {2, 6}, (6, c) by {6, 5} and (5, c) by {5, 2} would not be a well-founded set of justifications).

This process of storing a justification for every value deleted is based on the same idea as the system of justifications of deductions in truth maintenance systems (TMSs) [START_REF] Doyle | A Truth Maintenance System[END_REF]], [START_REF] Mcallester | An Outlook on Truth Maintenance[END_REF].

The algorithm DnAC-4

The algorithm we propose works with nearly the same data structures than AC-4. Each arc-value pair [(i, j), a] has a counter of the number of supports, denoted counter [(i, j), a]. A table D of booleans keeps track of which values are in the current domain or not. The first difference is that a set of supported values S jib is constructed for each arc-value pair [(j, i), b]: S jib ={a / b at node j supports a at node i} (we have S jb (of AC-4) equal to ≈S jib for {j, i} ∈ c). So, when a constraint {i, j} is retracted, we delete S ija and S jib for all arc-value pairs [(i, j), a] and [(j, i), b] instead of removing values (i, a) in S jb and values (j, b) in S ia . In the data structure we added a table justif to record the justifications of the values deleted: justif(i, a)=j iff (i, a) has been removed from D because counter [(i, j), a] was equal to zero (i.e. {i, j} is the origin of (i, a) deletion). Then, for all (i, a) in D, justif(i, a)=nil. The lists SL and RL respectively control the propagation of deletions and additions of values along the constraints.

When the algorithm starts with p (0) , the tables are initialized:

for each (i, a ) ∈ dom do begin D(i, a ) , true; justif(i, a ) , nil end;

Adding a constraint {i, j} is done by calling:

procedure Add ({i, j } ); begin Put {i, j } in the set of constraints c; SL , ∅ ; Beg-Add ((i, j ), SL ); Beg-Add ((j, i ), SL ); Propag-Suppress (SL ); end;

• the procedure Beg-Add (see fig. 3) builds counter [(i, j), a], counter [(j, i), b], S ija , S jib , for each values (i, a) and (j, b). It puts in the suppression list S L arc-value pairs without support on {i, j} (i.e. with counter equal to zero). • in the procedure Propag-Suppress (see fig. 4), values without support (in SL) are deleted and the consequences of these deletions are recursively propagated. For all value removed from D, Propag-Suppress updates the table justif. The well-foundness property must be kept after the relaxation of a constraint. So, there are two parts in the relaxation process:

• part1 : the procedure Init-Propag-Relax (see fig. 5) in step 1 puts in the relaxation list R L values (k, a) and (m, b) for which removing was directly due to {k, m} (i.e. justif(k, a)=m or justif(m, b)=k ), and deletes counters and sets of supported values for all arc-value pairs [(k, m ), a] and [(m, k), b]. In step 2 it adds in D values in R L and these adding of values are recursively propagated to each value that has a support restored on the constraint marked as its justification. Init-Propag-Relax finishes when every value with a support on the constraint marked as its justification of deletion is added to D. During this phase of putting back values, when an added value (i, a) is still without support on a constraint {i , j } (i.e. counter [(i, j), a]=0), Init-Propag-Relax puts in SL the arcvalue pair [(i, j) • part2 : Propag-Suppress retracts again values in SL, marking as the new justification the constraint on which the value is still without support (or one of the constraints if there are more than one). These suppressions are propagated: the classic arc-consistency process restarts.

We develop here DnAC-4 on the DCSP of figures 1, 2 and 6, to show the mechanism of justifications: Remarks: -(2, a) is not added in step 1 of the relaxation process because its empty support on {1, 2} (its justification) is not affected by the {2, 3} retraction.

-when step 1 starts, (2, c) has no support on {6, 2}, but since its justification is not {6, 2}, it is added and the propagation shows that (2, c) deleted cannot be supported by a well-founded set of justifications. (2, c) is in the new arcconsistent domain.

-at the end of step 1 (2, b) is still without support on the constraint {2, 4}, so the classic arc-consistency process restarts, deleting (2, b) and propagating.

(b,b) (c,c) (d,d) (b,b) (c,c) (d,d) (b,b) (c,c) (d,d) (a,b) (a,c) (a,d) (b,c) (b,d) (c,

Correctness of DnAC-4

We outline here the key steps for a complete proof given in [START_REF] Bessière | Using CSPs to encode TMSs[END_REF]].

Notations: AC α (dom)=the maximal arc-consistent domain of the CSP p (α) . j), a] / counter [(i, j), a]=0 and (i, a) ∈ D} (* TWS : true without support *) Let E ⁄ dom : p(E) ≡ ∃ (i, a) ∈ E, justif(i, a)=j and S ija ( E = ∅ Basic properties:

dom = {(i, a) / i ∈ X, a ∈ dom(i)} (i, a) ∈ D ⇔ D(i, a)=true TWS = {[(i,
(1) S jib ={a / ((i, a), [(i, j), a] = number of supports of (i, a) on {i, j}

(j, b)) ∈ R ij } (2) counter
(*=∧S ija (D∧ because R ij is symetric *) Justification properties: (3) justif(i, a)=j ⇒ (i, a) ∉ D and counter[(i, j), a]=0 (4) (i, a) ∉ D ⇒ justif(i, a)≠nil
(5) ∀E ⁄ dom\D : p(E)=true (* well-foundness property *) Property 1: The assertion ( TWS ⁄ SL ) denoted (P1) is true after each procedure of DnAC-4. Proof: (P1) was true for p (0) with D=dom because c = ∅ ⇒ TWS = ∅. We can easily verify this remains true by looking lines 8-9 of Beg-Add, lines 8-9 of Propag-Suppress and lines 7 and 12 of Init-Propag-Relax.

❏ Corollary 1: D is an arc-consistent domain at the end of Propag-Suppress. Proof: We know that P1 is true after Propag-Suppress. Line 1 ⇒ SL = ∅ at the end of Propag-Suppress

(P1) ⇒ ∀(i, a) ∈ D, ∀j /{i, j} ∈ c : counter[(i, j), a] > 0 (2) ⇒ ∀(i, a) ∈ D, ∀j /{i, j} ∈ c : (i, a) has a support (j, b) on {i, j} in D ⇒ D is arc-consistent.
❏ Corollary 2: At the end of Add, D is arc-consistent. Corollary 3: At the end of Relax, D is arc-consistent. Lemma 1: The assertion ( AC α (dom) ⁄ D ) is not affected by Propag-Suppress. Proof: Suppose ( AC α (dom) ⁄ D ) is true when Propag-Suppress starts. A value is removed from D if one of its counters is equal to zero. So, it has no supporting value in D on one constraint. Since ( AC α (dom) ⁄ D ) was true before its deletion, the value has no supporting value in AC α (d o m ) on this constraint and couldnot be in AC α (dom). So, ( AC α (dom) ⁄ D ) remains true after the deletion of the value. By induction it remains true during all Propag-Suppress. ❏ Corollary 4: ( AC α (dom) ⁄ D ) is true at the end of Add. Proof: In the procedure Add, before the call of Propag-Suppress, AC α (dom) ⁄ A C α-1 (dom)=D since D is not affected by Beg-Add. From lemma 1 we deduce that ( AC α (dom) ⁄ D ) is true at the end of Add. ❏ The upper bound time complexity for DnAC-4 is trivially O(ed 2 ), like for AC-4. More precisely, on one hand, during a restriction, DnAC-4 checks the consistency of more pairs of values than AC-4. The reason is that during a restriction, DnAC-4 builds S jib and counter [(i, j), a] even after the deletion of the value (i, a) from D , because it needs these informations for an hypothetic future relaxation. AC-4 stops this work, as soon as (i, a) is out of D. On the other hand, during a relaxation, DnAC-4 only checks values needed to verify the well-founded property of justifications. AC-4 handles all the new CSP.

Cases where DnAC-4 is performant

DnAC-4 is efficient when the phase of adding values is short. This is the case when the constraint graph is not connected. Then, the propagation stay in one connectedcomponent.

Actually, what seems the most important for DnAC-4 efficiency is chronology. Indeed, constraints are added step by step, and their coming date is important since the justification of a removed value is the first constraint for which the value had no support. This means that when a "young" constraint is retracted, the algorithm probably propagates a few, as the opposite of the retraction of an "old" constraint that can modify many justifications, and so can make the propagation larger.

Performance comparison

We compared AC-4 to DnAC-4 on randomly generated DCSPs. Two probabilistic parameters were used in the generation of CSPs. pc determines the probability that any two variables are directly connected, and pu the probability that any two values in an existing constraint are permitted. Two other parameters are n the number of variables and d the number of values for each variable.

For each randomly generated CSP, we counted the total number of consistency checks done in AC-4 and in DnAC-4 to achieve arc-consistency when we add successively all the constraints generated. Then, we choosed randomly a constraint which is responsible of at least one value deletion (if there exists any such constraint), and removed this constraint. We counted the number of consistency checks done in AC-4 and in DnAC-4 to achieve again arc-consistency in the CSP. We summed for each algorithm the number of consistency checks done during restrictions and relaxation. The comparison of the results indicates if DnAC-4 is better than AC-4 after only one relaxation (i.e. the number of consistency checks avoided during relaxation is more important than the number done in excess during restrictions).

We We can see that on all the classes of problems tested, after one relaxation of constraint DnAC-4 has recovered the time losed during restrictions. We found only three instances, in class 3, where AC-4 remains better than DnAC-4 after one relaxation. But in that class, CSPs are too restricted and much more than one relaxation is needed before the CSP accepts solutions. So, we can say that DnAC-4 can easily recover its extra-time-consuming.

The very good results after one relaxation in classes 1, 4, 7 and 8 are not really significant because CSPs in that classes are underconstrained, and doing a relaxation in that case is unlikely.

The last remark we can add is that randomly generated CSPs are not the best way to test efficiency of an algorithm. Constraints that are created are meaningless and propagations during relaxations always found very short in our tests could be larger in real applications, and so the algorithm DnAC-4 be less advantageous. But the gain during a relaxation is so important here in all DCSPs tested that we can hope DnAC-4 remains good on real applications.

DnAC-4 is currently under implementation on the SYNTHIA system [START_REF] Janssen | Problèmes de Conception : une Approche basée sur la Satisfaction de Contraintes. 9èmes Journées Internationales d[END_REF].

Conclusion

We have defined what we call Dynamic CSPs and have provided an efficient algorithm (DnAC-4) achieving arcconsistency in DCSPs. We have compared the performances of DnAC-4 and AC-4 (the fastest arcconsistency algorithm on static CSPs) on many different randomly generated CSPs. If DnAC-4 uses a little more time than AC-4 to build an arc-consistent domain after a restriction, it is more efficient for a relaxation because it has learned informations about the reasons of the deletions of values.

DnAC-4 can be useful for many systems that work in a dynamic environment. It can easily be extended to nonbinary CSPs (see [START_REF] Bessière | Using CSPs to encode TMSs[END_REF]).

The data structure created for the algorithm DnAC-4 can be used too to answer requests of the system (or the expert), like: "why this value has been deleted ?". The explanation given is then the set of constraints currently justifying the deletion of the value. It is a TMS-like use.

Figure 1 :

 1 Figure 1: An example of CSP

Figure 2 :

 2 Figure 2: The CSP of fig.1 after application of an arc-consistency algorithm

procedure

  Figure 3

procedure

  Figure 4 Removing a constraint {k, m} is done by calling: procedure Relax ({k, m } ); begin SL , ∅ ; Init-Propag-Relax ({k, m }, SL ); Propag-Suppress (SL ); end;

  b) and (2, c) are added because justification(2, b)={2, 3} and justification(2, c)={2, 3}. So, (5, b) and (5, c) are added and so (6, b) and (6, c) too. • step2: (2, b) has no support on {2, 4} so (2, b) is deleted and justification(2, b)={2, 4}. So, (5, b) and (6, b) are removed too by propagation and their justifications are recorded: justification(5, b)={2, 5} or {5, 6} and justification(6, b)={5, 6} or {6, 2} (it depends of the order of the propagation of suppressions).

Figure 6 :

 6 Figure 6: The CSP of fig.2 after the relaxation of the constraint {2, 3}

Theorem 1 :

 1 At the end of Add we have AC α (dom)=D. Proof: From corollary 2 and 4. ❏ Lemma 2: ( AC α (dom) ⁄ D ) is true at the end of Init-Propag-Relax. Proof: AC α (dom)\D ≠ ∅ implies (from (5)) that:∃ (i, a) ∈ AC α (dom)\D, justif(i, a)=j and S ija ( (AC α (dom)\D ) = ∅ Now justif(i, a)=j (3)(2) ⇒ S ija ( D = ∅ so: S ija ( AC α (dom) = ∅. It is a contradiction because (i, a) ∈ AC α (dom) ❏Theorem 2: At the end of Relax we have AC α (dom)=D.Proof: From lemma 1, 2 and corollary 3. ❏3.4. Complexity of DnAC-4DnAC-4 uses a maximum of 2ed counters (with e the number of edges and d the maximal number of values in the domain of a variable). The tables D and justif have a size of nd. There are 2ed sets S ija , each having a maximal size of d, so they need a total space of O(ed 2 ) which is the space complexity of the algorithm.

Figure 7 :

 7 Figure 7: Results of comparison tests between AC-4 and DnAC-4

  , a].

	procedure Init-Propag-Relax ({k, m }; var SL );
	begin
	{ Step 1: values whose justification was {k, m } are
		put in RL }
	1 RL , ∅ ;
	2 for each a ∈ dom(k ) do
		if justif(k, a )=m then
		begin Append(RL, (k, a )); justif(k, a ) , nil ;
		end;
	3 for each b ∈ dom(m ) do
		if justif(m, b )=k then
		begin Append(RL, (m, b )); justif(m, b ) , nil ;
	end; 4 Delete {k, m } from the set of constraints c and remove
		its counters and sets of supported values;
	{ Step 2: values in RL are added to D and
		consequences are propagated }
	5 while RL ≠ ∅ do
		begin
	6	choose (i, a ) from RL and remove it from RL;
	7	D(i, a ), true ;
	8	for each j / {i, j } ∈ c do
		begin
	9	for each b ∈ S ija do
	1 0	begin counter[(j, i ), b ] , counter[(j, i ), b ] + 1;
	1 1	if justif(j, b )=i then
		begin Append(RL, (j, b )); justif(j, b ) , nil ;
		end;
		end;
	1 2	if counter[(i, j ), a ]=0 then
		Append(SL, [(i, j ), a ] );
		end;
		end;
	end;
		Figure 5

  tested the algorithms on random DCSPs with 8, 12 and 16 variables, having respectively 16, 12 and 8 values. We tried three values for (pc, pu ): (35, 65), (50, 50) and (65, 35). For each of the nine classes of CSPs defined, we made the test on 10 different instances of DCSPs to have a result representative of the class.The results reported in the table below are the averages of the ten tests for each class.

		n=16	d=8		n=12	d=12	n=8	d=16
		pc=35	pc=50	pc=65	pc=35	pc=50	pc=65	pc=35	pc=50	pc=65
		pu=65	pu=50	pu=35	pu=65	pu=50	pu=35	pu=65	pu=50	pu=35
	restrictions AC-4 restrictions DAC-4 relaxation AC-4 relaxation DAC-4	3611 3622 3536 4	3866 4010 3818 28	4498 6968 4526 266	4140 4140 3946 0	4683 4698 4541 11		4223 4449 4136 33	3128 3128 2793 0	3654 3654 3401 0	3298 3337 3142 12
	total AC-4 total DAC-4	7147 3626	7684 4038	9025 7234	8086 4140	9224 4709		8359 4482	5921 3128	7055 3654	6440 3349
	DAC-4 gain	49%	47%	20%	48%	48%	46%	47%	48%	47%

Acknowledgments

I would like to thank particularly Marie-Catherine Vilarem who gives me advice and invaluable help in preparing this paper, and also Philippe Janssen and Philippe Jégou for their useful comments.


Christian Bessière
email: bessiere@crim.fr

Arc-Consistency for Non-Binary Dynamic CSPs

Constraint satisfaction problems (CSPs) provide a model often used in Artificial Intelligence. Since the problem of the existence of a solution in a CSP is an NP-complete task, many filtering techniques have been developed for CSPs. The most used filtering techniques are those achieving arc-consistency. Nevertheless, many reasoning problems in AI need to be expressed in a dynamic environment and almost all the techniques already developed to solve CSPs deal only with static CSPs. So, in this paper, we first recall what we name a dynamic CSP, and then, generalize the incremental algorithm achieving arc-consistency on binary dynamic CSPs to general dynamic CSPs. Like for the binary version of this algorithm, there is an advantage to use our specific algorithm for dynamic CSPs instead of the best static one, GAC4.

Introduction

Constraint satisfaction problems (CSPs) provide a simple and good framework to encode systems of constraints and are widely used to express static problems. Nevertheless, many problems in Artificial Intelligence involve reasoning in dynamic environments. For instance, in a design process, the designer may add constraints to specify further the problem, or relax constraints when there are no more solutions (see the system to design peptide synthesis plans: SYNTHIA [START_REF] Janssen | Synthia: Assisted design of peptide synthesis plans[END_REF]). Every time a constraint has been added or removed we need to check if there still exist solutions in the CSP.

Proving the existence of solutions or finding a solution in a CSP are NP-complete tasks. So, a filtering step is often applied to CSPs before searching solutions. The most used filtering algorithms are those achieving arc-consistency. Almost all arc-consistency algorithms are written for static CSPs. So, if we add or retract constraints in a CSP and achieve arc-consistency after each modification with one of these algorithms, we will probably do many times almost the same work. The only arc-consistency algorithm written for dynamic CSPs, DnAC-4 in [START_REF] Bessière | Arc-Consistency in Dynamic Constraint Satisfaction Problems[END_REF], deals only with binary CSPs.

So, in this paper we recall that a Dynamic CSP (DCSP) is a sequence of static CSPs each resulting from the addition or retraction of a constraint in the preceding one ([3], [START_REF] Bessière | Arc-Consistency in Dynamic Constraint Satisfaction Problems[END_REF]). We propose a generalized version of DnAC-4 to maintain arc-consistency in general DCSPs which outperforms those written for static CSPs.

The paper is organized as follows. Section 2 presents the CSP model (2.1) and defines what is a Dynamic CSP (2.2). Arc-consistency filtering method is introduced and the best algorithm achieving it (GAC4 in [START_REF] Mohr | Good Old Discrete Relaxation[END_REF]) is described (2.3). Why this algorithm is not optimal in DCSPs is underlined in 2.4. Section 3 presents a new method which adapts the idea of GAC4 to reach better performances on DCSPs. Section 4 contains a summary and some final remarks.

Definitions and preliminaries

Constraint Satisfaction Problems

A s t a t i c constraint satisfaction problem (CSP) (X, dom, c) involves a set of n variables, X={i, j…}, each taking value in its respective domain, dom(i), dom(j),…, elements of dom, and a set of constraints c. A constraint C p (i 1 ,…,i q ) constraining the subset {i 1 ,...,i q } of X is a subset of the Cartesian product dom(i 1 )x…xdom(i q ), that specifies which values of the variables are compatible with each other. A constraint is usually represented by the set of all t u p l e s which are not forbidden by it. A s o l u t i o n of a CSP is an assignment of values to all the variables such that all the constraints are satisfied. The task, in a CSP, is to find one, or all the solutions. Consider for instance the CSP presented in fig. 1. Each node represents a variable whose values are explicitly indicated. Each constraint is explicitly given by the list of its admissible tuples (C 1 and C 5 are a strict lexicographic order along the arrows and C 2 , C 3 , C 4 are equality constraints).

Dynamic Constraint Satisfaction Problems

A dynamic constraint satisfaction problem (DCSP) p is a sequence of static CSPs p (0) ,...p (α) , p (α+1) ,..., each resulting from a change in the preceding one imposed by "the outside world". This change can be a r e s t r i c t i o n (a new constraint is imposed on a subset of variables) or a relaxation (a constraint which was present in the CSP is removed because it is no longer interesting or because the current CSP has no solution).

So, if we have p (α) =(X , dom, c (α) ), we will have

p (α+1) =(X, dom, c (α+1) ) where c (α+1) =c (α) ± C, C being a constraint. p (0) =(X, dom, ∅).

Arc-consistency

The task of finding solutions in a CSP has been treated by several authors, and since the problem is NPcomplete, some of them have suggested that a preprocessing or filtering step be applied before the search (or backtracking) procedures. Then, consistency algorithms were proposed ( [START_REF] Montanari | Networks of Constraints: Fundamental Properties and Applications to Picture Processing[END_REF], [START_REF] Mackworth | Consistency in Networks of Relations[END_REF], [START_REF] Freuder | Synthesizing Constraint Expressions[END_REF]). These algorithms do not solve a CSP completely but they eliminate once and for all local inconsistencies that cannot participate in any solutions. These inconsistencies would otherwise have been repeatedly discovered by most backtracking procedures. The most widely used consistency algorithms are those achieving arc-consistency.

Definition.

A tuple u in a constraint C p is viable iff for all variable i constrained by C p , u[i] is a viable value. A value a for a variable i is viable iff for all constraint C p constraining i there exists a viable tuple u in C p such that u[i]=a. A CSP is arcconsistent iff for all i∈X, for all a∈dom(i), a is viable.

The complexity of the best algorithm building the largest arc-consistent domain in general CSPs (GAC4 in [START_REF] Mohr | Good Old Discrete Relaxation[END_REF]) is O(K) with K the sum of the lengths of all tuples for all constraints. It has been shown that it is an optimal algorithm.

The efficiency of GAC4 comes from the data structure it handles which is suitable to the arc-consistency property. Arc-consistency can be seen as based on the notion of support. A value a for the variable i is viable if there exists at least one tuple which "supports" it at each constraint. GAC4 makes this support evident by assigning a set of supports to each constraint-value pair. The sets designed by S iap contain the tuples in C p that support the value a for the variable i. The algorithm is founded on a recursive value pruning, deleting a value when it has no support on a constraint, and then removing at their turn all tuples including this value. And so on until all remaining values have support on all the constraints. So, the CSP is arc-consistent. And it is the maximal arc-consistent domain.

Arc-consistency in DCSPs

Mohr's and Masini's algorithm, GAC4, can be used in DCSPs. It keeps all its goods properties when we do a restriction, starting filtering from the current arcconsistent domain and pruning a new value when one of its support sets is empty after addition of constraints. But, when we remove a constraint (making a relaxation), GAC4 cannot find which value must be put back and which one must not: as it has "forgotten" the reason why a value has been removed, it cannot make the opposite propagation it has done during restrictions. So, we have to start filtering from the initial domain.

The incremental method

Introduction

As we have seen above, GAC4 does not have good properties (incrementality) for processing relaxations. So, in this section, we propose DnGAC4, a new arcconsistency algorithm for DCSPs. In DnGAC4 we extend GAC4 by recording some informations during restrictions while keeping its good properties. Then, DnGAC4 remains incremental for relaxations.

More precisely, during a restriction, for every value deleted, we keep track of the constraint origin of the deletion as the "justification" of the value deleted. The justification is the first constraint on which the value is without support. For every tuple deleted, we keep track of the value origin of its deletion as the "killer" of the tuple deleted. The killer is the first value retracted in the tuple. During a relaxation, with the help of justifications and killers, we can incrementally add to the current domain values which belong to the new maximal arc-consistent domain. But we need to be careful because after the relaxation the system must be in the same state as if the algorithm had started with the initial CSP p (0) and had done only restrictions with all the new set of constraints: the set of justifications and killers must remain well-founded to ensure that the new domain is the maximal arc-consistent domain.

Definition. Justifications and killers are wellfounded iff in any set E of retracted values there exists a value (i, a) such that, its justification being the constraint C p , every tuple of C p including (i, a) has its killer out of E.

In other words, well-foundness means that every removed value is justified by a non-cyclic chain of justifications and killers. The value is not recorded as one of the reasons of its self deletion. {(i, a, p)/ S iap =∅ and (i, a) ∈ D} ⁄ SL [START_REF] Mackworth | Consistency in Networks of Relations[END_REF] killer(u)=(i, a) ⇒ (i, a) ∈ u and (i, a) ∉ D [START_REF] Freuder | Synthesizing Constraint Expressions[END_REF] u ! D ⇒ killer(u)≠nil [START_REF] Bessière | Algorithmes d'arc-consistance pour les CSP dynamiques[END_REF] ∀E⁄dom\D: ∃(i, a)∈E: justif(i, a)=p and ∀u∈C p /(i, a)∈u: killer(u) ∉ E {well-founded property} From (5) we can deduce that D is arc-consistent at the end of Propag-Suppress, so at the end of Add or Relax too. From Propag-Suppress construction we can see that if D includes the maximal arc-consistent domain at its begining, this remains true at its end. Now, we need only to prove that when Propag-Suppress begins, we always have D including the maximal arc-consistent domain. It is evident in Add, and for Relax, we can prove this using properties ( 6), ( 7), ( 8) and looking Init-Propag-Relax construction.

Complexity of DnGAC4

In DnGAC4, the bigger data structures are the S iap and T iap lists of tuples. They take the same space as all the constraints C p in the CSP. This space is linear in the sum of the lengths of all the tuples of all the constraints (it is linear in the size of the problem).

The upper bound time complexity of DnGAC4, like in GAC4, is linear in the size of the problem since the atomic operations are first Append(S iap , u), and then Suppress(S iap , u) (the total size of the S iap sets being bounded by the size of the problem). But these operations must be processed in constant time. A suitable data structure is shown in [START_REF] Mohr | Good Old Discrete Relaxation[END_REF].

If we want to specify the complexity of DnGAC4, we can say that, on one hand, during a restriction, DnGAC4 does a little more processing than GAC4, building a more complex data structure (for each tuple a killer is stored, and for each value we record a justification). On the other hand, during a relaxation, DnGAC4 only checks values and tuples needed to verify the wellfounded property of justifications and killers. GAC4 handles all the new CSP.

Performance comparison

There are too many parameters in general DCSPs to provide significant tests on randomly generated DCSPs but it seems that DnGAC4 on general DCSPs works at least as better as DnAC-4 on binary DCSPs. If DnGAC4 is applied on CSPs containing only ternary constraints, we can see that it generally outperforms GAC4 after the first relaxation of constraint, reaching a gain of 35% (average of the classes of CSPs tested) on the sum of the running time of all restrictions plus the relaxation. More, if we modify the DCSP several times, adding and removing constraints until we find a "good" consistent CSP (what is done in all design problems) we remark that the gain of DnGAC4 fastly grows and overtops 50% after two or three relaxations. More changes will be done, more the use of DnGAC4 will be interesting.

DnGAC4 is now under implementation on SYNTHIA [START_REF] Janssen | Synthia: Assisted design of peptide synthesis plans[END_REF].

Conclusion

We have defined what we call Dynamic CSPs and have underlined that there does not exist algorithms incrementally maintaining arc-consistency in general DCSPs (there exists one only for binary DCSPs). We have noticed that arc-consistency is the most used filtering technique in CSPs, and so, it is important to have an incremental algorithm for all DCSPs. Then, we have provided an efficient algorithm (DnGAC4) incrementally achieving arc-consistency in general DCSPs. DnGAC4 can be useful for many systems which work in a dynamic environment.

Figure 1 :

 1 Figure 1: An example of CSP

Acknowledgements

I would like to thank particularly Marie-Catherine Vilarem for the implementation of my work on SYNTHIA and Philippe David who gives me constructive suggestions for the final draft.

The algorithm DnGAC4

The algorithm we propose works with the following data structures:

• a table D of booleans keeps track of which values are in the current domain or not (the current domain being named D we confuse (i, a)∈D and D(i, a)=true) • a set of supports for each value on each constraint: S iap ={u∈C p /(i, a)∈u and u is viable} • for each value, the constraint origin of its deletion is stored in justif (i, a).

if (i, a) is viable, justif(i, a)=nil else justif(i, a)=the number of the first constraint on which (i, a) had got an empty support.

• for each tuple, we store in killer(u) the first value deleted in it.

if u is viable, killer(u)=nil else killer(u)=the first value in u retracted from D. • a set of killed tuples for each value on each constraint: T iap ={u∈C p /killer(u)=(i, a)} • the lists S L and R L respectively control the propagation of deletions and additions of values along the constraints; the list UL records for reconsideration the tuples put back to ensure well-foundness but that still have a killer.

Before giving the algorithms, we define the function find-killer which will be used in the following. Add a constraint C p to the DCSP is done by calling the procedure Add.

procedure Add (C p (i 1 ,…,i q ): constraint); Put C p (i 1 ,…,i q ) in c; SL , ∅ ; Init-Add (C p (i 1 ,…,i q ), SL ); Propag-Suppress (SL ); for all i ∈ {i 1 ,…,i q } do 9 for all a ∈ dom(i ) do 10 if D(i, a ) and S iap = ∅ then Append(SL, (i, a, p ));

• the procedure Propag-Suppress takes constraint-value pairs (i, a, m ) in SL, removes (i, a) from D , updates justif(i, a) and also killer(u) for all u viable such that (i, a) ∈ u. These tuples u are added to T iap and removed from all S jbp which they were belonging. If a S jbp becomes empty, (j, b, p) is added in SL. And so on.

procedure Propag-Suppress (in out SL: list); To retract the constraint C m (i 1 ,…,i q ) from the DCSP we call the procedure Relax.

procedure Relax (C m (i 1 ,…,i q ): constraint); SL , ∅ ; Init-Propag-Relax (C m (i 1 ,…,i q ), SL ); Propag-Suppress (SL )

Two parts are needed in the relaxation process to maintain the well-founded property.

• part 1. first, the procedure Init-Propag-Relax adds to D and puts in RL all values (i, a ) for which deletion was justified by C m (i.e. justif(i, a)=m). In a second step, the consequences of the addition of these values (i, a) to D are propagated. Tuples u deleted by them (killer(u)=(i, a)) are put back in the supports lists S jbp of values (j, b) that they support (lines 13-15), except if there is another value of u for which we are sure that retraction is independant of u's retraction (lines 10-12). At each tuple put back, we add in D and in RL every (j, b) which has the supports set S jbp that becomes non empty on its justification constraint (p=justif(j, b)) (line 16). Additions of values are recursively propagated: this second step processes while RL is non empty. In this second step, if a tuple is added when it includes values not in D because we are not sure of the independance of the retraction of these values, we add it in a list UL which records these "suspended" tuples (line 17). In the third step, we check if these suspended tuples are really saved (their killers were not independent, they had not a well-founded justification) or if their killers are still present. In this latter case, we kill again the tuple and remove it from the supports sets of the values it supports.

During all the procedure Init-Propag-Relax, each time a support set S jbp of an added value (j, b ) is found empty, we put the constraint-value pair (j, b, p) in SL. • part 2. Propag-Suppress takes constraint-value pairs (i, a, m) in SL and removes again from D values (i, a) which still are without support on the constraint C m (S iam =∅). These retractions are propagated on the tuples and on the other values: the classic arcconsistency process restarts.

We develop here DnGAC4 on the DCSP of fig. 1, to show the mechanism of justifications and killers (notation: u p q is the qth tuple of the constraint C p ). Then, killer(u 3 1 ) , ( 3 , a ) and (4 , a ) is discarded (justif(4 , a ),3 ). We have the new maximal arcconsistent domain.

Correctness of DnGAC4

We give here the properties true after each procedure of DnGAC4 which are needed to prove the correctness of the algorithm. For a complete proof we will see [START_REF] Bessière | Algorithmes d'arc-consistance pour les CSP dynamiques[END_REF].


Christian Bessière
email: bessiere@crim.fr

Application of Constraint Networks Filtering Techniques to Truth Maintenance Systems

A truth maintenance system (TMS) is a general problem solving facility designed to work in tandem with an inference engine. Justification-based TMSs (the most commonly used TMSs) have not a sufficient expressive power for many applications. Logic-based TMSs overcome this limitation but are untractable. So, McAllester, or Forbus and de Kleer, have proposed to encode formulae in clauses and to run the efficient Boolean Constraint Propagation algorithm (BCP), what lose the completeness of the deductions. In this paper, we introduce the model of Constraint Networks (CNs), underlining that the notion of local completeness (called local-consistency in CNs) has been widely treated in CNs. We then propose an encoding of McAllester's TMS in Dynamic CN to be able to use CNs techniques. We show that not only we can compute as many deductions as BCP for the same time-consuming, but also we can outperform the local completeness computed for a slight more running-time. AI topic: reasoning Domain area: Expert systems, problem solving Impact: The estimated benefit is 40% more information deduced (in average) in a problem solver, while keeping reasonable time-consuming.

Introduction

In this paper, we briefly recall that Justification-based TMSs have not a sufficient expressive power for many applications (see [START_REF] Forbus | Truth Maintenance Systems[END_REF]). We present Logic-based TMSs (LTMSs) and remark that efficiency and completeness cannot hold together since any SAT problem can be encoded in an LTMS. Then, the problem is to find a compromise between efficiency and completeness. The usual way is to encode arbitrary formulae into Conjunctive Normal Form (CNF) and to run the efficient Boolean Constraint Propagation algorithm (BCP). De Kleer has shown in [START_REF] De Kleer | Exploiting locality in a TMS[END_REF] that encoding formulae into CNF results in losing locality properties of the original formulae and leads BCP to fail on some deductions. He proposed to solve local incompleteness by locally compiling formulae into their prime implicates.

We propose here another alternative, starting from the observation that the notions of incompleteness or local completeness are well known and have been widely treated in Constraint Networks (CNs). The idea is to encode an LTMS into a CN and to find CNs filtering techniques which compute the same deductions as the TMS's algorithm BCP, for the same cost. Then, we will look for another filtering technique which provides more deductions (i.e. less incomplete) for a sligth more running-time.

The rest of the paper is organized as follows: Section 2 presents the basic definitions on TMSs and underlines the drawbacks and advantages of each class saying why McAllester's TMS is interesting. Section 3 introduces CNs definitions necessary to understand the next section. Section 4 begins with a representation of McAllester's TMS in a Dynamic CN, gives properties of this representation and shows that we can improve the deduction algorithm using a well known CNs filtering technique. An experimental comparison of BCP and this new approach is given. Section 5 is a conclusion on the interest of this approach.

Definitions and preliminaries on truth maintenance systems

A truth maintenance system (T M S ) is a general problem solving facility designed to work in tandem with an inference engine. A TMS takes assertions from the problem solver (or inference engine). It produces deductions from the set of assertions and maintains justifications of its deductions. It incrementally updates its beliefs when assumptions are added or removed. It does dependency directed backtracking (DDB) when a contradiction arises to track down the assumptions which underlie that contradiction.

A large part of the definitions given in sections 2.1. and 2.2. are taken from [START_REF] Zabih | A Rearrangement Search Strategy for Determining Propositional Satisfiability[END_REF], [START_REF] De Kleer | Exploiting locality in a TMS[END_REF] and [START_REF] Forbus | Truth Maintenance Systems[END_REF]. We have limited the discussion to monotonic TMSs. Doyle's TMS with nonmonotonic justifications is not considered here, involving problems out of the topic of this paper.

Logic-based TMS (LTMS)

Justification-based truth maintenance system (JTMS) is the simplest and most commonly used type of TMS. A JTMS deals only with Horn clauses. It is sufficient for some applications but the expressive power is very limited.

Many applications need to express more than just Horn clauses. Logic-based TMSs (LTMSs) overcome this limitation. Unlike the JTMS, the LTMS allows one to express negation explicitly and to use the four usual binary connectives (∨, ∧, → and ≡ ). Therefore, it can represent any propositional formula.

Definition 2.1. A LTMS involves a set of

propositional symbols S, a set of propositional formulae F and a set of assumption literals A . A literal is either a propositional symbol σ of S or the negation ¬σ of a symbol σ. A formula is defined in the usual way with the connectives ¬, ∨, ∧, → and ≡ in terms of propositional symbols. The reason for distinguishing A from F is that F grows monotonically while assumptions may be added or removed from A at any time.

Definition 2.2.

A labeling λ is a mapping from S to the set {T, F, U} (T for true, F for false, and U for unknown). If for all σ in S, λ(σ)≠U then λ is complete; otherwise λ is partial. A completion of a partial labeling is a complete labeling which relabels all the U symbols T or F. The label of the literal σ is the label of the symbol σ and the label of the literal ¬σ is F, T or U depending on whether the label of σ is T, F or U. The label T or F for a literal is also called the truth value of the literal. For any labeling λ, literal l, we define λ[l←v] as the labeling which is identical to λ except that it assigns the literal l the truth value v.

Since in an LTMS the set F can contain any propositional formula, determining the satisfiability of F ∪ A or discovering if a label for a symbol logically follows from F ∪ A will be NP-complete tasks. So, LTMSs are usually implemented with the useful Boolean Constraint Propagation algorithm (BCP) to reduce the cost of deductions updating. BCP is sound but incomplete. Propositional formulae of F are called now constraints.

For BCP, given any labeling λ , each constraint is in one of 4 possible states:

• the constraint is satisfied: for every completion of λ the constraint is true. For example, if λ(x)=T, then the constraint x∨y is satisfied.

• the constraint is violated: there is no completion of λ which satisfies the constraint. For example, if λ(x)=T, then the constraint ¬x∧y is violated.

• the constraint forces a symbol's label: for every completion of λ which makes the constraint true, the symbol is always labeled T or always F. There may be multiple such symbols. For example, if λ(x)=T, then the constraint (x∨y)→z forces z to be labeled T.

• otherwise the constraint is open. BCP labels T , F or U every symbol of S . BCP processes the initial set of assumption literals A ; if σ ∈ A then σ is labeled T , and if ¬σ ∈ A then σ is labeled F. All remaining symbols are initially labeled U. BCP processes the constraints one at a time monotonically expanding the current labeling λ:

Algorithm BCP(F ∪ A , λ) 1. if F ∪ A contains any violated constraint then exit.
2. if F ∪ A contains any constraint that forces a label for a symbol, then select such a constraint C, select a symbol σ that C forces to the truth value v and return BCP(F ∪ A, λ[σ←v]).

otherwise return the labeling λ.

The problem of this algorithm is that determining whether a constraint is violated or whether a constraint forces a symbol's label are NP-complete tasks (since constraints are arbitrary formulae). So, each of these steps in BCP is exponential in the size of the constraint considered.

Clause-based TMS (CTMS)

BCP on arbitrary formulae is not very efficient since it is exponential in the size of the formulae. So, in practice, LTMSs are often restricted to clause-based T M S s (abbreviated CTMSs).

Definition 2.3. A CTMS involves a set of

propositional symbols S, a set of clauses F c instead of a set of arbitrary formulae F , and a set of assumption literals A . A clause is a disjunction of literals.

The algorithm BCP is still available in CTMSs. But tasks that were expensive on arbitrary formulae become straightforward on clauses.

Given a labeling λ, a constraint C ∈ F c is:

• Satisfied if some literal of C is labeled T. • Violated if every literal of C is labeled F.
• Unit open if one literal is labeled U and the remainder F (i.e. C forces the label T for this literal).

• Open if more than one literal is labeled U and the remainder F.

Therefore, BCP on clauses (which is similar to unit resolution) is very efficient. Even finding the justification for a deduced literal is done by simply taking the other literals of the clause where the deduction has been made (all of them must be labeled F to deduce the label T for the last one). So, it is sufficient to record the clause as the justification of the deduction. If we denote C the number of literals in a clause and F c  the sum of the

C i  for all C i ∈ F c then the complexity of BCP on F c ∪ A is O(F c +A).
Remark. JTMSs are particular CTMSs. BCP detects all contradictions in JTMSs.

McAllester's TMS (MTMS)

CTMSs implemented with BCP are very efficient but have a limited expressive power compared to general LTMSs. Hence, some authors (McAllester in [START_REF] Mcallester | An Outlook on Truth Maintenance[END_REF], Forbus and deKleer in [START_REF] Forbus | Truth Maintenance Systems[END_REF]) have proposed TMSs allowing any propositional formulae (in what they look like general LTMSs) but translating these arbitrary formulae in clauses before running BCP (in what they work like CTMSs). The difference between McAllester's TMS and Forbus's and deKleer's one is that in [START_REF] Forbus | Truth Maintenance Systems[END_REF] formulae are directly translated into Conjonctive Normal Form (CNF), when in [START_REF] Mcallester | An Outlook on Truth Maintenance[END_REF], formulae are decomposed into ternary formulae with the help of new symbols before translating them into CNF.

In this section, we try to give a formal definition of the TMS presented by McAllester and denoted MTMS in the rest of this paper. Definition 2.4. A well-formed formula (wff) is a formula or the negation of a formula involving a binary connective (∨, ∧, → or ≡) and two terms that are literals or wffs:

Let f be a formula, f is a wff iff • f = (f 1 ∨ f 2 ), or f = (f 1 ∧ f 2 ), or f = (f 1 → f 2 ), or f = (f 1 ≡ f 2 ) with f 1 , f 2 wffs or literals (f is a positive wff)
• or f = ¬f 1 with f 1 a wff. The main idea in a MTMS is the decomposition of any formula given as an assumption (or assertion) to the MTMS, in a set of ternary formulae. Each positive wff included in the formula given to the MTMS is associated to a new symbol by the connective ≡. For example, the formula (¬(x∨y)→z)) will be decomposed in the set of ternary formulae {φ 2 ≡(x∨y)) ; φ 1 ≡(¬φ 2 →z))}, φ 1 and φ 2 being two new symbols. φ 1 represents the formula (¬(x∨y)→z)).

Definition 2.5. A MTMS involves in an

external level, a set of propositional symbols S s and a set of assumptions F a which are visible to the user.

Any literal or wff can be an assumption.

In an internal level, the kernel, not visible to the user, it involves another set S wff of symbols (in addition to S s ), a set of clauses F c and a set of assumption literals A.

• There is a one to one mapping between S wff and the set of the positive wffs which appear in formulae of F a1 . Each symbol φ in S wff is associated to a positive wff f=(f 1 * f 2 ) by the ternary formula φ≡(l 1 * l 2 ) where l 1 and l 2 are the literals associated to the wffs f 1 and f 2 (with * ∈ {∨, ∧, →, ≡})2 .

• These ternary formulae are encoded in F c by their CNF.

• Every literal in F a or associated to a wff element of F a is put in A. A MTMS seen from the outside is powerful enough to encode any propositional formula, but inside is built like a CTMS and so is very efficient. What are the drawbacks ? When a formula is encoded in CNF it is decomposed in several clauses. Now, BCP is inherently local, considering only one propositional formula at a time. So, BCP is complete when applied to one formula, but not when applied to several formulae because of its locality. For example, BCP applied to the formula ((p→q)∧(p∨q)) deduces q, but applied to the set of clauses {(¬p∨q); (p∨q)} it does not deduce anything. So, BCP applied to the CNF of a formula is less powerful than applied to the original formula. The clauses of the CNF of a formula taken one after one forget local properties of the formula. The solution given by de Kleer in [START_REF] De Kleer | Exploiting locality in a TMS[END_REF] was to decompose formulae not into CNF but into prime implicates. BCP applied to the set of the prime implicates of a set of formulae is complete. Since there can be an exponential number of prime implicates for a set of formulae, deKleer proposed to build prime implicates only for formulae taken individually. Running BCP on the prime implicates of the individual formulae is the same as running BCP on the original formulae and he can exploit the efficiency of BCP on clauses. But computing prime implicates of a formula can be exponential in the size of the formula.

Constraint networks basic definitions

Constraint networks

A static constraint network (CN) (X, dom, c) involves a set of variables, X = {i, j,...}, each taking value in its respective domain, dom(i), dom(j),..., and a set of constraints c. Each constraint C(i 1 ,...,i q ) constraining the subset {i 1 ,...,i q } of X, is a set of tuples, subset of the Cartesian product dom(i 1 ) x...x dom(i q ), that specifies which values of the variables are compatible with each other.

A solution of a CN is an assignment of values to all the variables such that all the constraints are satisfied.

Dynamic constraint networks

A dynamic constraint network (DCN) p is a sequence of static CNs p (0) ,..., p (α) , p (α+1) ,..., each resulting from a change in the preceding one imposed by "the outside world". This change can be a restriction (a new constraint is imposed on a subset of variables) or a relaxation (a constraint which was present in the CN is removed).

So, if we have p (α) =(X (α) , dom (α) , c (α) ), we will have p (α+1) =(X (α+1) , dom (α+1) , c (α+1) ) where c (α+1) =c (α) ± C(i 1 ,...,i q ) and X (α+1) =X (α) ∪{i 1 ,...,i q }, C(i 1 ,...,i q ) being a constraint.

Local consistency properties

Since the task of finding a solution in a CN is NPcomplete, local consistency algorithms were proposed by many authors ( [START_REF] Montanari | Networks of Constraints: Fundamental Properties and Applications to Picture Processing[END_REF], [START_REF] Mackworth | Consistency in Networks of Relations[END_REF], [START_REF] Freuder | Synthesizing Constraint Expressions[END_REF]). These algorithms do not solve a CN completely but they eliminate once and for all local inconsistencies that cannot participate in any solutions.

The most widely used consistency algorithms are those achieving arc-consistency. Arc-consistency checks the consistency of values for each pair of variables linked by a constraint and removes the values that cannot satisfy this local condition. Definition 3.1. A CN is arc-consistent iff for all i in X, dom(i)≠∅ and for all v i in d o m (i), for all C(i 1 ,..., i q ) in c with i in {i 1 ,..., i q }, there exists

v i1 ...v iq in d o m ( i 1 )...dom(i q ) such that (v i1 ...v i ...v iq ) is a tuple in C.
Arc-consistency is very simple to implement and has a good efficiency. Its complexity is O(K) with K the sum of the lengths of all admissible tuples for all constraints in c [START_REF] Mohr | Good Old Discrete Relaxation[END_REF].

Pairwise-consistency is another local consistency property which checks the consistency of tuples for pairs of constraints involving common variables. Pairwiseconsistency has first been introduced in [START_REF] Beeri | On the desirability of acyclic database schemes[END_REF] on database schemes and has been applied to CNs in [START_REF] Janssen | A Filtering Process for General Constraint-Satisfaction Problems: Achieving Pairewise-Consistency Using an Associated Binary Representation[END_REF]. Definition 3.2. A CN is pairwise-consistent iff for all C(i 1 ,...,i q ) in c , C (i 1 ,...,i q )≠∅ and for all C(i 1 ,...,i q ) in c , for all C'(j 1 ,..., j p ) in c , with I={i 1 ,...,i q }∩{j 1 ,..., j p }≠∅, we have

C[ I ]=C'[ I ],
where C[ I ] is the projection of the tuples of C on I.

Encoding a TMS in dynamic CN

We have seen in section 2 that in a TMS we have to choose between expressive power and efficiency. If we choose to keep both of them like McAllester, or Forbus and de Kleer, we lose completeness. The compromise made by de Kleer when computing prime implicates, is to lose a bit of efficiency to earn local completeness. This approach is very similar to consistency algorithms used in CNs.

So, we propose a representation of McAllester's TMS in dynamic CN (called c o u p l e d -M T M S in the following) to be able to use CNs resolution techniques.

The transformation Definition 4.1.

A coupled-MTMS is a MTMS in which the kernel is represented by the dynamic CN (s=s s ∪s wff , {T, F} s , f c ∪a). The sets of symbols S s and S wff are replaced by the sets of bi-valued variables s s and s wff , the set of clauses F c is replaced by a set of ternary constraints f c and the set of assumption literals A by the set of unary constraints a. Every time CNF(φ≡(l 1* l 2 )) was added to F c in the MTMS's kernel (with * ∈{→, ∨, ∧, ≡}), the ternary constraint CNconstraint(φ≡(l 1* l 2 )) is added to f c in the kernel of the coupled-MTMS 3 . Every time a literal σ (resp. ¬σ) was added or retracted from A, then the unary constraint V σ =T (resp. V σ =F) is added or retracted from a, V σ being the variable in s corresponding to the symbol σ.

Remark. The domain of every variable of s s or s wff is {T, F}. So, if V σ is the variable in the CN representation of the kernel corresponding to the symbol σ in the MTMS, we can define the labeling λ in the MTMS corresponding to the domain dom in the CN representation of the kernel, by:

dom(V σ )={T} ⇔ λ(σ)=T dom(V σ )={F} ⇔ λ(σ)=F dom(V σ )={T, F} ⇔ λ(σ)=U

Properties of the CN representation

The proofs of all properties and theorems which follow are given in the full paper [START_REF] Bessière | Using CSPs to encode TMSs[END_REF]. Property 4.2. For all wff f, its representation in a MTMS or in a coupled-MTMS are logically equivalent and proportional in size. Theorem 4.3. BCP in a MTMS or an algorithm that achieve arc-consistency in a coupled-MTMS produce exactly the same deductions. Property 4.4. Using the incremental algorithm DnGAC4 ( [START_REF] Bessière | Arc-Consistency in Dynamic Constraint Satisfaction Problems[END_REF], [START_REF] Bessière | Arc-Consistency for Non-Binary Dynamic CSPs[END_REF]) to achieve arc-consistency in a coupled-MTMS or using BCP in a MTMS give proportional time consuming for any addition or retraction of assumption in F a . More, with DnGAC4, finding the justification of a deduced label for a symbol is as simple as in BCP on clauses.

We have defined a representation of a MTMS in terms of CNs (the coupled-MTMS) without any loss of efficiency. All the tasks processed by a MTMS are still available in a coupled-MTMS, and for the same cost.

Enhancing completeness

Having a representation of a MTMS in terms of CNs without loss of expressive power or efficiency, we can look for using CN techniques to achieve a local consistency stronger than arc-consistency without losing too much efficiency. Pairwise-consistency is a consistency property a "little stronger" than arc-consistency. Arcconsistency was complete for an individual constraint, pairwise-consistency is complete for a pair of constraints. Used in a coupled-MTMS it seems that pairwiseconsistency provides a good improvement in the number of deductions without involving a big loss of efficiency. The complexity of pairwise-consistency in a coupled-MTMS is O (m . log(m)) with m the number of CN constraints 4 . By properties 2.6. and 4.2., m is proportional to F a , the sum of the sizes of the formulae in the coupled-MTMS. So, the complexity of pairwiseconsistency in a coupled-MTMS is O(F a  . logF a ).

Example. Let the two formulae f 1 =(¬(x∨y)→z) and f 2 =(¬(x∨y)∨z). BCP on the CNF of the two formulae in Forbus's and de Kleer's TMS or BCP in a MTMS with F a ={f 1 , f 2 } as input does not deduce anything for z .

But let see what happens in a coupled-MTMS achieving arc plus pairwise consistencies.

After the addition of f 1 and f 2 in F a , we have:

s wff ={φ 1 , φ 2 , φ 3
}, three new symbols created to be associated to the positive formulae in F a (see the example of section 2.3.). Pairwise-consistency plus arc-consistency (see fig. 2) deduce the label T for z from the formulae f 1 and f 2 . We can remark that arc-consistency alone (like BCP) does not deduce z's value.

f c ={CNconstraint(φ 2 ≡(x∨y)), CNconstraint(φ 1 ≡(¬φ 2 →z)), CNconstraint(φ 3 ≡(¬φ 2 ∨z))} a={φ 1 =T, φ 3 =T} z φ1 T F T T T F F F F T T T φ2 z φ3 T F T T T F F F F T T T φ2 x y φ2 T F T T T F F F F T

Experimental results

We have compared the number of deductions made by BCP in a MTMS and by pairewise-consistency in a coupled-MTMS on randomly generated sets of clauses. We have made these tests on 3 classes of problems, with ten instances in each class (we give only the average of the ten instances). The problems have a fixed number of variables and a fixed number of binary and ternary clauses. We compare the number of deductions made by each algorithm when the number of unary clauses added (assumption literals) increases. We have generated only satisfiable problems.

Seeing figures 3 and 4, the first remark, evident, is that BCP cannot deduce anything if there does not exist unary clauses at the begining of the deduction process. The number of deductions made by pairewiseconsistency is almost always more than 40% better than BCP on the same problem. The difference between the two algorithms is the largest when there are more non-unary clauses and less assumption literals. This is what is wanted in a problem solver: adding less assumptions and having more informations. On all the classes tested, BCP needs more than twice as many assumption literals as pairewise-consistency to deduce the same number of values. It means, for example, that contradictions will be discovered twice later (in number of assumptions) than with pairewise-consistency. On all these tests, time-consuming of pairewiseconsistency remains between 1.8 and 2.7 times as much as BCP's.

Conclusion

In this paper, we have presented the main classes of TMSs and focused on one, interesting when a large expressive power is needed without losing too much efficiency. We have shown its drawbacks and recalled one solution given by deKleer to reach stronger completeness with prime implicates. In section 4, we have introduced a new approach, encoding a TMS into a Dynamic CN to apply CNs techniques. We have presented CNs local consistency techniques that in essence, look like some techniques used in TMSs. So, the comparison was easy. The first one (arc-consistency) is as powerful as BCP the main used algorithm on TMSs. The second one (pairwise-consistency) outperforms BCP for a slight more running time. Experimental results show that pairewiseconsistency is an interesting method to maintain a local completeness in a TMS.

Property 2 . 6 .Property 2 . 7 .

 2627 In a MTMS, F c ∪ A and F a are proportional in size. In a MTMS, F c ∪ A and F a are logically equivalent (i.e. the labelings satisfying F c ∪ A restricted to the symbols in S s are the labelings satisfying F a ).Example. Suppose the assumption formula (¬(x∨y)→z)arrives in F a , x, y and z being symbols of S s . The symbol associated to the formula must be put in A. If the formula was not already known, a symbol φ 1 is created in S wff .(x∨y) is a positive wff too, for which a symbol φ 2 is created in S wff . φ 2 and φ 1 are associated to the formulae by the connective ≡ : CNF(φ 2 ≡ ( x ∨ y )) and CNF(φ 1 ≡(¬φ 2 →z)) are added to F c . Now, φ 1 can be added to A. Suppose that the formula (¬(x∨y)∨z) arrives now in F a . A symbol φ 3 must be associated to the formula and put in A. The positive wff (x∨y) which appear in the formula was already known, so we need only to put CNF(φ 3 ≡(¬φ 2 ∨z)) in F c and φ 3 in A . Now, if the assumption (¬(x∨y)→z) is removed from F a , we simply retract φ 1 from A.

Figure 1 .

 1 Figure1. This CN is not pairewise-consistent. We have to discard the tuple (a, a, a) from the constraint C 1 (1, 2, 3) and the tuple (b, a, b) from the constraint C 2[START_REF] De Kleer | Exploiting locality in a TMS[END_REF][START_REF] Zabih | A Rearrangement Search Strategy for Determining Propositional Satisfiability[END_REF][START_REF] Mcallester | An Outlook on Truth Maintenance[END_REF]

Figure 2 .

 2 Figure 2. The ternary constraints in the coupled-MTMS and the deduction processes

Figure 3 .

 3 Figure 3. Comparison of BCP and pairewise-consistency deductive power on problems with 20 variables

  BCP needs unit open clauses to deduce values. Pairewiseconsistency can deduce values when there are no unit open clauses.

Figure 4 .

 4 Figure 4. Comparison of BCP and pairewise-consistency deductive power on problems with 60 variables

The number of symbols in S wff is linear in F a , the total size of the formulae in the MTMS.

A literal l is associated to a wff f if l=σ , where σ is the symbol associated to f which is a positive wff, or if l=¬σ and σ is associated to ¬f, f being a negative wff.

The function CNconstraint(φ≡(l 1* l 2 )) returns in extension the definition of the constraint, i.e. the disjunctive normal form of the formula φ≡(l 1* l 2 ). In our case, all the constraints will have four tuples.

We obtain a so good complexity because there are no constraints larger than ternary. In this case, it is sufficient to create a variable for each couple of variables in a constraint, to add the correct values to these variables domains, to extend the existent constraints to these variables and to acheive arc-consistency; this provides the same result as pairewise-consistency on the original CN. The logarithm comes from an existence test when we create new variables.


Christian Bessière
email: bessiere@lirmm.fr

Arc-Consistency and Arc-Consistency Again * **

There is no need to show the importance of arc-consistency in Constraint Networks. Mohr and Henderson [9] have proposed AC-4, an algorithm with optimal worst-case time complexity. But it has two drawbacks: its space complexity and average time complexity. In problems with many solutions, where constraints are large, these drawbacks become so important that users often replace AC-4 by AC-3 [8], a non-optimal algorithm. In this paper, we propose a new algorithm, AC-6, which keeps the optimal worst-case time complexity of AC-4 while working out the drawback of space complexity. Moreover, the average time complexity of AC-6 is optimal for constraint networks where nothing is known about the constraint semantics.

Introduction

Constraint networks provide a useful way to formulate problems such as design, scene labeling, temporal reasoning, and more recently natural language parsing. The problem of the existence of solutions in a constraint network is NP-complete. Hence, consistency techniques have been widely studied to simplify constraint networks before or during the search for solutions. They can improve the efficiency of search procedures, but they are also useful in stand-alone implementations because they can yield solution sets or highly reduced problems [START_REF] Van Hentenryck | A generic arc-consistency algorithm and its specializations[END_REF]. Arc-consistency is the most commonly used consistency technique. Waltz [START_REF] Waltz | Understanding Line Drawings of Scenes with Shadows, The Psychology of Computer Vision[END_REF] developed arcconsistency for vision problems, it was subsequently studied by Mackworth and Freuder [START_REF] Mackworth | Consistency in Networks of Relations[END_REF] and [START_REF] Mackworth | The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems[END_REF], by Mohr and Henderson [START_REF] Mohr | Arc and Path Consistency Revisited[END_REF] who proposed an algorithm with optimal worst-case time complexity: O(ed 2 ), where e is the number of constraints (or relations) and d the size of the largest domain. In [START_REF] Bessière | Arc-Consistency in Dynamic Constraint Satisfaction Problems[END_REF] its use was extended to dynamic constraint networks. Recently, Van Hentenryck, Deville and Teng [START_REF] Deville | An Efficient Arc Consistency Algorithm for a Class of CSP Problems[END_REF] and [START_REF] Van Hentenryck | A generic arc-consistency algorithm and its specializations[END_REF], proposed a generic algorithm which can be implemented with all known techniques, and have extracted classes of networks in which there are algorithms that run arc-consistency in O(ed). In 1992, Perlin [START_REF] Perlin | Arc-consistency for factorable relations[END_REF] gave properties of arc-consistency for factorable relations.

Everyone now looks for arc-consistency complexity in particular classes of constraint networks since AC-4 [START_REF] Mohr | Arc and Path Consistency Revisited[END_REF] has optimal worst-case complexity and it is assumed that we cannot do better. AC-4 drawbacks are its average time complexity, which is too near the worst-case time complexity, and even moreso, its space complexity which is O(ed 2 ). In problems with many solutions, where arc-consistency removes few values, the AC-4 initialization step is long because whole relations must be considered to construct its data structure. In these cases, AC-3 [START_REF] Mackworth | The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems[END_REF] runs faster than AC-4 despite its non-optimal time complexity [START_REF] Wallace | Why AC-3 is Almost Always Better than AC-4 for Establishing Arc Consistency in CSPs[END_REF]. Moreover, in problems with a large number of values in variable domains and with weak constraints, AC-3 is often used instead of AC-4 because of its space complexity.

In this paper we propose a new algorithm, AC-6, which while keeping the O(ed 2 ) optimal worst-case time complexity of AC-4, discards the problem of space complexity (AC-6 space complexity is O(ed)) and checks just enough data in the constraints to compute the arc-consistent domain. AC-4 looks for all the reasons for a value to be in the arcconsistent domain: for each value, it checks all values compatible with it (called its supports) to prove this value is viable. AC-6 only looks for one reason per constraint to prove that a value is viable: for each value, it checks one support per constraint and looks for another one only when the current support is removed from the domain.

The rest of the paper is organized as follows. Section 2 gives some preliminary definitions on constraint networks and arc-consistency. Section 3 presents the algorithm AC-6. In section 4, experimental results show how much AC-6 outperforms algorithms AC-3 and AC-4 1 . Section 5 discusses the drawbacks of this new algorithm. A conclusion is given in Section 6.

Background

A network of binary constraints (CN) is defined as a set of n variables {i, j,…}, a domain D={D i , D j ,…} where D i is the finite set of possible values for variable i, and a set of binary constraints between variables. A binary constraint (or relation) R ij between variables i and j is a subset of the Cartesian product D i xD j that specifies the allowed pairs of values for i and j. Beginning with Montanari [START_REF] Montanari | Networks of Constraints: Fundamental Properties and Applications to Picture Processing[END_REF], a binary relation R ij between variables i and j is usually represented as a (0,1)-matrix (or a matrix of Booleans) with D i  rows and D j  columns by imposing an order on the variable domains. Value true at row a, column b, denoted R ij (a, b), means that the pair consisting of the ath element of D i and the bth element of D j is permitted; value false means the pair is not permitted. In all networks of interest here R ij (a, b)=R ji (b, a). In some applications (constraint logic programming, temporal reasoning,…), R ij is defined as an arithmetic relation (=, ≠, <, ≥,…) without giving the matrix of allowed and not allowed pairs of values. When the constraint is very weak, R ij can be defined by the set of forbidden combinations of values for i and j (called the negative form). In fact, R ij can be represented as any function such that R ij (a, b) returns true iff the pair (a, b) is allowed.

A graph G can be associated to a constraint network, where nodes correspond to variables in the CN and an edge links nodes i and j every time there is a relation R ij on variables i and j in the CN. For the purpose of this paper, we consider G as a symmetric directed graph with arcs (i, j) and (j, i) instead of the edge {i, j}.

A solution of a constraint network is an instanciation of the variables such that all constraints are satisfied.

Having the constraint R ij , value b in D j is called a support for value a in D i if the pair (a, b) is allowed by R ij . A value a for a variable i is viable if for every variable j such that R ij exists, a has a support in D j . The domain D of a CN is arc-consistent for this CN if for every variable i in the CN, all values in D i are viable. When a CN has a domain D, we call maximal arcconsistent domain of this CN domain D ', defined as the union of all domains included in D and arc-consistent for this CN. D' is also arcconsistent and is the domain expected to be computed by an arcconsistency algorithm.

Arc-consistency with unique support

Preamble

As Mohr and Henderson underlined in [START_REF] Mohr | Arc and Path Consistency Revisited[END_REF], arc-consistency is based on the notion of support. As long as a value a for a variable i (denoted (i, a)) has supporting values on each of the other variables j linked to i in the constraint graph, a is considered a viable value for i. But once there is a variable on which no remaining value satisfies the relation with (i, a), then a must be eliminated from D i .

The algorithm proposed in [START_REF] Mohr | Arc and Path Consistency Revisited[END_REF] makes this support evident by assigning a counter [(i, j), a] to each arc-value pair involving the arc (i, j) and the value a on the variable i. This counter records the number of supports of (i, a) in D j . For each value (j, b), a set S jb is constructed, where

S jb ={(i, a)/(j, b ) supports (i, a)}. Then, if (j, b) is eliminated from D j , counter[(i, j), a] must be decremented for each (i, a) in S jb .
This data structure is the origin of the AC-4 optimal worst-case time complexity. But computing the number of supports for each value (i, a) on each constraint R ij and recording all the values (i, a) supported by each value (j, b) implies an average time complexity and a space complexity both increasing with the number of allowed pairs in the relations since the number of supports is proportional to the number of allowed pairs in the relations. If the constraints are given in extension (e.g. matrices of Booleans), this space complexity (bounded by O(ed 2 ) with the size of the supports sets S jb ) is "only" proportional to the size of the problem. But in cases where constraints are defined by arithmetic relations, or given in negative form, the size of the AC-4 data structure may be dramatically larger than the size of the problem.

The purpose of AC-6 is then to avoid expensive checking and storage of all supports for all values. AC-6 keeps the same principle as AC-4, but instead of checking all supports for a value, it only checks one support (the first one) for each value (i, a) on each constraint R ij to prove that (i, a) is currently viable. When (j, b) is found as the smallest support of (i, a) on R ij , (i, a) is added to S jb , the list of values currently having (j, b) as smallest support. If (j, b) is removed from D j then AC-6 looks for the next support in D j for each value (i, a) in S jb . Using AC-6 only requires total ordering in all domains D j . But this is not a restriction since in any implementation total ordering is imposed on the domains. This ordering is independent of any ordering computed in a rearrangement strategy for searching solutions.

The algorithm

The algorithm proposed here works with the following data structure:

• A table M of Booleans keeps track of which values of the initial domain are in the current domain or not (M(i, a)=true ⇔ a∈D i ). In this table, each initial D i is considered as the integer range 1..D i . But it can be a set of values of any type with total ordering on these values. We use the following constant time functions and procedures to handle D i sets, which are considered as lists:

-last(D i ) returns the greatest value in D i if D i ≠ ∅, else returns 0.

-if a∈D i \last(D i ), next(a, D i ) returns the smallest value in D i greater than a.

-remove(a, D i ) removes the value a from D i .

• S jb ={(i, a)/(j, b) is the smallest value in D j supporting (i, a) on R ij } while in AC-4 it contains all values supported by (j, b).

• Counters for each arc-value pair in AC-4 are not used in AC-6.

• A Waiting-List contains values deleted from the domain but for which the propagation of the deletion has not yet been processed.

In AC-4, when a value (j, b) is deleted, it is added to the Waiting-List to await propagation of the consequences of its deletion. These consequences were to decrement counter[(i, j), a] for every (i, a) in S jb and to delete (i, a) when counter[(i, j), a] becomes zero. In AC-6, use of the Waiting-List is not changed but the consequence of (j, b) deletion is now to find another support for every (i, a) in S jb . With ordering on D j , after b (the old support) we look for another value c in D j supporting (i, a) on R ij (we know there is no such value before b). When such a value c is found, (i, a) is added to S jc since (j, c) is the new smallest support for (i, a) in D j . If no such value exists, (i, a) is deleted.

AC-6 uses the following procedure to find the smallest value in D j not smaller than b and supporting (i, a) on R ij : The algorithm AC-6 has the same framework as AC-4. In the initialization step, we look for a support for every value (i, a) on each constraint R ij to prove that (i, a) is viable. If there is a constraint R ij on which (i, a) has no support, it is removed from D i and put in the Waiting-List.

In the propagation step, values (j, b) are taken from the Waiting-List to propagate the consequences of their deletion: finding another support (j, c) for values (i, a) they were supporting (values (i, a) in S jb ). When such a value c in D j is not found, (i, a) is removed from D i and put in the Waiting-List at its turn.

Correctness of AC-6

Here are the key steps for complete proof of the correctness of AC-6. In this section we denote DmaxAC the maximal arc-consistent domain which is expected to be computed by an arc-consistency algorithm.

• In AC-6, value (i, a) is removed from D i only when it has no support in D j on a constraint R ij . If all previously removed values are out of DmaxAC, then (i, a) is out of DmaxAC. DmaxAC is trivially included in D when AC-6 is started. Then, by induction, (i, a) is out of DmaxAC. Thus, DmaxAC ⁄D is an invariable property of AC-6.

• Every time a value (j, b) is removed, it is put in the Waiting-List until the values it was supporting are checked for new supports. Every time a value (i, a) is found without support on a constraint, it is removed from D . Thus, every value (i, a) in D has at least one support in D∪Waiting-List on each constraint R ij . AC-6 terminates with an empty Waiting-List. Hence, after AC-6, every value in D has a support in D on each constraint. Thus, D is arc-consistent.

• DmaxAC ⁄D and D arc-consistent at the end of AC-6 implies that D is the maximal arc-consistent domain at the end of AC-6. ❏

Space and time complexity

The matrix M has a size proportional to the number of values in D, O(nd). Arc-value pairs [(i, j), a] have at most one support (j, b) with (i, a) belonging to S jb ; hence the total size of the S jb sets is at most equal to the number of arc-value pairs: O(ed). Therefore, the worst-case space complexity of AC-6 is O(ed) (instead of O(ed 2 ) for AC-4). Moreover, the counters of AC-4 are not used. In spite of their O(ed) space complexity, they are an expensive part of the AC-4 data structure. Needing a direct access, an implementation with arrays is necessary, taking space for 2ed counters, even if some of them will never be used.

In both the initialization step and the propagation step, the inner loop is a call to the procedure nextsupport which computes a support for a value on a constraint, starting at the current value. Hence, for each arcvalue pair [(i, j), a], each value in D j will be checked at most once. There are ed arc-value pairs, thus O(ed 2 ) is the worst-case time complexity for AC-6, as for AC-4. Furthermore, with no information on the constraint semantics, this algorithm is the best we can expect in time. It stops processing of a value just when it has proof that it is viable (i.e. the first support) 3 .

Experimental results

After producing an algorithm with just enough processing to ensure that each value is viable, we expect that it will outperform AC-3 and AC-4 on all problems.

We tested the performances of the three algorithms on a large spectrum of problems. For each problem, we counted the number of atomic operations and tests done by each algorithm (we counted one for each O(1) set of instructions). This measure is more precise than counting the number of constraint checks since it is directly proportional to running-time (while being independent of the implementation of the structures).

The first comparison was done on the zebra problem ( [START_REF] Dechter | Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition[END_REF] or [START_REF] Van Hentenryck | Constraint Satisfaction in Logic Programming[END_REF]) which has similarities with some real-life problems. With the representation of this problem given in [START_REF] Dechter | Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition[END_REF], we obtain the following results:

AC-3: 3692 AC-4: 3802 AC-6: 1995 In Fig. 1, we then compared the three algorithms on a problem often used for algorithm comparisons: the n-queens (i.e. a nxn chessboard on which we want to put n queens, none of them attacked by any other). We can encode it in a CN by representing each column by a variable whose values are the rows. The graph associated to the CN is complete, each pair {i, j} of variables being linked by a constraint that specifies the allowed positions for the two queens in columns i and j. This CN is very particular since it is extremely symmetrical and all the constraints are weak (note that arc-consistency does not discard any value in this CN).

Results obtained here cannot be generalized for other kinds of CNs. However, this CN is interesting to illustrate the behavior of algorithms in particular cases which can locally arise in a part of a CN. In these cases, AC-4 has a bad behavior while AC-3 and AC-6 have an O(ed) average time complexity. Finally, we defined classes of randomly generated constraint networks and showed in Fig. 2, 3 and 4 the behavior of the three algorithms on these different types of constraint networks. Four parameters were taken into account: n the number of variables, d the number of values per variable, pc the probability that a constraint R ij between two variables exists, and pu the probability in existing relations R ij that a pair of values R ij (a, b) is allowed. The result given for each class is the average of ten instances of problems in the class so as to be more representative of the class. Let's roughly summarize these results:

• AC-4 performances decrease when d or pu grow. The larger the domains and the weaker the constraints, the worse AC-4. When we take a look at these figures, AC-4 does not seem interesting. However, being good when arc-consistency discards many values, randomly generated CNs are not favourable to it. In practical cases, constraints are less homogeneous than in randomly generated CNs and AC-4 is better. Many applications, like SYNTHIA [START_REF] Janssen | SYNTHIA: Assisted Design of Peptide Synthesis Plans[END_REF] to design peptide synthesis plans, prefer AC-4 to AC-3.

• AC-3 is never very bad but it can check several times a pair of values because of its non-optimal time complexity. When propagation of deletions is long, in "middle" CNs (i.e. not too much constrained and not under-constrained), AC-3 becomes less efficient. However, CNs treated in practice are often "middle" CNs since under-constrained CNs and tooconstrained CNs are easy to solve, with solutions or contradictions found quickly.

• AC-6 has kept the optimal worst-case time complexity of AC-4 while working out the problem of considering whole relations . Hence, it is very good on CNs with weak constraints, as opposed to AC-4, and remains efficient on CNs where the constraints are tight or on "middle" CNs, as opposed to AC-3.

Discussion on the limitations of AC-6

In the above sections, we only considered constraint networks with arbitrary constraints. We said that AC-6 is optimal in time on these constraint networks. All experimental results presented in Section 4 use basic versions of the three algorithms AC-3, AC-4, and AC-6. But there are improved versions of AC-4 [START_REF] Mohr | Running efficiently arc consistency[END_REF] dealing with arithmetic relations (<, ≥, ≠, =, …) in O(ed). The generic algorithm AC-5 can be instanciated to produce efficient algorithms for a number of important classes of constraints: functional, anti-functional, monotonic… [START_REF] Van Hentenryck | A generic arc-consistency algorithm and its specializations[END_REF]. For all of these classes of constraints, the basic version of AC-6 is not optimal in time since the improved versions of AC-4 or AC-5 have a worst-case time complexity of O(ed). However, in many applications, functional constraints, arithmetic relations and other particular constraints are mixed with arbitrary constraints in the constraint network. In these cases, AC-6 provides a simple, general, and efficient algorithm, which deals well with every kind of constraint, avoiding ad hoc implementations or heavy data structures.

However, the main limitation of AC-6 is its theorical complexity when used in a backtracking search procedure. The really full look-ahead search procedure [START_REF] Nadel | Tree Search and Arc Consistency in Constraint Satisfaction Algorithms[END_REF] is a search procedure which computes arcconsistency at each step of the tree search (i.e. every time a value is chosen for a variable). Any arc-consistency algorithm can be taken to implement this procedure. When AC-4 is used, a heavy initialization phase is made at the root of the search tree, computing all sets of supports and counters for every value. But once this data structure is constructed, we can avoid a new expensive initialization phase at each step of the search, duplicating the data structure of the step before. We can still process in O(1) the direct consequence of the deletion of a support for a value (i.e. decrementing a counter). Using AC-6, the direct consequence of the deletion of a support for a value (i.e. checking the constraint to find the next support) will be processed in O(d). Hence, we think that we can find examples of constraint networks where a really full look-ahead procedure written with AC-6 has a worse behavior than one written with AC-4. In practice, on the RESYN application [START_REF] Vismara | RESYN: Un système d'aide à la conception de plans de synthèse en chimie organique[END_REF] where AC-4 has been replaced by AC-6 in the search procedure, the results are quite favourable to AC-6. But complete experimentation must be done on a large spectrum of problems. It should involve really full look-ahead implemented with AC-4 and AC-6, and other look-ahead search procedures like forward-checking [START_REF] Haralick | Increasing Tree Seach Efficiency for Constraint Satisfaction Problems[END_REF], which is often considered in the literature as being the best search procedure for constraint networks.

Conclusion

We have provided an algorithm, AC-6, to achieve arc-consistency in binary constraint networks. It keeps the O(ed 2 ) optimal worst-case time complexity of AC-4 while working out the two drawbacks of this algorithm: its space complexity (O(ed 2 )), and its average time complexity on constraint networks with weak constraints. AC-6 has an O(ed) space complexity and its running-time decreases as the weakness of the constraints grows. Experimental results are given, showing that AC-6 outperforms AC-3 and AC-4 (the two other best algorithms to achieve arcconsistency) on all the problems tested. However, its superiority on AC-4 when used in a search procedure requires further experimental proof.

  procedure nextsupport(in i, j, a : integer; in out b : integer; out emptysupport : boolean); begin if b ≤ last(D j ) then begin emptysupport ← false ; {search of the smallest value greater (or equal) than b that belongs to D j } while not M(j, b) do b ← b + 1 ; 2 {search of the smallest support for (i, a) in D j } while not R ij (a, b) and not emptysupport do if b < last(D j ) then b ← next(b, D j ) else emptysupport ← true end else emptysupport ← true end;

  {initialization} Waiting-List ← Empty-List ; for (i, a) ∈ D do S ia ← ∅ ; M(i, a) ← true ; for (i, j) ∈ arcs(G) do for a ∈ D i do begin b ← 1 ; nextsupport(i, j, a, b, emptysupport ) ; if emptysupport then remove(a, D i ) ; M(i, a) ← false ; Add-to(Waiting-List, (i, a)) else Add-to(S jb , (i, a)) end {propagation} while Waiting-List ≠ ∅ do begin pick (j, b) from Waiting-List ; for (i, a) ∈ S jb do {before its deletion (j, b) was the smallest begin support in D j for (i, a) on R ij } delete (i, a) from S jb ; if M(i, a) then begin c ← b ; nextsupport(i, j, a, c, emptysupport ) ; if emptysupport then remove(a, D i ) ; M(i, a) ← false ; Add-to(Waiting-List, (i, a)) else Add-to(S jc , (i, a)) end end end

Figure 1 .

 1 Figure 1. Comparison of AC-3, AC-4 and AC-6 on the n-queens problem

Figure 2 .Figure 3 .

 23 Figure 2. AC-3, AC-4 and AC-6 on randomly generated CNs with 20 variables having 5 possible values, where the probability pc to have a constraint between two variables is 30 %

Figure 4 .

 4 Figure 4. AC-3, AC-4 and AC-6 on randomly generated CNs with 18 variables having 9 possible values

,[START_REF] Van Hentenryck | A generic arc-consistency algorithm and its specializations[END_REF]) is not discussed in this section since it is not an improvement for arbitrary constraints. It is a generic framework in which all previous algorithms can be written and with which we can produce good algorithms for particular constraint classes.

To improve slightly AC-6, we can replace "b ← b + 1" by " b ← latest-next(j, b)" where latest-next(j, b) is the value b' that was equal to next(b, D j ) when b was removed from D j (if b was not last(D j )). This improvement is significant only with large domains.

The only possible improvements are variable ordering heuristics[START_REF] Wallace | Ordering Heuristics for Arc Consistency Algorithms[END_REF].

Acknowledgments

I would particularly like to thank Marie-Odile Cordier, without our discussions this paper would not have been written. I also thank Amit Bellicha and Jean-Charles Régin for their useful comments on earlier drafts, and the anonymous AI Journal reviewers for their suggestions.

* This paper is a revised version of [2]. ** This work was partially supported by the CSPFlex and the BAHIA projects of the PRC-GDR IA (CNRS).