Topas

von Hagen Kröber, 1997

Topas ist ein objektorientierter Fertigungssimulator für parallele Rechnerarchitekturen. Da die Analyse von Fertigungssystemen regelmäßig zu einer Menge mehr oder weniger autonom arbeitender Subsysteme, wie Fertigungsplätzen, Werkern, Transportsystemen, Puffern usw., führt, liegt es nahe, diese relativ unabhängig voneinander agierenden Komponenten in einem Simulationsmodell als parallel wirkende Agenten mit in Umfang und Zeit begrenzter Kommunikation aufzufassen. Die im Bereich der Künstlichen Intelligenz untersuchten Multiagentensysteme (MAS) bieten einen guten Ansatz zur Lösung von Parallelisierungsproblemen, wie sie bei der Modellierung komplexer Fertigungssysteme auftreten. Agenten sind dabei selbständig planende, handelnde und lernende Einheiten der Fertigung, wie Maschinen, Transporteinheiten, Lager usw. Sie bewerben sich im Rahmen eines marktorientierten Verhandlungsprotokolls (contract net) um die Übernahme von Aufträgen zur Ausführung von Teilaufgaben (Bohren, Fräsen, Montieren, Transportieren, Lagern, ... ). Das Ziel der Planung und Simulation ist die Ermittlung von optimalen Fertigungsabläufen mit minimalen Durchlaufzeiten der einzelnen Fertigungsaufträge durch Selbstorganisation der Agentengesellschaft.
Was ist ein Agent ?

Die Übersetzung des Wortes Agent bedeutet "wirkendes, handelndes Wesen". In der vorstehenden Abbildung wird eine typische Agentenarchitektur für die Modellierung von Agenten in Fertigungssystemen skizziert. Dabei handelt es sich um sogenannte reflektive Agenten, d.h. jeder Agent hat eine Intention. Produktionsagenten haben die Intention, möglichst viele Aufträge zu erledigen. Lageragenten die Intention, möglichst wenig zu lagern, aber trotzdem immer liefern zu können, usw.
Allgemein können Agenten mit folgenden Eigenschaften charakterisiert werden:

autonom:
Der Agent besitzt selbst die Kontrolle über seine Aktivitäten und handelt ohne direkten Eingriff aus seiner Umwelt.
rational, zielorientiert:
Der Agent hat Ziele, die er versucht, durch sein darauf ausgerichtetes Verhalten zu erreichen.
intelligent:
Die Definition von Intelligenz ist eine Grundfrage der klassischen Künstlichen Intelligenz (KI) und bisher noch nicht zufriedenstellend beantwortet. Im allgemeinen wird einem künstlichen System beschränkte Intelligenz zugestanden, soweit sich sein Verhalten in einer begrenzten Umwelt nicht erkennbar von dem eines Menschen unterscheiden läßt (Turing-Test).
adaptiv, lernend:
Frühere Beobachtungen und Erfahrungen des Agenten führen zu Veränderungen seines zukünftigen Verhaltens.
kommunikativ, sozial:
Betont wird die Fähigkeit zur expliziten Kommunikation des Agenten mit seiner Umwelt und die (Selbster-) Kenntnis von der Einbeziehung des Agenten in eine Agentengesellschaft.
Das Zusammenwirken mehrerer Agenten nach einem gegebenen Organisationsprinzip (Kooperationsmodell) führt zu Agentengesellschaften, den sogenannten Multiagentensystemen.
Multiagentensysteme

Aus der Synergetik stammt das Prinzip der Selbstorganisation, das zur Erklärung für das spontane Entstehen von Ordnungsstrukturen innerhalb einer größeren Anzahl von einzelnen Individuen (Agenten) herangezogen wird. Probleme, an deren Lösung ein einzelner Agent scheitern würde, können nur durch das koordinierte Zusammenwirken mehrerer Agenten gelöst werden.
Anhand der folgenden Merkmale können Agentensysteme klassifiziert werden:

