A Dynamic Organization in Distributed Constraint Satisfaction

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Student Abstracts

We present a novel dynamic organization to solve DCSP(Distributed Constraint Satisfaction Problem). DCSP provides a formal framework for studying cooperative distributed problem solving[Yokoo 921. To solve DCSP, we have developed a simple algorithm using iterative improvement. This technique has had great success on certain CSP(Constraint Satisfaction Problems)[Minton 9O][Selman 92]. In our algorithm each agent performs iterative improvement and also plural agents can do in parallel. However, one drawback of this technique is the possibility of getting caught in local minima(which are defined specifically in our algorithm). LMO is a technique for escaping from local minima. It is summarized as follows: When an agent(A1) gets caught in a local minimum, (step I) Al sends its CSP(variables, domains and constraints) to an agent(A2). Al selects A2 such that it shares violated constraints at that time. Ties are broken randomly. (step 2) AZ puts its CSP and Al’s CSP together and searches for all possible assignments with simple backtracking. After that, A2 performs iterative improvement. Besides escaping from local minima, LMO prevents agents from getting caught in the same local minima as before. Therefore our algorithm for DCSP is complete.