Title: Dynamic vs. static agent ordering in distributed arc consistency
Authors: Saida Hammoujan; Imade Benelallam; El Houssine Bouyakhf
Addresses: LIMIARF/FSR, Mohammed V University, 4 Av. Ibn Battouta, B.P. 1014 RP, Rabat, Morocco ' National Institute of Statistics and Applied Economics, B.P. 6217, Madinat Al Irfane, Rabat Instituts, Morocco ' LIMIARF/FSR, Mohammed V University, 4 Av. Ibn Battouta, B.P. 1014 RP, Rabat, Morocco
Abstract: Recently, many approaches were proposed for solving distributed constraint satisfaction problems (DisCSPs). One of these approaches, we cite asynchronous maintenance of arc consistency (AMAC) that it has proven to be an efficient algorithm. AMAC algorithm performs an asynchronous arc consistency process during sequential search. In this paper, we propose two new approaches based on AMAC. However, instead of using a lexicographic ordering as a static agent/variable ordering, we present two asynchronous algorithms that exploit the structure of the DisCSPs by the use of powerful agent/variable ordering heuristics and enforce arc-consistency during resolution. The first algorithm we propose, AMAC_DO, uses dynamic variable ordering heuristics that are very useful in centralised CSPs. The second algorithm, ILAAC, is based on the split of the problem into several sub-problems using the pseudo-tree structure of the constraint graph. We offer an analysis and interpretation of experimental evaluation of the proposed approaches. The experimental results show clearly the usefulness of arc consistency process combined with variable ordering heuristics for random problems in terms of communication cost and computation effort.
Keywords: distributed constraint satisfaction problems; DisCSPs; arc consistency; variable ordering heuristics; pseudo-tree.
International Journal of Advanced Intelligence Paradigms, 2018 Vol.10 No.3, pp.266 - 289
Received: 28 Apr 2015
Accepted: 15 Nov 2015
Published online: 28 Mar 2018 *