Nogood Learning in DisCSP Algorithms Ghizlane EL KHATTABI Imade BENELALLAM El Houssine BOUYAKHF LIMIARF Laboratory SI2M Laboratory LIMIARF Laboratory Rabat, Morocco Rabat, Morocco Rabat, Morocco elkhattabi.ghizlane@gmail.com imade.benelallam@ieee.org bouyakhf@mtds.com ABSTRACT DisCSP can represent several real distributed problems, As dis- The arti�cial intelligence (AI) is one of the powerful research area. tributed Meeting Scheduling[9, 14], Distributed Resource Allocation AI gathers several topics such as Constraint Programming CP, Ma- Problem[11] and Sensor Networks[2, 8]. These problems, includ- chine Learning ML, and Multi-Agent System MAS. Our contribution ing big problems, require more treatment. So, we have to think to is inspired by these last AI topics: CP, ML and MAS. We therefore reduce the treatments, when using DisCSPs algorithms. consider Distributed Constraint Satisfaction Problem formalism While there are several DisCSP algorithms, as ABT[5], AFC[10], DisCSP, which is a Constraint Programming problem, distributed AFC-ng[13] and AWC[15]. We do not have to create new algorithms, among several autonomous agents in a MAS system. To solve such to solve the very big DisCSP problems. problems, many algorithms are proposed in the literature. Most of The idea is to use the machine learning principle, which is them, rely on message exchanging to �nd a global solution that adapted to big data, in the existing algorithms. In our contribu- satis�es the set of constraints of each agent. Generally, two types of tion we use the two algorithms ABT and AFC-ng. messages are used, the �rst type is used by each agent to inform oth- We will not designate, statically, which is the training algorithm ers of its chosen value, and the second type (nogood) is used by the and which is the testing one . The choice will be done dynamically same agent to inform others that their choices had blocked it. The and intelligently during the resolution process. At a given point, Machine Learning principle is used by launching asynchronously the fast algorithm which �nds a failure the �rst will be the training two DisCSP algorithms in the same DisCSP problem and sharing one and the other the testing one. This a�ectaion of rules is not the nogoods of the two algorithms. Experimental results exhibit de�nitive, it can be changed during the resolution process. The that each algorithm learns from the nogoods of the other algorithm. contribution details will be described more accuratly in the paper. The paper proceeds as follows: the section 2 contains some use- KEYWORDS ful de�nitions. The detailed description of the two used algorithms (ABT and AFC-ng) will be done in section 3. Then, the main con- Multi Agent System, Arti�cial Intelligence, algorithms, nogoods, tribution is presented in section 4. And section 5 will show the Distributed Constraint Problem experimental results. Finally we resume by a conclusion in section ACM Reference Format: 6. Ghizlane EL KHATTABI, Imade BENELALLAM, and El Houssine BOUYAKHF. 1997. Nogood Learning in DisCSP Algorithms. In Proceedings of Interna- 2 SOME DEFINITIONS tional Conference on Applied Research in Computer Science and Engineering (ICAR’17). ACM, New York, NY, USA, 7 pages. https://doi.org/10.475/123_4 We recall brie�y some fundamental de�nitions in the context of constraint programming domain. 1 INTRODUCTION De�nition 2.1 (MAS). A Multi-Agent System is a set of autonomous In recent years, ones of the most used areas in the arti�cial intel- agents, interconnected via certain relations. These agents share a ligence are i) the constraint programming[12], which allows to problem and try to solve it collectively. present and solve combinatorial real problems, such as scheduling De�nition 2.2 (CSP). a CSP (Constraint Satisfaction Problem) is and plani�cation problems, ii) Multi-agent system[6], that repre- a mathematical problem, comprised of a set of Variables V, de�ned sent a set of agents (or a set of computer systems) that colaborate in a set of Domains D and should satisfy a set of Constraints C. in order to do a set of tasks, independently of humans. The two latter domains have been used to create another subdomain DisCSP De�nition 2.3 (DisCSP). A DisCSP (Distributed CSP) is a CSP (for Distributed Constraint Problems)[16], that is a mathematical whose components (variables, domains, and constraints) are dis- problem, distributed among several autonomous agents, aiming to tributed among several agents (a MAS). So it is formalized as a solve the problem together. And iii) the Machine Learning[1] that set of Agents A, the same three CSP parameters V, D and C and a appeared a long time ago, but takes the hard meaning recently by function that associates each variable to an agent. the big data arrival. It bases on examples to learn new techniques. De�nition 2.4 (Solution). A solution is an assignment of all vari- ables 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 x i = i ^ x j = j ^ ... ! x k = k which means that as long as x i has the value i and x j has the value j , x k can not take the value k . The part which exist before the ! symbol is called ICAR’17, June 22 - 23, Hadat-Baabda, Lebanon Ghizlane EL KHATTABI, Imade BENELALLAM, and El Houssine BOUYAKHF the left-hand-side (lhs) and the other is called the right-hand-side 27: procedure R������C�������(ms ) (rhs). 28: if Coherent(ms .N o ood, (sel f ) [ {sel f }) then 29: CheckAddLink(msg); De�nition 2.6 (Conccurent Constraint Checks CCCs). The Con- 30: add(msg.Nogood,myNogoodStore); current Constraint Checks is a metric used to evaluate the DisCSP 31: m V alue empt ; algorithms. It computes the number of the constraints checked con- 32: CheckAgentView(); currently. Each agent handles a constraint counter. Each message 33: elseif msg.sender 2 + (sel f ) ^ Coherent(msg.Nogood, self) then sent carries this value. The receiver tests if the received value is 34: SendMsg : Ok? (msg.Sender, myValue); 35: end if greater than the value of its counter. If so, it updates its own counter 36: end procedure by the received one. When the resolution is over. The largest counter value is selected as the Concurrent Constraint Checks value. 37: procedure S��L���(ms ) 38: add(msg.sender, + (sel f )); 3 THE PRINCIPLE DISCSP ALGORITHMS 39: sendMsg:ok?(msg.sender, myValue); 40: end procedure 3.1 Asynchronous BackTracking ABT 41: procedure C����A��L���(msg) The Asynchronous Backtracking is a DisCSP algorithm which al- 42: for each ar 2 lhs(msg.Nogood) do lows agents to solve the problem asynchronously. The order priority 43: if ar < (sel f ) then of agents is made statically and lexicographically (Ai is a higher 44: sendMsg:adl( ar ,self); priority than A j when i