We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
THE IMPACT OF THE CONFLICT ON SOLVING DISTRIBUTED CONSTRAINT SATISFACTION PROBLEMS.
- Authors
HOSSEINI, Samaneh; ZAMANIFAR, Kamran
- Abstract
Distributed Constraint Satisfaction Problems (DCSPs) involve a vast number of AI and Multi-Agent problems. Many important efforts have been recently accomplished for solving these kinds of problems using both backtracking-based and mediation-based methods. One of the most successful mediation based algorithms in this field is Asynchronous Partial Overlay (APO) algorithm. By choosing some agents as mediators, APO tries to centralize portions of the distributed problem, and then each mediator tries to solve its centralized sub-problem. This work continues until the whole problem is solved. This paper presents a new strategy to select mediators. The main idea behind this strategy is that the number of mediators conflicts (violated constraints) impacts directly on its performance. Experimental results show that choosing the mediators with the most number of conflicts not only leads to considerable decrease in APO complexity, but also it can decrease the complexity of the other extensions of the APO such as IAPO algorithm. MaxCAPO and MaxCIAPO are two new expansions of APO which introduce this idea and are presented in this article. The results of using this mediator selection strategy show a rapid and desirable improvement over various parameters in comparison with APO and IAPO.
- Subjects
CONSTRAINT satisfaction; ARTIFICIAL intelligence; ASYNCHRONOUS transfer mode; MULTIAGENT systems; INTELLIGENT agents; COMPUTER algorithms
- Publication
Computing & Informatics, 2009, Vol 28, Issue 5, p673
- ISSN
1335-9150
- Publication type
Article