Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-372
Main Title: Autonomous Dynamic Reconfiguration in Collaborative Problem Solving
Translated Title: Autonome Dynamische Rekonfiguration im kooperativen Problemlösungsprozeß
Author(s): Hannebauer, Markus
Advisor(s): Jähnichen, Stefan
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Mit dieser Arbeit wird eine ausführliche Untersuchung von kooperativem Problemlösen, seinen Vor- und Nachteilen, vor allem aber seiner Verbesserung durch Autonome Dynamische Rekonfiguration vorgelegt. Autonome Dynamische Rekonfiguration behandelt zwei typische Probleme kooperativen Problemlösens: schlechte Problemlösungsergebnisse und hoher Kommunikationsaufwand. Die Kernidee ist dabei die autonome und dynamische Anpassung der Konfiguration eines Problemlösungsprozesses, d. h. der Verteilung von Wissen, Zielen und Fähigkeiten, an das Problem selbst. Grundlage dafür sind zwei lokale Operationen: Agent Melting und Agent Splitting. Beim Agent Melting werden das Wissen, die Ziele und Fähigkeiten mehrerer Agenten in einem Agenten zusammengeführt, beim Agent Splitting ein Agent in mehrere Agenten zerlegt, wobei möglicherweise neue Agenten entstehen. Dabei wird eine stichhaltige theoretische Grundlage sowohl für kooperatives Problemlösen als auch für Autonome Dynamische Rekonfiguration gelegt. Die Problemstellung, eine gute Konfiguration für ein gegebenes Problem zu finden, weist eine Verbandsstruktur auf und ist nachweislich schwer zu lösen. Durch die Charakterisierung von Agent Melting und Agent Splitting als Operationen auf Äquivalenzrelationen können wichtige Eigenschaften dieser Operationen nachgewiesen werden, wie Strukturerhalt, Wirkung, Hinlänglichkeit und nebenläufiges Verhalten. Im praktischen Teil dieser Arbeit wird eine effiziente und effektive Instanz von kooperativem Problemlösen präsentiert. Alle dargestellten Konzepte, wie das Multi-phase-Agreement-Finding-Protokoll zum externen Problemlösen, die kompositionale Belief-Desire-Intention-Agentenarchitektur und eine spezielle Architektur zur Constraint-Spezifikation beim internen Problemlösen, sind so entworfen, daß sie mit dynamischen Konfigurationsänderungen umgehen können. Alle Konzepte werden durch einen lokalen Steuerungsmechanismus integriert, der durch Beobachtung und Selbstbeobachtung entscheidet, wie die Konfiguration angepaßt werden muß. Sowohl Theorie als auch Praxis werden mithilfe einer Fallstudie aus der medizinischen Terminplanung evaluiert. Die Autonome Dynamische Rekonfiguration liefert dabei überzeugende Ergebnisse - die Lösungsqualität wird um bis zu 20 Prozent gesteigert, während der Kommunikationsaufwand mehr als halbiert wird. Mithilfe dieser Technik erreicht der kooperative Problemlösungsprozeß fast die Qualität eines zentralen Ansatzes, ist aber effizienter.
This thesis is a comprehensive study of collaborative problem solving, its advantages and pitfalls, but mainly its improvement by autonomous dynamic reconfiguration. Autonomous dynamic reconfiguration deals with two common problems in collaborative problem solving - poor problem solving results and high communication effort. The main idea of autonomous dynamic reconfiguration is to autonomously and dynamically adapt the configuration of a collaborative problem solving effort, i.e. the distribution of knowledge, goals and skills, to the problem itself. This is done by two individual local operations -- agent melting and agent splitting. Agent melting means to unify the knowledge, goals and skills of two or more agents in a single agent, while agent splitting denotes a process in which a single agent is split, possibly resulting in an additional new agent. In this work we lay a sound theoretical foundation for collaborative problem solving itself and for its improvement by autonomous dynamic reconfiguration. The problem of finding a good configuration for a given problem has been proven to feature a lattice structure and to be complex to solve. Based on a characterization of agent melting and agent splitting as equivalence relation manipulators, these two operators show verifiable properties regarding structure retainment, impact, sufficiency and concurrency. On the practical side, collaborative problem solving finds a very flexible and effective instantiation in this work. All presented concepts for collaborative problem solving, such as the multi-phase agreement finding protocol for external problem solving, the composable belief-desire-intention agent achitecture and the distribution-aware constraint specification architecture for internal problem solving, are designed to support a changing configuration. This set of concepts is integrated by the AuReCon controller that decides by observation and self-observation how to locally adjust the configuration. The proposed theory and practice are validated using a case study in medical appointment scheduling. The autonomous dynamic reconfiguration approach shows convincing results in improving the problem solving quality by up to 20 percent and by more than halving the communication effort. Using autonomous dynamic reconfiguration, the collaborative problem solving techniques can match the quality of a central approach and are more efficient.
URI: urn:nbn:de:kobv:83-opus-2749
http://depositonce.tu-berlin.de/handle/11303/669
http://dx.doi.org/10.14279/depositonce-372
Exam Date: 30-Nov-2001
Issue Date: 17-Dec-2001
Date Available: 17-Dec-2001
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Agentenverschmelzung
Agentenzerteilung
Autonome Dynamische Rekonfiguration
Kooperatives Problemlösen
Multiagentensysteme
Selbstorganisation
Agent Melting
Agent Splitting
Autonomous Dynamic Reconfiguration
Collaborative Problem Solving
Multi-Agent Systems
Self-Organization
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Publications

Files in This Item:
File Description SizeFormat 
hannebauer_markus.pdf60,71 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.