| dc.description.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. | |
