MaxCAPO: A New Expansion of APO to Solve Distributed Constraint Satisfaction Problems

S.H. Semnani and K. Zamanifar (Iran)


Distributed Constraint Satisfaction, APO, cooperative mediation, multi-agent


Distributed Constraint Satisfaction Problems (DCSPs) involve a vast number of AI and Multi-Agent problems. Many important efforts have been recently accomplished to solve these kinds of problems using both backtracking based and mediation based methods. One of the most successful algorithms in this field is Asynchronous Partial Overlay (APO). By choosing some agents as mediators, APO tries to centralize portions of the distributed problem. Each mediator tries to solve its centralized sub problem. This paper presents a new strategy for selecting mediators. The main idea behind this strategy is that the number of a mediator’s conflicts (violated constraints) impacts directly on its performance. Experimental results show that choosing a mediator with the most conflicts leads to a considerable decrease in APO complexity. The results show a rapid and desirable improvement over various parameters in comparison with APO.

Important Links:

Go Back