The power of ants in solving Distributed Constraint Satisfaction Problems

Distributed Constraint Satisfaction (DCSP) has long been considered an important area of research for artificial intelligence and multi-agent systems. Also, Ant Colony Optimization (ACO) is an important evolutionary method for solving various optimization problems. This paper demonstrates the power of ants in solving DCSPs and describes a new approach for such a solution, showing how it differs from previous ACO-based DCSP solvers. The presented algorithm is designed to provide the special requirements that are important in the distributed form of Constraint Satisfaction Problem (CSP). The paper describes the important criteria for distributed CSP and then demonstrates how the presented algorithm stands out over similar DCSP solvers considering these criteria. Finally, the proposed approach is evaluated on random binary problems. The practical results show that this method, in most of the cases, outperforms the Asynchronous Backtracking Algorithm (ABT) and Distributed Breakout Algorithm (DBA) two important algorithms in this field of research.

► We demonstrated ants’ power in solving DCSP and described new method for such a solution.
► Presented algorithm provides important requirements of the distributed form of CSP.
► We demonstrated how the presented algorithm stands out over similar DCSP solvers.
► Proposed approach is evaluated on random binary problems.
► Results show that this method, in most of the cases, outperforms the ABT and DBA.