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.

DOI: 10.1504/IJAIP.2018.090790

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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article