A Dynamic Organization in Distributed Constraint Satisfaction

Katsutoshi Hirayama, Seiji Yamada, Jun'ichi Toyoda

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.