Return from the ant
Creators: name: Brückner, Sven
Publisher: name: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Year: 2000
Subjects: subject: Multi-Agenten Systeme
subject: Produktionssteuerung
subject: Koordination
subject: Stigmergie
subject: Swarm Intelligence
subject: Emergenz
subject: Selbst-Organisation
subject: Multi-Agent Systems
subject: Manufacturing Control
subject: Coordination
subject: Stigmergy
subject: Emergence
subject: Self-Organization
subject: 004 Informatik
subject: 28 Informatik, Datenverarbeitung
subject: SU 840

description: Die vorliegende Dissertation hat einen technologischen und einen anwendungsbezogenen Schwerpunkt. Technologisch ordnen sich die präsentierten Forschungsergebnisse in das Gebiet der "Swarm Intelligence" (dt.: Schwarm-Intelligenz) ein. Swarm Intelligence ist ein Teilbereich der Informatik, der sich an der Überschneidung zwischen der Multi-Agenten Systeme Forschung der Künstlichen Intelligenz und dem Forschungsgebiet "Artificial Life" (dt.: Künstliches Leben) befindet. Im Gegensatz zur Swarm Intelligence im allgemeinen, überträgt der spezielle Ansatz "Synthetic Ecosystems" (dt.: synthetische Ökosysteme) nicht nur Koordinationsmechanismen aus biologischen Multi-Agenten Systemen, wie zum Beispiel Insekten Kolonien, in den Entwurf künstlicher Systeme. Vielmehr sollen die grundlegenden Prinzipien "natürlich" entstandener komplexer Systeme, also auch zum Beispiel einer Aktienbörse, übernommen werden. Als anwendungsbezogener Hintergrund der Dissertation wurde die verteilte Steuerung moderner industrieller Fertigungsanlagen gewählt. Die Fertigungssteuerung ist ein geeignetes Anwendungsfeld für die Technologien, die im Rahmen der Forschungsarbeiten entwickelt wurden. Damit dient die Präsentation eines synthetischen Ökosystems für die Fertigungssteuerung der Demonstration des neuartigen Ansatzes zum Entwurf, Realisierung und Evaluierung komplexer, industriell relevanter Systeme. Gleichzeitig leistet die vorgestellte Architektur der Fertigungssteuerung und die darin verwandten Koordinationsverfahren einen Beitrag zur Weiterentwicklung holonischer Produktionssysteme. Der holonische Ansatz zur Produktionsplanung und -steuerung genießt derzeit große Aufmerksamkeit sowohl in der Forschung als auch in der Industrie. Als Teilgebiet der Entwicklung intelligenter Fertigungssysteme (engl.: IMS - Intelligent Manufacturing Systems), propagiert der holonische Ansatz eine Abkehr von der traditionell zentralistischen und hierarchischen Planung und Steuerung hin zu selbst-organisierenden Systemen autonom (inter-)agierender Individuen ("Holone"). Bei der praktischen Umsetzung holonischer Systeme werden sehr häufig Technologien aus der Multi-Agenten Systeme Forschung angewandt. Mit dieser Dissertation rücken auch synthetische Ökosysteme in das Blickfeld holonischer Systeme. Natürliche Agentensysteme im allgemeinen und Kolonien sozialer Insekten im besonderen faszinieren durch ihre Robustheit, ihre Flexibilität und ihre Anpassungsfähigkeit. Solche Systeme bestehen häufig aus sehr vielen, sehr einfachen Individuen und doch weisen sie ein komplexes und koordiniertes Gesamtverhalten auf. Es gibt mehrere Zweige in unterschiedlichen Wissenschaften, zum Beispiel in der Biologie, Physik, Ökonomie oder in der Informatik, die sich mit verteilten Systemen lokal interagierender Individuen beschäftigen. Ihre Erforschung resultiert in einer Reihe wiederholt beobachteter grundlegender Eigenschaften. Um künstlich erschaffene Systeme mit ähnlichen Eigenschaften auszustatten werden Entwurfsprinzipien für das Design von Multi-Agenten Systemen in dieser Dissertation vorgeschlagen. Jedes Entwurfsprinzip wird systematisch eingeführt, motiviert und in seinen Konsequenzen für Anwendungen in der Fertigungssteuerung diskutiert. Stigmergie ist ein grundlegendes Konzept der Koordination einer großen Anzahl von Individuen unter anderem in Kolonien sozialer Insekten. Die Formulierung dieses Konzepts ist auf den Biologen Grassè zurückzuführen, welcher in der Mitte des zwanzigsten Jahrhunderts das Schwarmverhalten von Termiten untersuchte. Stigmergie beruht auf der Tatsache, daß das Verhalten eines jeden Individuums durch die aktuelle Konfiguration seiner lokalen Umwelt bestimmt wird. Die Umwelt wiederum, wird durch die Aktivitäten der Individuen verändert. Diese Wechselwirkung führt in Verbindung mit entsprechend ausgelegten individuellen Verhaltensmustern zur Emergenz einer global koordinierten Erfüllung der anstehenden Aufgaben der Kolonie. Im Detail wird sematektonische von marker-basierter Stigmergie unterschieden, wobei bei sematektonischer Stigmergie der Zustand der Aufgabenerfüllung selbst (z.B. Stand des Nestbaus) das Individualverhalten beeinflußt, während marker-basierte Stigmergie aufgabenunabhängige Marker (z.B. Pheromone) in der Umwelt platziert. Multi-Agenten Systeme finden ihre Realisierung in Software, welche gegebenenfalls an physische Aktuatoren gekoppelt ist. Im allgemeinen besteht diese Software aus einer Laufzeitumgebung und den darin ausgeführten Agenten. Die vorliegende Dissertation präsentiert eine Erweiterung von Laufzeitumgebungen um eine anwendungsunabhängige Pheromon Infrastruktur (PI). Die PI ermöglicht es den Softwareagenten des jeweiligen synthetischen Ökosystems, künstliche Pheromone als Datenstrukturen in einem virtuellen Raum abzulegen und wahrzunehmen. Diese Datenstrukturen dienen als Marker in stigmergetischen Koordinationsmechanismen. Die Algorithmen der PI operieren auf diesen künstlichen Pheromonen und emulieren die natürlichen Vorgänge der räumlichen Ausbreitung und Verdunstung von Pheromonen auf abstrakter Ebene. Zusätzlich wird das natürliche Vorbild um eine automatische Aufbereitung von Informationen erweitert. Die Funktionalität der PI wird in dieser Dissertation spezifiziert. Des weiteren wird ein formales Modell erstellt, welches die Grundlage einer numerischen Analyse der Eigenschaften der PI bildet. Die Analyse liefert Vorhersagen für das Entstehen von räumlichen Mustern von Pheromonkonzentrationen in der PI. Diese Vorhersagen können dann in der Feineinstellung und der Evaluierung von Koordinationsmechanismen verwendet werden. Außerdem dient das formale Modell als Grundlage für den Beweis der globalen Stabilität der PI. Damit ist gesichert, daß unabhängig von der gewählten räumlichen Struktur und den von der jeweiligen Anwendung generierten Pheromonen die Konzentrationen der Pheromone immer in ihrer Stärke begrenzt sind. Der Beweis der globalen Stabilität ist eine wichtige Voraussetzung für die Verwendung der PI in praktischen Anwendungen. Die Spezifikation einer verteilten Realisierung der PI bildet den Abschluß der allgemeinen Betrachtung. Die Agenten, welche die (virtuelle) räumliche Struktur der PI widerspiegeln, werden im Detail spezifiziert. Auf der Basis dieser Spezifikation ist im Rahmen der Dissertation ein Prototyp der PI realisiert worden. Dieser Prototyp diente dem Nachweis des vorhergesagten Verhaltens der Infrastruktur und der späteren Evaluierung des entwickelten Fertigungssteuerungssystems. Im weiteren Verlauf der vorliegenden Dissertation wird ein neuartiger Ansatz zur Fertigungssteuerung betrachtet. Die absehbaren Veränderungen der äußeren Bedingungen der industriellen Produktion, ausgelöst durch den globalen Übergang von Anbieter- zu Verbrauchermärkten, erfordert die Fertigung immer komplexerer und variantenreicherer Produkte in ständig schwankenden Stückzahlen und deutlich verkürzten Lebenszyklen bei gleichzeitig sinkenden Kosten. Zur Erfüllung dieser Anforderungen in der Massenproduktion wandelt sich die traditionell starr verkettete Strangfertigung (z.B. Transferstraßen) zur flexiblen Fließfertigung (z.B. flexible Bearbeitungszentren). Die Steuerung einer flexiblen Fließfertigung erfordert neue Herangehensweisen. In einer holonischen Fertigung, zum Beispiel, organisiert sich die Produktionsplanung und Produktionssteuerung selbst um die Erfüllung der aktuellen Aufträge. Dabei werden in der Steuerung verteilte, reaktive Verfahren verwendet, welche eine deutlich gesteigerte Robustheit und Flexibilität gegenüber Störungen und Veränderungen aufweisen. Der Übergang zur flexiblen Fließfertigung bedeutet die Einführung von Flexibilität in der Bearbeitung aber auch im Transport des Materials. Es ist eine grundlegende Eigenschaft dieser Fertigungssysteme, daß zu einem beliebigen Zeitpunkt eine Reihe möglicher Transportwege und damit eine Vielzahl möglicher Muster im Materialfluß zur Verfügung stehen. Dabei führt aber nur eine kleine Menge dieser Muster zu einer bestmöglichen Erfüllung der globalen Produktionsziele (z.B. hoher globaler Durchsatz). Es ist also die Aufgabe der Fertigungssteuerung in jeder Situation das bestmögliche Materialflußmuster zu erreichen. Ist ein verteilter Ansatz für die Steuerung gewählt worden, so muß diese Optimierung nach globalen Produktionszielen in die lokalen Steuerungsentscheidungen integriert werden, ohne die Autonomie der lokalen Einheiten zu verletzen. Die Dissertation präsentiert ein sogenanntes geführtes Fertigungssteuerungssystem (GFSS), welches einen verteilten und reaktiven Steuerungsansatz mit einer Flußoptimierung unter Beachtung globaler Produktionsziele in neuartiger Weise verbindet. Der Entwurf des GFSS folgte den vorgeschlagenen Prinzipien für synthetische Ökosysteme und die Agenten im GFSS werden mit Hilfe der Pheromon Infrastruktur koordiniert. Die Agenten und Pheromone des GFSS werden detailliert spezifiziert und in einem realistischen Beispiel aus der Automobilindustrie evaluiert. In der Evaluierung wird von den Ergebnissen der Analyse der PI Gebrauch gemacht. Die dabei gewählte numerische Beschreibung des Einzelverhaltens und die darauf aufbauende Betrachtung des emergierenden Gesamtverhaltens weist den Weg zu einer systematischen Evaluierung von emergenten Systemeigenschaften in synthetischen Ökosystemen. In einem abschließenden Kapitel werden die drei inhaltlichen Schwerpunkte der Dissertation noch einmal betrachtet. Vor dem Hintergrund des GFSS werden die vorgeschlagenen Entwurfsprinzipien für synthetische Ökosysteme systematisch auf ihre Anwendbarkeit und praktische Bedeutung hin überprüft. Außerdem wird die allgemeine Verwendung der PI für den Austausch von Informationen zwischen Agenten untersucht. Und schließlich wird die Fertigungssteuerung aus der Sicht abstrakter Zustandsräume diskutiert. Die vorliegende Dissertation weist den Weg für eine Reihe weiterführender Forschungsarbeiten. So werden zum einen detaillierte Konzepte für die Erweiterung des GFSS um eine automatische Strategiebewertung und -generierung und um ein Visualisierungssystem vorgestellt. Zum anderen werden aber auch notwendige Ergänzungen der Entwurfsprinzipien und mögliche Verbesserungen der PI und des darauf basierenden Evaluierungsansatzes vorgeschlagen.
description: The synthetic ecosystems approach attempts to adopt basic principles of natural ecosystems in the design of multiagent systems. Natural agent systems like insect colonies are fascinating in that they are robust, flexible, and adaptive. Made up of millions of very simple entities, these systems express a highly complex and coordinated global behavior. There are several branches in different sciences, for instance in biology, physics, economics, or in computer science, that focus on distributed systems of locally interacting entities. Their research yields a number of commonly observed characteristics. To supply engineered systems with similar characteristics this thesis proposes a set of principles that should be observed when designing synthetic ecosystems. Each principle is systematically stated and motivated, and its consequences for the manufacturing control domain are discussed. Stigmergy has shown its usefulness in the coordination of large crowds of agents in a synthetic ecosystem. Sign-based stigmergy through synthetic pheromones is supported by an extension to runtime environments for software agents called the pheromone infrastructure. In this thesis the operation of the pheromone infrastructure is specified, formally modeled and analyzed, and an implementation is presented. The guided manufacturing control system for flexible flow shops is designed following the proposed principles and it uses the pheromone infrastructure to coordinate its agents. It comprises two subsystems. The control (sub)system, which enables production, is distributed and reactive. The advisory (sub)system observes the operation of the control system and advises the manufacturing execution under global considerations. This thesis specifies the guided manufacturing control system and evaluates its operation in a simple but realistic example adapted from the automotive industry. The applicability of the design principles, the usage of the pheromone infrastructure, and the operation of manufacturing control in abstract state spaces are considered on the basis of the guided manufacturing control system.