Affiliations: Planning and Optimization Laboratory, Research Institute for Computer Architecture and Software Technology (FIRST), GMD — German National Research Center for Information Technology eMail: hannebau@first.gmd.de
Abstract: Several interesting practical problems in process control, planning and scheduling can be expressed and solved using the model of constraint satisfaction problems. At least four drawbacks of this classical model directly relate to areas of distribution: complexity, scalability, privacy and robustness. Hence, research on distributed constraint satisfaction problems is a new direction in the area of multi-agent systems. A typical engineering task in distributed constraint satisfaction is the design of the distribution itself. A careful look at this task reveals that the design of distribution is critical to the quality and efficiency of the problem solving process and is itself an optimization problem. In this article we formalize different variants of this configuration problem and prove them to be all at least NP-complete. For solving these problems, we present two local operators, agent melting and agent splitting, that can be combined to allow for an autonomous and dynamic reconfiguration of the organizational structure of the problem-solving agents. We prove sequences of these operators to be sufficient for solving any given configuration problem. We also briefly describe what practical steps are necessary to exploit the rather theoretical result of the proof in realistic applications.
