Options
2000
Report
Titel
A formalization of autonomous dynamic reconfiguration in distributed constraint satisfaction
Abstract
Viele interessante praktische Probleme in der Prozeßkontrolle, in Aktions- und Einsatzplanung können als Constraint-Satisfaction-Probleme modelliert und mit entsprechenden Verfahren gelöst werden. Mindestens vier der Nachteile dieses klassischen Modells hängen direkt mit Themen der Verteilung zusammen: Komplexität, Skalierbarkeit, Datenschutz und Robustheit. Aus diesem Grunde hat sich in letzter Zeit die Untersuchung von Distributed-Constraint-Satisfaction- Problem als Forschungsrichtung etabliert. Eine typische technische Aufgabe in diesem Zusammenhang ist der Entwurf der Verteilung an sich. Eine genaue Untersuchung dieser Aufgabe zeigt, daß der Verteilungsentwurf eine kritische Größe für die Qualität und die Effizienz des Problemlösungsprozesses ist und auch selbst ein Optimierungsproblem darstellt. In diesem Bericht formalisieren wir verschiedene Varianten dieses Konfigurationsproblems and weisen nach, daß sie alle zumindest NP-vollständig sind. Zur Lösung dieser Probleme schlagen wir zwei lokale Operatoren vor, die Agentenverschmelzung und die Agentenzerteilung, die beide kombiniert werden können, um die autonome und dynamische Rekonfiguration der Organisationsstruktur zwischen den Problemlösern zu ermöglichen. Wir beweisen, daß Folgen dieser Operatoren hinreichend für die Lösung jedes Konfigurationsproblems sind. Außerdem beschreiben wir kurz, welche praktischen Schritte notwendig sind, um die eher theoretischen Ergebnisses dieses Beweises in realistischen Anwendungen umzusetzen.
;
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 this area. 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 report 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 solvers. 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.
FIRST