Dynamic vs. static agent ordering in distributed arc consistency
by Saida Hammoujan; Imade Benelallam; El Houssine Bouyakhf
International Journal of Advanced Intelligence Paradigms (IJAIP), Vol. 10, No. 3, 2018

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.

Online publication date: Wed, 28-Mar-2018

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Advanced Intelligence Paradigms (IJAIP):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com