Improved Forward Checking Tree Algorithm for Distributed Constraint Satisfaction Problems

Constraint Programming (CP) is one of the promising and hopeful Artificial Intelligence paradigms. It’s based on its powerful framework named Constraint Satisfaction Problem (CSP). This framework makes it possible to formalize many real world combinatorial problems. The Distributed CSP (DisCSP) is used when the problem is distributed into groups of variables; each one managed by a specific agent; and that the values of those variables can only be modified by their respective agent. Many algorithms have been proposed to solve DisCSP problems. Their main purpose is to reduce the solving time, the number of constraint checks and the number of exchanged messages between the agents during the solving process. In this paper, we propose a new algorithm based on the Asynchronous Forward Checking Tree (AFC-tree) algorithm for the DisCSP problems named Improved Forward Checking Tree (IFC-tree). The experimental results show the efficiency of this algorithm by improving different metrics of the solving performances.