Static versus dynamic generation of local solutions in Distributed Constraint Satisfaction Problems

Abstract

Solutions to difficult real-world problems, like logistics planning and timetable scheduling, are often bound by certain constraints that need to be satisfied. As such, solutions to these problems can be found by modeling and solving the problems as Constraint Satisfaction Problems (CSP). In this thesis, we will research algorithms for solving a distributed version of CSP, DisCSP, where the problem is divided amongst multiple agents. In order to solve these problems, agents must find a solution to their individually assigned subproblem, and communicate with other agents to ensure their local solutions do not interfere with each other. We will look at two algorithms, one having agents generate all possible local solutions before communicating with other agents, so called static generation, the other having agents generate local solutions only after certain agents have communicated theirs, so called dynamic generation. We will test these algorithms by using them to solve Calcudoku, a logic puzzle with a great parallel to planning problems, on which we will expand first. We compare the algorithms based on the computational effort and the amount of communication they require to solve Calcudokus of different sizes. Our results show that when solving Calcudokus of the chosen dimensions, the algorithm using static generation outperforms the algorithm using dynamic generation in terms of both computational effort and amount of communication. However, our results suggest that if the DisCSP to be solved gets more complex, dynamic generation of local solutions might be preferred.