The arti cial intelligence (AI) is one of the powerful research area. AI gathers several topics such as Constraint Programming CP, Machine Learning ML, and Multi-Agent System MAS. Our contribution is inspired by these last AI topics: CP, ML and MAS. We therefore consider Distributed Constraint Satisfaction Problem formalism DisCSP, which is a Constraint Programming problem, distributed among several autonomous agents in a MAS system. To solve such problems, many algorithms are proposed in the literature. Most of them, rely on message exchanging to nd a global solution that satis es the set of constraints of each agent. Generally, two types of messages are used, the rst type is used by each agent to inform others of its chosen value, and the second type (nogood) is used by the same agent to inform others that their choices had blocked it. The Machine Learning principle is used by launching asynchronously two DisCSP algorithms in the same DisCSP problem and sharing the nogoods of the two algorithms. Experimental results exhibit that each algorithm learns from the nogoods of the other algorithm.
In recent years, ones of the most used areas in the arti cial
intelligence are i) the constraint programming[
DisCSP can represent several real distributed problems, As
distributed Meeting Scheduling[
While there are several DisCSP algorithms, as ABT[
The idea is to use the machine learning principle, which is adapted to big data, in the existing algorithms. In our contribution we use the two algorithms ABT and AFC-ng.
We will not designate, statically, which is the training algorithm and which is the testing one . The choice will be done dynamically and intelligently during the resolution process. At a given point, the fast algorithm which nds a failure the rst will be the training one and the other the testing one. This a ectaion of rules is not de nitive, it can be changed during the resolution process. The contribution details will be described more accuratly in the paper.
The paper proceeds as follows: the section 2 contains some useful de nitions. The detailed description of the two used algorithms (ABT and AFC-ng) will be done in section 3. Then, the main contribution is presented in section 4. And section 5 will show the experimental results. Finally we resume by a conclusion in section 6. 2
We recall brie y some fundamental de nitions in the context of constraint programming domain.
De nition 2.1 (MAS). A Multi-Agent System is a set of autonomous agents, interconnected via certain relations. These agents share a problem and try to solve it collectively.
De nition 2.2 (CSP). a CSP (Constraint Satisfaction Problem) is a mathematical problem, comprised of a set of Variables V, de ned in a set of Domains D and should satisfy a set of Constraints C.
De nition 2.3 (DisCSP). A DisCSP (Distributed CSP) is a CSP whose components (variables, domains, and constraints) are distributed among several agents (a MAS). So it is formalized as a set of Agents A, the same three CSP parameters V, D and C and a function that associates each variable to an agent.
De nition 2.4 (Solution). A solution is an assignment of all variables with values from its domains, so as the existing constraints are satis ed.
De nition 2.5 (Nogood). A nogood is a partial a ectation that can not be extended to a solution. In DisCSP algorithms, the nogood takes the form xi = i ^ xj = j ^ ... ! xk = k which means that as long as xi has the value i and xj has the value j , xk can not take the value k . The part which exist before the ! symbol is called the left-hand-side (lhs) and the other is called the right-hand-side (rhs).
De nition 2.6 (Conccurent Constraint Checks CCCs). The Concurrent Constraint Checks is a metric used to evaluate the DisCSP algorithms. It computes the number of the constraints checked concurrently. Each agent handles a constraint counter. Each message sent carries this value. The receiver tests if the received value is greater than the value of its counter. If so, it updates its own counter by the received one. When the resolution is over. The largest counter value is selected as the Concurrent Constraint Checks value. 3 3.1
The Asynchronous Backtracking is a DisCSP algorithm which allows agents to solve the problem asynchronously. The order priority of agents is made statically and lexicographically (Ai is a higher priority than Aj when i<j). The algorithm 1 exhibits the di erent procedures and functions used by an ABT agent to nd a solution.
Each agent self has an AgentView structure, to save the assignments of higher priority agents than self, and a NogoodStore structure to store the nogoods sent by the lower priority agents to self.
When the ABT protocol starts running, each agent chooses an assignment to its local variables, creates an OK message that carries its choice and sends it to the lower priority agents.
Algorithm 1 ABT algorithm 1: procedure ABT myvalue 2: CheckAgentView(); 3: while ¬end do 4: msg getMsg(); 5: Switch (msg.type) 6: Ok? : ProcessInfo(ms ); 7: ngd : ResolveCon ictm(s ); 8: stp : end t r ue; 9: adl : SetLink(ms ); 10: end while 11: end procedure empty;end false; 12: procedure C A V (ms ) 13: if ¬consist ent (m V alue; m A entV iew ) then 14: m V alue ChooseV alue(); 15: if myValue then 16: for each child 2 +(sel f ) do 17: sendMsg : Ok? (child, myValue); 18: end for 19: else Backtrack(); 20: end if 21: end if 22: end procedure 23: procedure P I (ms ) 24: Update(myAgentView, msg.Assig); 25: CheckAgentView(); 26: end procedure 27: procedure R C (ms ) 28: if Coherent(ms .N o ood, (sel f ) [ { sel f }) then 29: CheckAddLink(msg); 30: add(msg.Nogood,myNogoodStore); 31: m V alue empt ; 32: CheckAgentView(); 33: elseif msg.sender 2 +(sel f ) ^ Coherent(msg.Nogood, self) then 34: SendMsg : Ok? (msg.Sender, myValue); 35: end if 36: end procedure 37: procedure S L (ms ) 38: add(msg.sender, +(sel f )); 39: sendMsg:ok?(msg.sender, myValue); 40: end procedure 41: procedure C A L (msg) 42: for each ar 2 lhs(msg.Nogood) do 43: if ar < (sel f ) then 44: sendMsg:adl( ar ,self); 45: add( ar , (sel f ) 46: Update (myAgentView, ar 47: end if 48: end for 49: end procedure 50: procedure B 51: new N o ood sol e(m N o oodSt or e); 52: if new N o ood = empt then 53: end t r ue; 54: sendMsg:stp(system); 55: else 56: sendMsg:ngd(newNogood); 57: Update (myAgentView, rhs(newNogood) 58: CheckAgentView(); 59: end if 60: end procedure varValue); unknown); 61: function V () 62: for each 2 D(sel f ) not eliminated by m N o oodSt or e do 63: if consistent( ,m A entV iew ) then return (v); 64: else 65: 66: 67: end if 68: end forreturn (empt ) 69: end function add(xj = alj ! sel f , , myNogoodStore); . is inconsistent with xj ’s value 70: procedure U (m A entV iew , new Assi ) 71: add(newAssig, myAgentView); 72: for each n 2 m N o oodSt or e do 73: if ¬Coher ent (lhs(n ), m A entV iew ) then 74: remove(ng, myNogoodStore); 75: end if 76: end for 77: end procedure 78: procedure C (no ood , a ent s) 79: for each ar 2 no ood [ a ent s do 80: if no ood [ ar ] , m A entV iew [ ar ] then
return false; 81: end if 82: end for
return true; 83: end procedure
After receiving the OK message, the receiver updates its AgentView with the new received values and checks if its assignment is still consistent with the content of its updated AgentView.
De nition 3.1 (Consistent). An assignment is consistent with other assignments if all the constraints that link this assignment with the others are satis ed.
If this is not the case, it browses its domain, in order to nd an a ectation which satis es the consistency condition.
For each tested value, if it does not satisfy a certain number of constraints with some values from the Agentview, a nogood is created and stored in the NogoodStore. This nogood contains in its lhs the values which block the current tested value and the checked value in its rhs. The nogood is used as a justi cation of why the tested value is not chosen.
If the whole domain is scanned without nding any consistent value, the agent generates a nogood from the stored nogoods (justications). The rhs of the resultant nogood is the value of the lowest priority agent, and the others values are put into the lhs. The agent self sends this nogood to the lowest priority agent (whose value exists in the rhs). This nogood is used to say to the receiver that as long as the other agents have the values that exist in the lhs, you should change this value which is in the rhs.
The receiver stores the nogood in its nogoodStore, and tries to nd a new consistent value which is not removed by one of the stored nogoods in the NogoodStore, taking into account (as after receiving an OK message) the AgentView values. In the same way as the OK message, if the agent nds the good assignment it sends it via an OK message, otherwise, it sends a nogood message. Without having forgotten that: after receiving a new OK message, even the nogoodStore is updated, by removing the obsolete nogoods (whose lhs contains, at least, a di erent value that becomes di erent).
A solution is found when a silence is detected. If a null nogood message is generated by the highest priority agent the problem is unsolvable. 3.2
As ABT, AFC-ng (nogood based Asynchronous Foward Checking)
[
The synchronous part of AFC-ng is seen when agents try to assign its variables. At one point, just a single agent can a ect its variables, it is the one that receives the CPA message (for Current Partial Assignment). It is a data structure which represents the research process state and contains a partial assignment of the DisCSP problem variables, so that each agent tries to extend, until it contains the assignments of all existing variables (all agents), so as the constraints are satis ed. And the asynchronous part is highlighted when an agent spreads its value choices to the lower priority agents. The receivers revise its domains asynchronously.
The algorithm 2 shows the AFC-ng resolution stages. When the protocol starts, it is the highest priority agent which generates the CPA structure, puts in its instantiation and sends it to lower priority agents via CPA message.
Algorithm 2 AFC-ng algorithm 1: procedure AFC 2: end false; AgentView.Consistent 3: if Ai = IA then 4: Assign(); 5: end if 6: while ¬end do 7: msg getMsg(); 8: Switch (msg.type) do 9: cpa : ProcessCPA(ms ); 10: ngd : ProcessNogood(ms ); 11: stp : end t r ue; 12: end while 13: end procedure 55: procedure B 56: n d sol e(m N o oodSt or e); 57: if n d = empt then 58: Report F AI LU RE; 59: end t r ue; 60: 61: 62: 63: 64: 65: else . Let xj denote the variable in rhs(ng) for k =j+1 to i-1 do
AgentView[k].value empty; end for for each (nogood 2 NogoodStore) do
if (¬Compatible(nogood,AgentView) _ xj 2 no ood ) then 66: remove (nogood, NogoodStore); 67: end if 68: end for 69: AgentView.Consistent false; 70: i empt ; 71: sendMsg:ngd(ng) to Aj ; 72: end if 73: end procedure 74: procedure P N (ms ) 75: if Compatible( msg.nogood, AgentView ) then 76: add(msg.nogood,NogoodStore); 77: . according to the HPLV [] 78: if (rhs(msg.nogood).value = i ) then 79: i empt ; 80: Assign(); 81: end if 82: end if 83: end procedure 84: procedure U A V (CPA) 85: AgentView CPA; 86: for each (ng 2 NogoodStore) do 87: if ¬ Compatible(ng, AgentView) then 88: remove(ng, myNogoodStore); 89: end if 90: end for 91: end procedure 92: procedure R 93: for each ( 2 D0(xi )) do 94: if is ruled out by A entV iew ) then 95: Store the best nogood for ; 96: 97: end if 98: end for 99: end procedure . update values and tags . according to the HPLV
Each receiver checks if the received message is up to date (using a counter for each agent). If so, it updates its AgentView and NogoodStore. It replaces the AgentView by the received CPA and removes the obsolete nogoods that exists in the NogoodStore. Then it revises its domain, by adding a justifying nogood, for each inconsistent value. After which, it checks if the domain becomes empty, if yes, it generates a nogood (as ABT) and sends it to the lowest priority agent. Otherwise, if it is the predecessor of the sender, it chooses a value for its variable (the value that is not eliminated by a nogood) , adds it to the CPA and propagates the message to the lower priority agents.
The nogood message is treated in the same way as in the ABT nogood.
The end of protocol can be detected without using another external algorithm. A solution is found when the lowest priority agent adds its assignment to the CPA (the size of the CPA structure is equal to the number of agents). The insolvency is detected by one of the existing agents. When its domain becomes empty and there is no nogood justifying this failure, it stops the resolution, declaring that the problem is insolvable. 4
The subsections 3.1 and 3.2 show that there are several common features between ABT and AFC-ng including: (1) The NogoodStore content: the two algorithms have the same NogoodStore structure with the same contents; (2) The AgentView content: : the two algorithms have the same AgentView structure. Even if the AFC-ng AgentView contains the counters (the ABT does not use the counters), but it also contains the higher priority agent assignments as it is done by the ABT AgentView; (3) The nogood stucture: the two nogoods are generated in the same way.
These common points are the basis to launch the two algorithms in the same DisCSP problem, in order to collaborate with each other and nd the solution, either with less message exchanged and fewer tested constraints or else In a minimum of time.
In order to ensure this, we did it in two di erent ways: 4.1
In the rst method, the two algorithms are launched at the same time. All agents launch the ABT algorithm and just the initial agent which starts the AFC-ng algorithm.
In addition to stp message, each agent can receive and send four other types of messages: CPA, ngd_AFCng (nogood message sent using AFCng algorithm), Ok?, ngd_ABT (nogood message sent using ABT algorithm) and stp message.
For each received message the associated procedure is applied as the original algorithm.
The algorithm 3 shows only the procedures and functions that have been changed.
In addition to their structures AgentView_ABT, AgentView_AFCng, NogoodStore_ABT and NogoodStore_AFCng, each agent creates two new structures SentNogoodsByABT to store the nogoods sent by ABT algorithm and SentNogoodsByAFCng which will contain the nogoods sent by AFCng.
Then, when an agent creates and sends a new nogood by ABT(backtrack_ABT procedure), it stores it in the new structure SentNogoodsByABT.
The same thing when it generates a new nogood using AFC_ng (backtrack_AFCng procedure), it stores it in the SentNogoodsByAFCng structure. Algorithm 3 Learning-1 1: procedure ABT AFC 1 2: end false; AgentView_AFCng.Consistent 3: if Ai = IA then 4: Assign(); 5: end if 6: CheckAgentView(); 7: while ¬end do 8: msg getMsg(); 9: Switch (msg.type) do 10: cpa : ProcessCPA(ms ); 11: ngd_AFCng : ProcessNogood(ms ); 12: Ok? : ProcessInfo(ms ); 13: ngd_ABT : ResolveCon ictm(s ); 14: stp : end t r ue; 15: end while 16: end procedure 17: procedure B _AFC 18: n d sol e(m N o oodSt or e); 19: if n d = empt then 20: The same AFC-ng Treatment; 21: else 22: 23: The same AFC-ng Treatment; 24: add(ngd, SentNogoodsByAFCng); 25: end if 26: end procedure 27: procedure B _ABT 28: new N o ood sol e(m N o oodSt or e); 29: if new N o ood = empt then 30: the same ABT treatment; 31: else 32: the same ABT treatment; 33: add(newNogood, SentNogoodsByABT) 34: end if 35: end procedure add(xj = alj ! sel f , , NogoodStore_ABT);
. is inconsistent with xj ’s value else 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: end if 78: end for 79: end procedure 59: procedure R 60: for each ngd 2 SentNogoodsByABT do 61: if (istheAgentViewAlreadyInconsistent(ngd) then 62: for each ( 2 D(sel f )) do 63: ngd ngd.lhs^ ngd.rhs! xi = ; 64: if is eliminated by nogoodStore_AFCng then 65: keep the best nogood between the eliminating nogood and ngd;
. According to the HPLV add (ngd, nogoodStore_AFCng; end if end forreturn null; end if end for for each ( 2 D0(xi )) do
if ( is ruled out by A entV iew or eliminated by no oodSt or e_ABT ) then
Store the best nogood for ;
. according to the HPLV[
So, When an agent tries to choose a value using the ABT or revise the domain using the AFC-ng algorithm (ChooseValue_ABT(), Revise()). Firstly, it checks if there is a sent nogood in the other algorithm and the whole elements of the latter exist in the AgentView of the current algorithm.
If so, ChooseValue_ABT procedure clears the NogoodStore_ABT, generates a new nogood whose lhs is the nogood components (lhs and rhs), browses the whole domain, completes the nogood rhs by the current tested value and adds it to the current algorithm NogoodStore (NogoodStore_ABT). Then it return null, saying that there is no consistent value, without testing the constraints, because it is already tested by the other algorithm (AFCng).
After this, if there is no nogood sent by the other algorithm, the procedure continue its treatments. It browses the domain, value by value, tests if the value tested is not eliminated by the ABT NogoodStore (NogoodStore_ABT) (the same as ABT ChooseValue procedue without sharing nogoods), if so, it checks if there is a nogood in the other nogoodStore (NogoodStore_AFCng) which is compatible with the AgentView_ABT and eliminates the tested value. If so, it adds the found nogood in the NogoodStore_ABT. Otherwise, it tests if the value is consistent with AgentView_ABT, if so, it returns the value, otherwise, it adds the justifying nogood.
For the Revise() method, it tests if there is a nogood which exists in the SentNogoodByABT structure and which is coherent with the AgentView_AFCng.
If so, it browses the domain, in order the construct a new nogood whose the lhs is the lhs and rhs conjunction of the found nogood and the rhs is the tested value. If the tested value is already removed by a nogood (in NogoodStore_AFCng), it keeps the better nogood (the constructed nogood or the found nogood), according to the HPLV method. Otherwise, it adds the generated nogood to the NogoodStore_AFCng.
ABT AFC-ng Learning-1
Learning-2 ABTAFC-ng_Learning-1
ABT AFC-ng Learning-1
Learning-2
ABTAFC-ng_Learning-1 If there is no sent nogood by the ABT algorithm, the Revise() procedure browses the domain. It checks not only if the value is inconsistent with the AgentView_AFCng but also if the value is eliminated by nogoodStore_ABT, if so, it keeps the best nogood using the HPLV method. 4.2
The second method follows the same methodology as the rst. The only di erence is highlighted when the ABT or AFC-ng algorithm generates a no empty nogood. Before sending it and adding it into SentNogoods structures (SentNogoodsByABT and SentNogoodsByAFCng), it should check if the generated nogood is not already sent by the other algorithm.
So, if an algorithm nds that its new generated nogood is already sent by the other algorithm, it stops the resolution and the other continues its resolution process. 5
In this section, we compare the algorithms ABT and AFC-ng with the two learning methods (Learning-1 and Learning-2) and also with ABT/AFC-ng_Learning-1 (i.e. taking into account just the fast algorithm which nds the solution the rst, using the Learning-1 method).
The assessment is made against the number of exchanged
messages (# MSGs) and the Concurrent Constraint Checks (# CCCs),
using disChoco platform [
We experiment the ve algorithms in random problems. The problems are characterized by the parameters (n, d, p1, p2) where, n is the number of agents, d is the domain size, p1 is the problem density and p2 is the tightness of constraints.
Algorithm 4 Learning-2 1: procedure B _AFC 2: n d sol e(m N o oodSt or e); 3: if n d = empt then 4: The same AFC-ng Treatment; 5: else 6: if ¬ SentNogoodsByABT contains ngd then 7: The same AFC-ng Treatment; 8: add(ngd, SentNogoodsByAFCng); 9: end if 10: end if 11: end procedure 12: procedure B _ABT 13: new N o ood sol e(m N o oodSt or e); 14: if new N o ood = empt then 15: the same ABT treatment; 16: else 17: if ¬ SentNogoodsByAFCng contains ngd then 18: the same ABT treatment; 19: add(newNogood, SentNogoodsByABT) 20: end if 21: end if 22: end procedure
The ABT/AFC-ng_Learning-1 algorithm is obtained by using the Learning-1 method with the ABT and AFC-ng algorithms and computing just the number of MSGs and CCCs in ABT for ABT_Learning1 and in AFC-ng for the AFC-ng_Learning-1 algorithm, and keep the results of the fast one.
All generated problems have n = 20 and d =. We evaluate the algorithms into two types of problems. With low density value p1 = 0.2 and with high density value p1 = 0.7.For the two kinds of problems, we variate the tightness p2 from 0.1 to 0.9 by 0.05 as a step.
Figure 1 shows the number of exchanged messages and Conccurent Constraint Checks by the ve methods, for sparse graphs (20, 10, 0.2,p2). The experimentation results show that Learning-1 and Learning-2 methods are between ABT and AFC-ng, knowing that we compute the number of exchanged message by the two algorithms ABT and AFC-ng, even if, is just one of its which nds the solution (or detect the insolvability). These results show that we could learn the informations between the algorithms, because otherwise, if we do not any nogood learning, the number of exchanged messages will be the sum of the two algorithms, which will be very large, so as the ABT and AFC exchanged message numbers will be Negligible in front of the sum.
For CCCs, we are at least like the better of them.
So when we compute the number of exchanged messages by only the algorithm which nds the solution the rst (because it can be nd by the ABT or the AFC-ng, according to the most fast algorithm), we obtain very important results. The ABT/AFCng_Learning1 exchanges less messages and tests less constraints concurrently. s G S M 2 3 2 1 0 the participant algorithms. Assessments prove that, by learning nogoods, we save exchanged messages and tested constraints.
The results give us the idea, for the future work, to launch the rst algorithm (ABT, AFC-ng or another DisCSP algorithm), save the nogoods and recuperate the results. Then run the second algorithm, learning from the saved nogoods. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
The choice of computing the MSGs and CCCs of only the algorithm which nds the solution is not obsolete. Because, the machine learning principle is serving to store the exchanged nogood messages following each resolution (by an algorithm). And then use the stored messages, to learn and resolve the DisCSP fast. In this case we will not compute the number of MSGS or CCCs of the training step, because it is already done.
The second gure shows the evaluation results (number of MSGs, gure, and CCCs) for dense graphs (20, 10, 0.7, p2). As the previous it represents the performance of the ve algorithms, forp2, ranging from 0.1 to 0.9, except the Learning-2 method which we evaluate just for 0.1 to 0.25. The latter is better than the ABT, AFC-ng and the Learning-1 methods, because, when an algorithm nds that the other has already send the same nogood message, it stops the resolutions.
This is feasible, when problems are simple, but for complex problems, it is less likely, to nd the same nogood with the two algorithms. The Learning-1 is so the more useful.
The results make clear that the Learning (Learning-1 or Learning2) saves us the exchanged messages and the tested constraints, even if we compute the used resources by the two algorithms. The importance of learning becomes more legible, when we plot the ABT/AFC-ng_Learning-2. 6
In this paper, we have proposed two methods Learning-1 and Learning-2, that allow to at least two DisCSP algorithms at the same DisCSP problem, and share the nogoods content between