Problemlösungsstrategie:
Problemlösung durch Synthese und/oder Dekomposition und Verteilung von Teilproblemen.
Organisationsstufen:
Grad des Zusammenwirkens der Agenten (Individuum, Team, Gesellschaft).
Agentenanzahl:
klein oder groß, statisch oder dynamisch.
Granularität:
Relative Komplexität von Teilaufgaben der Agenten im Verhältnis zum Gesamtproblem.
Interaktionschema:
Abstraktionsniveau von Kommunikationsinhalten (einfach, komplex) und die Anzahl an der Kommunikation beteiligter Agenten.
Verteilung der Kontrolle:
Das Verhalten der Agenten wird zentral gesteuert und kontrolliert, die Agenten sind teilweise autonom oder völlig unabhängig.
Kooperationsbereitschaft:
Altruistische Agenten berücksichtigen die Ziele anderer Agenten, tit-for-tat-Agenten sind nur bedingt kooperativ und egoistische Agenten stehen in reiner Konkurrenz zueinander.
Kopplung:
Der Grad der Wechselwirkung zwischen den Agenten bestimmt sich durch das Verhältnis von Kommunikations- zu lokalem Berechnungsaufwand.

Da die zur Kooperation und Koordination notwendige Kommunikation die wesentliche Rolle bei der Beschreibung und Bewertung von Multiagentensystemen spielt, werden diese Systeme meist in folgender Weise systematisiert:

Systeme der indirekten Kommunikation:

Systeme der direkten Kommunikation:
Das Contract-Net-Modell

Ein Contract Net setzt sich aus einem lose gekoppelten Netz verteilter Knoten (Agenten) zusammen, die über ein Kommunikationssystem direkt miteinander Informationen austauschen. Es existieren keine zentrale Kontrollinstanz und keine globale Wissensbasis. Ein Problem ist nur durch die Kooperation der Agenten lösbar und wird in einer Folge von Verhandlungen zwischen Agentenpaaren auf die Knoten verteilt. Das Kommunikationsprotokoll definiert einen marktähnlichen Koordinierungsmechanismus zwischen einem Vertragsanbieter (Manager) und einem Vertragsnehmer (Contractor).


Zustandsdiagramm eines Manager-Agenten



Zustandsdiagramm eines Contractor-Agenten

Ein Agent kann eine Aufgabe entweder selbst bearbeiten oder Teile davon in Form einer Ausschreibung anderen Agenten bekanntmachen. Innerhalb eines mehrstufigen Verhandlungsdialogs zwischen dem Manager und seinen Bewerbern wird für jeden (Teil-) Auftrag der geeignetste Bewerber ermittelt. Dieser Contractor hat mit dem Zuschlag die Verantwortung für die Bearbeitung seines Auftrages übernommen. Die Rollenverteilung unter den Agenten ist nicht fest vorgegeben. Ein Agent kann also gleichzeitig als Manager und als Contractor wirken. Die Agenten kennen a priori nicht die Fähigkeiten und das Verhalten der anderen Agenten. Jeder Agent führt planende und ausführende Operationen aus.
Die Verteilung der Ablaufkontrolle und das Fehlen von zentralen Ressourcen ermöglichen ein hohes Maß an Nebenläufigkeit. Demgegenüber steht ein hoher Kommunikationsaufwand für die Synchronisation der Agenten. Die Ausnutzung der potentiell vorhandenen Parallelität ist unmittelbar vom Charakter des Anwendungsproblems abhängig.

Agentenorientierte Simulation von Fertigungssystemen

Zur Einordnung in die klassische Simulationsmethodik ist dieser Ansatz eine Variante der ereignisorientierten, diskreten Simulation. Die Agenten werden dabei als permanente aktive Elemente des Simulationsmodells betrachtet. Das Ziel der Simulation liegt darin, einen möglichen Fertigungsablauf als Ergebnis der Selbstorganisation der Agenten zu erzeugen, der durch einen konkreten Materialfluß und folgende Kenngrößen beschreibbar ist:

Das dynamische Verhalten des Simulationsmodells entsteht durch eine Folge von Zustandsänderungen zu bestimmten diskreten Zeitpunkten der Modellzeit. Sie werden sowohl durch Ereignisse des Materialflusses (Jobs) wie auch durch Ereignisse der Kommunikation (Nachrichten) ausgelöst. Wobei Nachrichten i.allg. keine Entsprechung im realen Fertigungssystem besitzen!
Die Fortschreibung der Modellzeit erfolgt gemäß dem ereignisorientierten Simulationsmodell durch das Setzen einer Simulationsuhr auf den Ereigniszeitpunkt des nächsten auszuführenden Ereignisses. Darüber hinaus besitzt jeder Agent eine eigene, lokale Simulationsuhr. Alle für einen Agenten eingeplanten Ereignisse werden, nach ihrem Zeitstempel geordnet, in einer Ereignisliste im FIFO-Prinzip verwaltet. Lokale Simulationsuhren und damit lokale Modellzeit führen zu Nebenläufigkeit im Modellierungsansatz und der Notwendigkeit der Synchronisation der Ereignisausführung.
In Topas wird die Synchronisation der Agenten mit dem konservativen Verfahren realisiert. Dabei wird durch den Austausch von Zeitgarantien und dem Setzen von globalen Barrieren die Kausalität bei der Ausführung von Ereignissen a priori gewährleistet. D.h. ein Ereignis wird erst dann ausgeführt, wenn sichergestellt ist, daß es nicht von einem später auszuführenden Ereignis abhängig ist.
Das gesamte Simulationssystem ist in vier Abstraktionsebenen aufgeteilt:
Modellierungsebene:
Aktive Elemente sind die Fertigungsplätze, Transporteinheiten, Lager und Schnittstellenelemente. Sie sind durch eine Material- und Informationsflußtopologie miteinander verbunden.
Agentenebene:
Hier wird die nach dem Contract-Net-Modell organisierte Agentengesellschaft repräsentiert.
Simulationsebene:
Jeder Agent wird auf einen logischen Prozeß abgebildet. Die logischen Prozesse führen lokale Ereignisse aus und planen sich gegenseitig neue Ereignisse ein.
Ausführungsebene:
Die Verwaltung nebenläufiger Aktivitäten, Kommunikation und Interaktion werden mit Hilfe der Funktionalität der Programmbibliothek Parallel Virtual Machine (PVM) implementiert.
Das Simulationssystem ist somit ein verteiltes Programmsystem. Seinem Entwurf liegt ein paralleles und objektorientiertes Programmiermodell zugrunde. Die Umsetzung echt paralleler Funktionsabläufe macht die Anwendung des CSP-Modells (Communicating Sequential Processes von Hoare) erforderlich.


Topas-Systemarchitektur

Die Kommunikation zwischen den Prozessen auf der Ausführungsebene erfolgt bidirektional, direkt und asynchron nach dem Prinzip des Message Passing. Die Zuordnung von Prozessen zu Prozessorknoten ist Aufgabe des PVM-Systems und wird nach PVM-internen Strategien vorgenommen.

Ablauf einer Simulationsstudie
  1. Vorgabe der Modellbeschreibung durch eine
  2. Starten und Initialisieren des Simulationssystems durch Aufruf der Simulatorkonsole.
  3. Nach Ablauf der Simulation ist eine Ergebnisdatei zur Auswertung verfügbar.
Die Simulationsergebnisse beruhen auf dem Lösen eines Planungsproblems für ein gegebenes Produktionsprogramm auf einer feststehenden Fertigungstopologie. Die Lösung des Planungsproblems beruht auf der Selbstorganisation einer Agentengesellschaft, in der jeder Agent durch Erreichen lokaler Optimalität versucht, zur Gesamtoptimalität beizutragen. Insbesondere die Anwendung optimaler Bewertungsstrategien für Angebote und das Lernen der Agenten über das situationsabhängige Verhalten ihrer Umgebung lassen dem System einen Optimierungsspielraum.