Entwicklung eines Multiagentensystems auf Basis des Frameworks Jade zur Lösung komplexer Schedulingprobleme

Inhaltsverzeichnis

1 Einleitung

2 Grundlagen
2.1 Definition Agent
2.2 Arten von Softwareagenten nach Russel und Norvig
2.3 Eigenschaften einer Agentenumgebung
2.4 Multiagentensystem
2.5 Emergenz im Multiagentensystem
2.6 Rollenmodell
2.7 Referenzmodell für Agentenplattformen
2.8 Betrachtung agentenbasierter Systeme und aktueller Einsatzgebiete
2.8.1 Electronic Commerce
2.8.2 Information Retrieval
2.8.3 Weitere Einsatzgebiete
2.9 Schedulingproblem

3 Konzeption eines Multiagentensystems
3.1 Anforderungen
3.2 Agentenrollen
3.2.1 Server Agent
3.2.2 Task Contractor Agent
3.2.3 Controller Agent
3.2.4 Collector Agent
3.2.5 Splitter Agent
3.2.6 Answer Agent
3.2.7 Jabber Agent
3.2.8 Client Agent
3.2.9 Load Balance Agent
3.2.10 Worker Agent
3.3 Architektur
3.4 Kommunikation der Agenten
3.4.1 Nadiri chtenpaket
3.4.2 Scheduling Task Paket
3.4.3 Control Task Paket
3.5 Last Verteilung
3.6 Ausfallsiclierlieit und Fehlertoleranz
3.7 Funktionsweise des Systems
3.8 Skalierbar keit
3.9 Betrachtung des entstandenen Systems

4 Implementierung
4.1 Java Agent Development Framework
4.1.1 Verhaltensmuster von Agenten
4.1.2 Interaktion zwischen Agenten
4.1.3 Gruppenunterstützungsmodell
4.1.4 Informationssicherheit
4.1.5 Ausfallsicherheit
4.2 Scheduling Framework
4.2.1 Näherungs verfahren der Simulation
4.2.2 Funktionsweise des Frameworks
4.2.3 Algorithmen und Zielkriterien
4.3 Implementierung von Lagoon
4.3.1 Start des Systems
4.3.2 Agentenrollen
4.3.3 Nachrichtenpakete und Kommunikation der Agenten
4.4 Grafische Benutzeroberfläche

5 Schedulingalgorithmen
5.1 Einteilung der Algorithmen
5.2 Sequenzierungsalgorithmen
5.2.1 Random Down Swing
5.2.2 Random Walk Recipe Variation
5.2.3 Simplex Methode
5.2.4 Partikel Schwarm Optimierung
5.3 Partitionierungsalgorithmus
5.3.1 Central Complex
5.3.2 Weitere Optimierungsalgorithmen

6 Simulation und Ergebnisse
6.1 Testfälle und Simulationsumgebung
6.2 Simulation 1: Parallele Maschinen
6.3 Simulation 2: Simplex Methode
6.4 Simulation 3: Lateness
6.5 Simulationsergebnis

7 Zusammenfassung und Ausblick

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

A Grundlagen
A. l Agentenarchitekturen
A. 2 Kommunikationsparameter

В Konzeption eines Multiagentensystems
B. l Beispielstruktur eines Systems mit Lagoon
B. 2 Sequenzdiagramm des Beispiels für die Funktionsweise

c Implementierung
C.l Weitere Frameworks für Agentensysteme
C. 2 Klassenhierarchie der Behaviours
C. 3 Kommunikationsaktivitäten

D Simplex Methode am Beispiel

E Simulation
E.l Betriebsumgebungen
E.2 Testfälle
E.3 Simulation: Simplex Methode

Kurzfassung

Ziel dieser Diplomarbeit ist die Konzeption und Implementierung eines universell ersetzbaren Multiagentensystems für unterschiedliche Anwendungsgebiete. Bei diesen Systemen erfolgt das Lösen von Aufgaben durch das Zusammenwirken der spezialisierten Handlungsweisen autonom agierender, intelligenter Agenten. Die dabei entstellenden Koordinations-, Kooperations- und Organisationsprobleme werden durch die Methoden des Rollenmodells und der verteilten künstlichen Intelligenz bewältigt. Zur Evaluierung des entwickelten Systems erfolgen Berechnungen von kombinatorischen sequenzabhängigen Schedulingproblemen. Dazu werden mehrere Optimierungsalgorithmen auf der Basis von Agenten erstellt.

Das in dieser Arbeit entworfene Multiagentensystem erfüllt mit seinen Fälligkeiten die aktuellen Anforderungen für flexibles verteiltes Reclinen. Die Untersuchung zeigt, dass agentenbasierte Softwarearchitekturen viele Vorteile gegenüber dem objekt- und komponentenbasierten Ansatz bieten. Die Agententechnologie ermöglicht eine übersichtliche Systementwicklung und führt unter anderem zu einer besseren Beherrschung der Systemkomplexität. Durch das intelligente Verhalten der Agenten lassen sich die komplexen Schedulingprobleme effizient lösen.

Abstract

The objective of this thesis is the conception and implémentation of multi-agent system that is capable of being used in a variety of different environments. Such a system is able to solve tasks by using a variety of independent specialized agents. There are however problems in the co-ordination and co-operation of large numbers of agents that act independently. These problems are countered by the use of the role model and distributed artificial intelligence. For the purpose of the evaluation of the multi-agent system combinatory sequence dependent scheduling is used. The algorithms for the optimization are also going to created by agents.

The developed multi-agent system has the attributes that are required for modern flexible distributed computing. This investigation has shown that an agent-based software architecture posses many advantages in comparison to an object- and component-based approach. These advantages include a considerable advance in the development of systems as the agent-approach leads to a less complex layout. In addition, an agent-based architecture improves the control of a complicated system.

1 Einleitung

Ein Agent ist eine selbstständig, aktiv handelnde Softwarekomponente, welche die Umgebung durch Sensoren wahrnimmt und über Effektoren beeinflusst. Wenn mehrere Agenten miteinander interagieren, um ein Problem zu lösen, dann entsteht ein Multiagentensystem. Solche Systeme werden bereits seit mehreren Jahren in verschiedenen Bereichen eingesetzt. Sehr verbreitet sind sie in der Logistik-, Produktions- und Verkehrsplanung. Auch auf dem Gebiet der Biologie, Soziologie und Gesundheitsversorgung finden Agenten Anwendung. Seit einiger Zeit werden Multiagentensysteme sogar zur Simulation in der Computergrafik eingesetzt und zur Filmherstellung genutzt, um kostengünstig viele bewegte Lebewesen darzustellen. Der Einsatz von Agenten in der Netzwerktechnologie ermöglicht die automatische und dynamische Last Verteilung, hohe Skalierbarkeit und ausfallsichere Netzwerke. Durch Agenten- und Multiagentensysteme lassen sich die Gegebenheiten besser als bei einem objektorientierten Ansatz abbilden, über das einzeln spezifizierte Verhalten werden dynamische Wechselwirkungen nachgewiesen, Zusammenhänge verständlich und Phänomene erklärt.

Das anhaltend große Interesse an agentenbasierter Softwareentwicklung sowohl in Industrie als auch in der Forschung basiert auf der Effizienz, der Robustheit und der Komplexitätsminimierung sowie der Mobilität dieser Systeme. Das Ziel der vorliegenden Diplomarbeit ist die Konzeption und Implementierung eines Multiagentensystems zur Lösung von komplexen Schedulingproblemen. Die zu untersuchende Anforderung des Schedulings tritt bei Cluster Tools auf. Diese werden zur Bearbeitung von Wafern in der Halbleiterindustrie eingesetzt. Für die effiziente Herstellung von Chips ist ein optimierter Ablaufplan erforderlich, um die Produktionszeit zu verkürzen und die damit verbundenen Kosten zu senken. Die zur Optimierung eingesetzten Verfahren aus dem Gebiet der evolutionären Algorithmen lassen sich durch den Einsatz von Agenten präzise adaptieren.

Bei einer agentenbasierten Softwarearchitektur werden Aufgaben durch gemeinsame Operationen mehrerer Agenten gelöst. Dabei treten jedoch Koordinations-, Organisations- und Strukturprobleme auf. Daher befasst sich diese Arbeit neben intelligenten Softwareagenten mit den Entwicklungsmethoden agentenbasierter Systeme. Auseinandergesetzt wird sich dabei mit der Gestaltung der Architektur von Multiagentensystemen sowie mit Verfahren und Strategien zur Kommunikation und Kooperation von Agenten. Zentrale Aspekte eines solchen verteilten Systems sind die Ressourcenauslastung, Fehlertoleranz und Sicherheit.

Als Grundlage dient ein in Java programmiertes Framework, welches die allgemeinen Spezifikationen für Agentensysteme berücksichtigt. Dieses stellt grundlegende Funktionalitäten für die Erzeugung von Agentenplattformen mit mehreren Diensten und Agenten mit verschiedenen Verhaltensformen bereit. Darüber hinaus wird die Kommunikation zwischen Agenten unterstützt. Zur Evaluierung des Multiagentensystems steht ein weiteres Framework für typische Schedulingprobleme in der Halbleiterproduktion zur Verfügung. Es beinhaltet einen diskreten Ereignissimulator, welcher Näherungs verfahren zur Simulation von Ablaufplänen verwendet. Weiterhin bietet es neben mehreren Algorithmen zur Optimierung von diesen Schedules auch Bewertungsfunktionen bezüglich der Erfüllung verschiedener, zeitlicher Vorgaben an.

Nach dieser Einleitung enthält die Arbeit im zweiten Kapitel zunächst eine detaillierte Beschreibung der theoretischen Grundlagen. Dabei werden die Eigenschaften von Agenten- und Multiagentensystemen betrachtet, die verschiedenen Arten klassifiziert sowie die Agentenumgebungen beschrieben. Auf das gemeinschaftliche Verhalten und die Entstehung von Emergenz wird eingegangen. Darüber hinaus bieten das Rollenmodell und die Methoden der künstlichen Intelligenz, Möglichkeiten zur Koordination, Organisation und Kooperation von mehreren Agenten in solchen Systemen. Anschließend wird das Referenzmodell zum Aufbau von Multiagentensystemen beschrieben. Weiterhin werden verschiedene Einsatzgebiete der Agententechnologie sowie bereits bestehende Systeme betrachtet. Eine Beschreibung des Anwendungsgebiets der Halbleiterproduktion und der kombinatorischen sequenzabhängigen Schedulingprobleme schließen die Grundlagen ab. Das Kapitel 3 umfasst die Entwicklung des Multiagentensystems für komplexe Schedulingprobleme. Dies beinhaltet eine Analyse der zeitgemäßen Anforderungen, auf deren Basis das System erstellt wird. Der wesentlichste Bestandteil dieser wissenschaftlichen Arbeit ist die Konzeption und die Strukturierung eines plattformunabhängigen, flexibel einsetzbaren Multiagentensystems. Dazu gehört die Beschreibung der einzelnen Komponenten, der Architektur und der Kommunikation der Agenten. Weiterhin erfolgt eine Erläuterung der Funktionsweise, der Funktionalität und der Lastverteilung des entwickelten Systems. Anschließend werden Ausfallsicherheit und Skalierbarkeit betrachtet. Darauf auftauend erfolgt eine Analyse des entstandenen Multiagentensystems und der eingesetzten Techniken. In Kapitel 4 werden die beiden zur Entwicklung genutzten Frameworks beschrieben. Daran schließt sich die Umsetzung des konzipierten Multiagentensystems auf das plattformspezifische Modell an. In Kapitel 5 werden zu den bereits implementierten Optimierungsalgorithmen im Scheduling Framework weitere vorgestellt. Neben einer Erklärung der Algorithmen und deren Funktionsweise bezüglich des komplexen Lösungsraumes ist deren Implementierung erläutert. In Kapitel 6 findet mit Hilfe von Simulationen ein Vergleich verschiedener Lösungsmethoden für die gegebene Problemstellung des Anwendungsgebietes statt. Den Abschluss bilden eine Zusammenfassung und ein Ausblick dieser Arbeit.

2 Grundlagen

Dieses Kapitel behandelt die erforderlichen Grundlagen für die Entwicklung eines Multiagentensystems. Zu Beginn erfolgt eine Definition des Agenten und dessen Eigenschaften. Anschließend sind die verschiedenen Arten von Softwareagenten beschrieben sowie die Eigenschaften einer Agentenumgebung. Zentrales Thema ist die Betrachtung von Multiagentensystemen. Dabei wird auf das gemeinschaftliche Verhalten von den einzelnen Agenten in einem komplexen System und die Entstehung von Emergenz eingegangen. Ausgehend vom Rollenmodell werden Verhaltensweisen von Agenten für die Abläufe in einem System eingeführt. Danach erfolgt eine Beschreibung des standardisierten Referenzmodells, welches den grundlegenden Aufbau von Multiagentensystemen darstellt. Dieses wird für die Konzeption des zu entwickelnden Systems verwendet. Der folgende Abschnitt gibt einen Überblick vom Einsatzspektrum der Agententechnologie. Das Kapitel schließt mit einer Erläuterung des Anwendungsgebietes der Schedulingprobleme ab.

2.1 Definition Agent

Der in dieser Arbeit betrachtete Begriff Agent ist aus dem Gebiet der künstlichen Intelligenz. Das Wort „Agent“ stammt vom lateinischen Substantiv „ agens “ und bedeutet „Handelnder“. Es existiert bisher keine eindeutige und allgemein anerkannte Definition des Agentenbegriffes. Als Begründung dafür ist der interdisziplinäre Charakter der Agenten in den unterschiedlichen Wissenschaftsgebieten und der Praxis zu nennen. Eine weit akzeptierte Definition ist die folgende von Rüssel und Norvig [RN10]:

„Ein Agent ist eine Einheit, von der man sagen kann, dass sie ihre Umwelt über Sensoren wahrnimmt und sie mit Hilfe von Effektoren beeinflusst.“

(Rüssel und Norvig, 1996)

Somit stellt das Agentenverhalten aus mathematischer Sicht eine Abbildung der akzeptierten Situationen oder Wahrnehmungsfolgen auf ausführbare Handlungen dar. Trotz unterschiedlicher Begriffsdefinitionen gibt es einen gewissen Konsens über die Eigenschaften von Agenten. Eine Reihe von Autoren, unter anderem auch Wooldrige und Jennigs, beschreiben verschiedene Eigenschaften, um einen Agenten zu charakterisieren [WJ95].

Eine Auswahl der wesentlichen Agenteneigenschaften:

- Autonomie:

Agenten operieren ohne direktes Eingreifen von Benutzern und besitzen eine gewisse Kontrolle über die eigenen Aktionen sowie inneren Zustände. Sie treffen selbstständig Entscheidungen.

- Soziale Fähigkeiten:

Agenten interagieren mit anderen Agenten oder Diensten und führen Lösungen für gemeinsame Probleme kooperativ durch. Die Kommunikation erfolgt auf einer semantischen Serviceebene, sodass die Agenten von Aufforderungen, Angeboten und Anfragen getrieben sind.

- Reaktivität:

Agenten nehmen die Umgebung wahr, reagieren rechtzeitig und in einer angebrachten Art und Weise auf Veränderungen. Unter Umgebung wird alles verstanden, mit dem der Agent interagiert. Das sind z. B. Anwender über eine graphische Benutzeroberfläche, eine virtuelle Welt oder eine Ansammlung anderer Agenten.

- Kommunikation:

Die Fähigkeit des Agenten ermöglicht die Verständigung mit Benutzern und insbesondere mit anderen Agenten über eine Agentenkommunikationssprache.

- Mobilität:

Den Agenten ist es möglich, sich selbst oder durch einen weiteren Agenten im Netzwerk zu bewegen und somit die physische Position zu ändern.

- Adaption:

Die Agenten lernen aufgrund von Erfahrungen, Beobachtungen oder zuvor getätigten Entscheidungen und verbessern dadurch das eigene Verhalten.

- Robustheit:

Äußere und innere Störungen werden durch entsprechendes Verhalten kompensiert.

- Kollaboration:

Agenten beauftragen andere Agenten, starten oder überwachen Prozesse und reagieren auf Ergebnisse. Ziele werden durch Zusammenarbeit und Verhandlungen mit anderen Agenten erreicht.

- Intelligenz:

Der Agent erfüllt die ihm gestellten Aufgaben durch eigenes logisches „Denken“. Das geschieht mittels einer Menge von Regeln.

Der Agent ist ein Beauftragter mit Handlungsvollmacht. Zur Erfüllung seiner Aufgaben besitzt er verschiedene Fähigkeiten. Der Agent unterstützt den Benutzer und übernimmt in dessen Auftrag mehrere Arbeiten. Die Eigenschaften eines Agenten bestimmen den Grad an Unabhängigkeit bzw. Autonomie. Eingriffe in das Agentenverhalten durch äußere Einflüsse zur Einschränkung der Autonomie oder Veränderungen der Entscheidungskriterien sind möglich. Zu beachten ist, dass ein Agent meist ein beschränktes Wissen über die Umgebung besitzt. Auf die Agenteneigenschaft Intelligenz wird im Folgenden näher eingegangen, um den Unterschied zwischen Agent und intelligenter Agent zu verdeutlichen.

Definition intelligenter Agent

Ein intelligenter Agent besitzt eine künstliche Intelligenz (KI). Diese befähigt den Agenten, neuartige Situationen zu bewältigen. Die Intelligenz steht in Bezug zur Erfassung und Bewertung von Gegebenheiten sowie zum Erkennen von Zusammenhängen und zum Anwenden von entsprechenden Reaktionen. Das Agentenverhalten folgt vordefinierten und erlernten Regeln. Weiterhin lassen sich dem Agenten bestimmte Ziele und Befehle vorgeben.

Hayes-Roth definiert intelligente Agenten wie folgt [Hay95]:

„Intelligente Agenten führen kontinuierlich drei Funktionen aus: die Wahrnehmung von dynamischen Bedingungen der Umwelt; die Ausführung von Aktionen, um die Umwelt zu beeinflussen; und logisches Denken, um die Wahrnehmungen zu interpretieren, Probleme zu lösen, Schlussfolgerungen zu ziehen und Aktionen festzulegen.“

(Barbara Hayes-Roth, 1995)

Somit zeichnen sich intelligente Agenten durch Wissen und Lernfähigkeit aus sowie der Eigenschaft Schlussfolgerungen zu ziehen. Der Agent repräsentiert die Ziele und Wünsche des Anwenders und wendet erhaltenes Wissen an. Intelligente Agenten werden oft durch die zusätzlichen Eigenschaften „Rational“ und „Allwissend“ charakterisiert. Rationale Agenten agieren stets durch die Aktionen, welche den größten Erfolg bewirken. Dies ist für kritische Systeme entscheidend. Ein allwissender Agent kennt die Resultate der Aktionen bereits im Voraus. Abbildung 2.1 zeigt die verschiedenen Einflüsse auf die Eigenschaften eines Agenten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Einflussgebiete von Agenten (Vgl. [BZW98])

Kategorien von Agenten

Die Agenten lassen sich in drei Kategorien einteilen: Menschliche Agenten, Hardware Agenten und Software Agenten. Alle Agententypen führen Aufgaben für die Auftraggeber selbstständig aus. Oft sind dafür spezielle Kenntnisse und Fähigkeiten notwendig. Beispielsweise erwartet ein Kunde von einem Reisebüro, dass alle mit der Buchung der Reise verbundenen Aufgaben zuverlässig und selbstständig ausgeführt werden. Dazu gehört das Sammeln und Vergleichen von unterschiedlichen Angeboten sowie das Abstinnnen auf die Kundenwünsche. Roboter übernehmen Aufgaben von Menschen, Z. B. in lebensfeindlichen Umgebungen.

Suchmaschinen unterstützen den Benutzer bei der Informationsermittlung. In Abbildung 2.2 ist diese Klassifikation dargestellt. Diese Konzepte lassen sich auf die anderen Agentenkategorien übertragen. Im weiteren Verlauf dieser Arbeit erfolgt die Betrachtung ausschließlich für Softwareagenten, die in einer vernetzten, digitalen Welt im Auftrag eines Benutzers selbstständig Aufgaben bearbeiten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Kategorien intelligenter Agenten (Vgl. [BZW98])

Es existieren viele verschiedene Agentenarchitekturen zur Beschreibung des Typs, der Art und Weise sowie der Definition und Verwaltung des Agentenverhaltens. Diese bilden das zentrale Element, das Entscheidungsmöglichkeiten, Wissensbasis und Aktionen der Agenten definiert. Im Anhang A.l werden mehrere Agentenarchitekturen benannt, für die es bisher keine Standardisierung gibt.

2.2 Arten von Softwareagenten nach Russel und Norvig

Die Agenten lassen sich auf verschiedene Weise klassifizieren. Eine einfache Einteilung erfolgt auf Grund der Funktion in einem System [GOWOO]. Dies führt zu einer Aufschlüsselung mit vielen verschiedenen Agentenklassen. Diese allgemeine Kategorisierung ermöglicht zudem keine Erkennung der Komplexität und der Eigenschaften eines Agenten. Eine allgemein anerkannte Klassifizierung ist die von Russel und Norvig. Die Agenten werden in fünf verschiedene Gruppen eingeteilt, basierend auf deren Fähigkeiten und dem Grad der Intelligenz [RN 10]. Dabei besitzt eine Gruppe von Agenten stets die Eigenschaften der untergeordneten Gruppen. Die aufgelisteten Agentenarten werden im Folgenden erläutert:

- Einfacher Reflexagent
- Modellbasierter Reflexagent
- Zielgesteuerter Agent
- Nutzenorientierter Agent
- Lernender Agent

Die prinzipielle Funktionsweise wird durch den Skeleton Agent beschrieben. Bei jeder Aktivierung des Agenten aktualisiert dieser das interne Modell, um die gegenwärtige Situation zu reflektieren. Daraufhin erfolgt die Wahl der besten Aktion. Somit erfolgt eine schrittweise Verarbeitung des Agenten, um von einer Situation zur nächsten zu gelangen.

Einfacher Reflexagent

Der einfache Reflexagent reagiert nur auf Grundlage der aktuellen Wahrnehmung. Zustände aus der Vergangenheit werden nicht mit in die Entscheidungsfindung einbezogen. Die Wahrnehmung wird interpretiert und mit Hilfe eines Modells verarbeitet. Die Handlungsweise des Reflexagents basiert rein auf Bedingungs- und Aktionsregeln.

Ein Reflexagent sammelt Informationen über den aktuellen Zustand. In einer Erweiterung besitzt der Agent ein Gedächtnis und speichert Informationen über die Umgebung und bereits ausgeführte Aktionen. Die Bedingungs- und Aktionsregeln werden dann auf dieses Gesamtbild angewendet.

Werden einfache Reflexagenten in nur teilweise beobachtbaren Umgebungen eingesetzt, treten oft Endlosschleifen auf und der Agent erreicht nicht sein Zieh Die Schleifen im Agentenverhalten lassen sich durch Zufall beeinflusste Handlungen unterbrechen. In Abbildung 2.3 ist der Aufbau des Agenten dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Funktionsweise des einfachen Reflexagenten nach [RN10]

Modellbasierter Reflexagent

Ein modellbasierter Reflexagent findet sich in einer nur teilweise beobachtbaren Umgebung zurecht. Der Agent besitzt ein internes Modell, das auf den zuvor gespeicherten Erfahrungen beruht und auch den bisher nicht beobachteten Teil der Umgebung repräsentiert. Die Entscheidungsfindung für die Aktionen des Agenten wird wie beim einfachen Reflexagenten auf der Grundlage des Modells und dem aktuellen Zustand gewählt. Im Unterschied zum einfachen Reflexagenten werden dabei frühere Wahrnehmungen mit einbezogen und unbeobachtete Teile der Umgebung berücksichtigt. Weiterhin beachtet der in Abbildung 2.4 abgebildete Agent die durch seine Aktion entstehende Änderung in der Umgebung. Die Planung von Aktionen und schließlich auch zielgerichtetes Handeln werden dadurch möglich.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Funktionsweise des modellbasierten Reflexagenten nach [RN10]

Zielgesteuerter Agent

Zielgesteuerte Agenten sind modellbasierte Agenten mit der zusätzlichen Eigenschaft zielgerichtete Informationen für die Entscheidungsfindung einzubeziehen. Zielinformationen beschreiben Situationen, die der Agent bevorzugt. Diese unterstützen den Agenten bei der Auswahl der Reaktion zwischen mehreren Möglichkeiten. Es wird die Reaktion gewählt, welche dem eigentlichen Ziel des Agenten am nächsten kommt. Suchen und Planen sind Bestandteile dieser Agentenart, um durch künstliche Intelligenz eine Folge von Aktionen zu berechnen, die zum Erreichen des Ziels führen.

In nur teilweise beobachtbaren Umgebungen erscheint die Handlungsweise des zielgesteuerten Agenten ineffizient. Die Ursache dafür ist die Unvollständigkeit der Informationen über die Umgebung und deren dynamischer Veränderung. Dieser Agent reagiert durch seine Fähigkeiten sehr flexibel. Abbildung 2.5 zeigt die Struktur des Agenten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Funktionsweise des zielgesteuerten Agenten nach [RN10]

Nutzenorientierter Agent

Der nutzenorientierte Agent erweitert die Fähigkeiten des zielgerichteten Agenten. Zielgerichtete Agenten unterscheiden nur zwischen Zielzuständen und Nicht-Zielzuständen. Nutzenorientierte Agenten definieren zusätzlich den Grad der Nützlichkeit eines Zustandes und ermitteln diesen über eine so genannte Fitnessfunktion. Durch diese zusätzliche Fähigkeit unterscheidet der in Abbildung 2.6 dargestellte Agent detaillierter zwischen verschiedenen Situationen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6: Funktionsweise des nutzenorientierten Agenten nach [RN10]

Lernender Agent

Ein lernender Agent operiert zunächst in einer unbekannten Umgebung. Durch Erkunden lernt der Agent die Umgebung kennen und erstellt ein Modell. Die zwei Hauptfähigkeiten des Agenten sind das selbstständige Lernen, um die Grundlage für die Entscheidungsfindung zu verbessern und die Ausführung von Handlungen, damit die definierten Ziele erreicht werden.

Die Lernfähigkeit benötigt eine Rückmeldung über den Nutzen der Aktion, um das interne Modell zu ändern und die zukünftigen Handlungen zu verbessern. Eine weitere Komponente, welche die Entscheidung der Aktion des Agenten beeinflusst, ist das Bedürfnis neue Erfahrungen zu sammeln. Es ist notwendig, nicht nur Aktionen auszuüben, die zielgerichtet sind, sondern auch Tätigkeiten auszuführen, um neues Wissen zu erlangen. In Abbildung 2.7 ist die prinzipielle Funktionsweise des Agenten dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.7: Funktionsweise des lernenden Agenten nach [RN10]

2.3 Eigenschaften einer Agentenumgebung

Die Agenten befinden und interagieren stets in der Agentenumgebung. Als Umgebung wird alles verstanden, mit dem der Agenten interagiert. Die virtuelle Agentenumgebung definiert die Bedingungen für das Existieren und Wirken der Agenten. Zur Erlangung und Veränderung der Informationen stellt die Umgebung entsprechende Dienste bereit [OPF+Ol]. In Abhängigkeit der gegebenen Bedingungen erhalten die Agenten angepasste Fälligkeiten, um Aufgaben zu erfüllen. Im Folgenden werden die verschiedenen Eigenschaften der Agentenumgebung erläutert [Kue09]:

Zugänglich - Unzugänglich

Eine Umgebung ist für das Verhalten eines Agenten zugänglich, wenn alle relevanten Informationen für die auszuführende Aktion durch Sensoren erfasst werden. Falls die Umgebung unzugänglich ist, lassen sich nicht alle Informationen durch Sensoren ermitteln. Ein Ausgleich durch interne Zustände ist möglich.

Deterministisch - Stochastisch

Aus Sicht des Agenten wird bei einer deterministischen Umgebung der nächste Zustand vollständig durch den gegenwärtigen und die ausgewähhe Aktion festgelegt. In stochastischen Umgebungen lässt sich der nächste Zustand nicht Vorhersagen. Dabei kommt es vor, dass eine Umgebung stochastisch erscheint, wenn diese nicht zugänglich ist.

Episodisch - Sequentiell

Eine episodische Umgebung ist in Wahrnehmungs- und Handlungsabläufe unterteilbar. In einer Episode ist die Leistung des Agenten nicht von der vorangegangenen Episode abhängig. Entscheidungen lassen sich unabhängig voneinander treffen. In einer sequentiellen Umgebung beeinflusst eine Entscheidung alle nachfolgenden Wahrnehmungen und Aktionen.

Diskret - Kontinuierlich

In einer diskreten Umgebung enthält der Walirnehmungs- und Handlungsraum des Agenten eine endliche Menge von klar gegeneinander abgrenzbaren Zuständen. Anderenfalls agiert der Agent in einer kontinuierlichen Umgebung.

Statisch - Semidynamisch - Dynamisch

Eine dynamische Umgebung kann sich während der Aktionsfindung des Agenten verändern. Dadurch erbringen die Aktionen des Agenten unter Umständen nicht den gewünschten Effekt. Die Entscheidungsdauer ist daher so gering wie möglich zu halten. Im Gegensatz dazu verändert sich eine statische Umgebung während der Aktionsfindung nicht und lässt sich vollständig durch den Agenten kontrollieren. Wenn sich die Umgebung nicht verändert, aber das Verhalten des Agenten von einer Zeit abhängt, dann wird die Umgebung semi dynamisch genannt.

2.4 Multiagentensystem

Ein Agentensystem besteht aus einem Agent, der mit seiner Umgebung interagiert und Aufgaben löst. Ein Multiagentensystem (MAS) entsteht erst dann, wenn mehrere Agenten innerhalb eines festgelegten Rahmens miteinander interagieren. Das Wissen von Agenten und der KI lässt sich daher auf MAS und verteilte künstliche Intelligenz (VKI) übertragen. Bond und Gasser beschreiben MAS wie folgt [BG98]:

„Multi-Agenten Systeme beschäftigen sich mit der Koordination intelligenten Verhaltens einer Anzahl von autonomen, intelligenten Agenten: der Aufgabe, wie sie ihr Wissen, ihre Ziele, Fähigkeiten und Pläne vereint einsetzen können, um Probleme zu lösen.“

(Bond und Gasser, 1998)

Somit ist es möglich, dass ein MAS aus mehreren gleichartigen oder unterschiedlich spezialisierten Softwareagenten besteht. Die einzelnen Agenten werden dabei als abgrenzbare Einheiten verstanden, welche zugewiesene Aufgaben autonom und bei Bedarf in Kooperation mit anderen Agenten bewältigen. Die Kooperation ermöglicht zudem verschiedene Aufgabenstellungen zu bearbeiten. Durch intelligentes

Verhalten erfolgt eine Koordination und Organisation der einzelnen Agenten. Dabei werden deren Ziele und Fälligkeiten sowie das spezifische Wissen genutzt und als Einheit abgestimmt, Ulli in Kooperation die übertragenen Aufgaben zu lösen. Die dafür auszuführenden Aktionen sind im Ablauf zu planen und zu koordinieren. Dabei ist darauf zu achten, dass nicht mehrere Agenten unabsichtlich gleiche oder gegenseitig behindernde Aktionen ausführen. Das Lösen von Zielkonflikten geschieht durch Verhandlungen oder entsprechende Koordination. Sämtliches Verhalten von den intelligenten Agenten ist autonom zu gestalten. Meist wird ein MAS in Gruppen von Agenten eingeteilt, sodass eine hierarchische Struktur entsteht [Schoo]. Einige Agenten steuern daher mehrere Hilfsagenten, Ulli eine Aufgabe entsprechend zu bearbeiten. Für die Interaktion der Agenten ist eine Plattform sowie eine Kommunikationssprache nötig.

MAS sind selbstorganisierende Systeme. In der Systemtheorie bezeichnet dies eine Form der Systementwicklung, wobei die formgebenden, gestaltenden und beschränkenden Einflüsse von den Elementen selbst ausgehen. Ein selbstorganisierendes MAS besitzt eine hohe Flexibilität. Solche Systeme lassen sich auf einfache Weise erweitern, ändern und rekonstruieren, ohne dass die Anwendung detailliert zu modifizieren ist. In der Regel neigen MAS dazu, fehlertolerant zu sein. Die hohe Redundanz von Komponenten und die selbstorganisierenden Fähigkeiten sind auf allen Hierarchieebenen des Systems vorhanden. Dies ermöglicht es, Aufgaben flexibler und zuverlässiger zu erfüllen als ein einzelnes, lokales System. Selbstorganisation zeichnet sich durch die folgenden vier Eigenschaften aus:

- Komplexität: Die einzelnen Teile des Systems beeinflussen sich wechselseitig, wodurch eine Vorhersage des Systemverhaltens erschwert wird.
- Selbstreferenz: Jedes Element beeinflusst sich selbst mit dem eigenen Verhalten über mehrere Stellen im System.
- Redundanz: Es gibt keine Trennung zwischen koordinierenden, organisierenden und steuernden Teilen.
- Autonomie: Die Strukturen zur Interaktion und Kooperation werden selbstständig aufgebaut.

Der Nachteil von MAS bestellt in der aufwendigen Organisation und Kommunikation der Agenten. Demgegenüber stellen unter anderem die folgenden positiven Eigenschaften [BZW98]:

- Parallelität: Aufgaben werden zeiteffizienter berechnet.
- Robustheit: Bei veränderten Bedingungen bleibt die Funktionsfähigkeit des Systems erhalten.
- Skalierbarkeit: Durch Hinzunahme von weiteren Elementen wird die Leistungsfähigkeit gesteigert.
- Integration mehrerer Wissens- und Aktivitätsquellen: Jeder Agent bringt seine Leistung in die Gemeinschaft ein.
- Auflösung von Interessens- und Zielkonflikten: Die Agenten verhandeln selbstständig miteinander.
- Redundanz: Ausfälle von Teilsystemen werden kompensiert.
- Verteiltheit: Das System besitzt eine dezentrale Struktur.
- Getreue Abbildung eines Systems: Komplexe Systeme lassen sich detailgetreu nachbilden und analysieren.

Nach [BZW98] lassen sich Agentensysteme anhand der drei grundlegenden Eigenschaften klassifizieren: Anzahl der Agenten im System, Fähigkeit zur Mobilität und Grad der Intelligenz der Agenten, siehe Abbildung 2.8.

MAS treten überwiegend in der Biologie auf und werden in der Technik verwendet. Beispielsweise stellen Tierschwärme eine Gruppe von natürlichen MAS dar. Diese sind ein Vorbild bei der Optimierung technischer Prozesse. Im Bereich der Technik wird KI zur Steuerung genutzt.

Abbildung in dieser Leseprobe nicht enthalten

2.5 Emergenz im Multiagentensystem

VKI beschäftigt sich unter anderem mit Emergenz im MAS. Emergenz beschreibt das Entstehen neuer Strukturen oder Eigenschaften aus dem Zusammenwirken der Elemente in einem komplexen System. Dabei werden die Eigenschaften eines „Ganzen“ als emergent bezeichnet, welche sich aus den einzelnen „Teilen“ nicht direkt herleiten lassen und nur aus dem Zusammenwirken der Elemente, d. h. aus dem Prozess heraus, erklärbar sind [UP 10]. Ein zusannnengewachsenes System leistet somit mehr als die Summe der einzelnen Elemente. Das Zusammenwirken der spezialisierten Handlungsweisen übertrifft die Möglichkeit der individuellen Systemelemente.

Bei emergenten Systemen haben sich für die einzelnen Elemente folgende Eigenschaften herausgestellt [Fer99]:

- Durch die Handlungen eines Teilnehmers werden globale Effekte erreicht.
- Ein Teilnehmer besitzt oft keine globale Sicht auf das System.
- Die Koordination erfolgt meist ohne zentrale Steuerung.
- Das emergente System ist robust gegenüber dem Ausfall einzelner Teile.

Die Auswirkungen des Verhaltens auf der Mikroebene sind erst auf der Makroebene sichtbar. Aus diesem Grund ist in der VKI das so genannte Mikro-Makro-Problem von zentraler Bedeutung [Hİİ99]. Es bezieht dabei die Koordination der einzelnen Elemente und Skalierbarkeit des Systems mit ein. Bekannte, natürliche Emergenzen sind Ameisenkolonien und Vogelschwärme. Durch das Zusammenwirken der einzelnen Lebewesen über das soziale Verhalten, gelingt es komplexe Aufgaben zu bewältigen. Der Informationsaustausch zwischen den Mitgliedern einer Gruppe bietet einen evolutionären Vorteil gegenüber anderen Lebewesen [Kro09].

Die zentrale Aufgabe der VKI besteht in der Modellierung von Agenten, die soziale Fähigkeiten besitzen. Ausgehend von der Definition des Agenten in Abschnitt 2.1 stehen diese in Wechselwirkung mit der Umgebung. Das Lösen von Aufgaben erfordert gegebenenfalls verschiedene Spezialisierungen, welche von einem Agenten nicht allein erfüllt werden. Dies führt jedoch oft nur zu einer Zerlegung des Problems in mehrere Teile. Für die Entstehung von Emergenz und sozialem Verhalten ist neben den Eigenschaften von Agenten die Kommunikation entscheidend.

Aus diesem Grund ist die Kooperation der Agenten eines der wichtigsten Aspekte der VKI. In [Fer99] werden die folgenden Hauptvorteile herausgestellt:

- Bearbeitung von Aufgaben, die ein Agent nicht alleine bewältigt
- Steigerung der Produktivität eines jeden Agenten
- Erhöhung der Anzahl abgearbeiteter Aufträge in einer bestimmten Zeit

Demzufolge sind die Agenten mit Eigenschaften auszustatten, sodass ein emergentes Verhalten möglich ist. Agenten übernehmen Aufgaben, um ein übergeordnetes Ziel zu verfolgen. Dies stellt die Mikro-Ebene im MAS dar. Die daraus entstehenden Fähigkeiten des zusammengesetzten Systems bilden die Makro-Ebene.

2.6 Rollenmodell

Für die Modellierung eines Softwaresystems existieren verschiedene Ansätze. Das in dieser Arbeit eingesetzte Schema basiert auf dem so genannten Rollenmodell. Dieses Konzept ist im Kontext der modellgetriebenen Architektur jedoch nicht standardisiert [RWL95]. Beim Rollenmodell übernehmen einzelne Teile eines Systems verschiedene Funktionen. Das herkömmlich verwendete Dienstmodell beschreibt dagegen die Fähigkeit einer Instanz, bestimmte Aufgaben zu erledigen. Der Dienst ist an die Instanz und nicht an eine Aufgabe gebunden. Dies ist mit der Suche eines Agenten nach einem Auftrag vergleichbar. Im Unterschied zum Dienst bietet die Instanz einer Rolle an, Aufgaben im Rahmen der Verfolgung eines übergeordneten Ziels zu übernehmen. Anhand des Beispiels bedeutet dies, dass die Agenten ihre Fähigkeiten anbieten und entsprechende Aufträge erhalten. In beiden Fällen ist jedoch über eine öffentliche Ausschreibung passiv danach zu suchen. Die Modelle definieren sich daher über das Element, welches die aktive Suche vornimmt.

Im Kontext der agentenorientierten Softwareentwicklung existieren verschiedene Definitionen des Rollenbegriffs. Ferber definiert den Begriff der Rolle wie folgt [Fer99] :

„Die Rollen beschreiben die Positionen der Agenten innerhalb einer Organisation zusammen mit den Aktivitäten, die von ihnen erwartet werden, damit die Organisation ihre Ziele erreicht.“

(Jacques Ferber, 2001)

Damit ist die Rolle als eine Fähigkeit mit Rechten und Pflichten charakterisiert, welche von dem jeweiligen Agenten übernommen werden. Es gibt dabei die Unterscheidung zwischen fester und dynamischer Rollenzuweisung. Im Unterschied zur festen Zuweisung, ändert sich bei der dynamischen Zuweisung die Rolle während der Laufzeit. Es ist möglich, dass eine Instanz mehrere Rollen einninnnt. [RWL95]

Die von einem Agenten angebotenen oder angeforderten Dienstleistungen lassen sich als die Menge der Fähigkeiten und Leistungen zusammenfassen. Abbildung 2.9 verdeutlicht den Unterschied zwischen Dienst und Rolle, so wie diese von den Agenten auf der Multiagentenplattform gehandhabt werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.9: Unterschied zwischen Dienst und Rolle (Vgl. [Lid07])

Die Vorteile des Rollenmodells bestellen in seiner Flexibilität und Allgemeingültigkeit. Der Entwickler eines Systems erhält mehr Freiheit in der Modellierung und Umsetzung. Es lassen sich auf einfache Weise konkrete Organisationsformen und Aufgabenverteilungen Umsetzen. Andererseits sind für das Modell intelligente Agenten notwendig, Ulli entsprechende Strukturen zu entwickeln. Im Rollenmodell gibt es keine zentrale Einheit, welche die Agenten dirigiert. Es gibt keine vordefinierte Hierarchie und es lassen sich beliebige Ordnungen abbilden. Dies führt unter anderem zur Entstehung von Kommunikations-, Koordinations­mid Organisationsproblemen. Zur Lösung werden unter anderem soziologische Theorien adaptiert, die das Verhalten eines Individuums in einer Gesellschaft, die Gruppendynamik, die Gruppenbildung und die Gruppenorganisation beschreiben [Hİİ99]. Für das in dieser Arbeit zu entwickelnde MAS wird eine speziell für die Problemstellung angepasste, dynamische Struktur erstellt.

Das zu entwickelnde MAS basiert vollständig auf dem Rollenmodell. Jeder Agent im MAS bekommt eine oder mehrere Rollen fest zugewiesen. Auf der Suche nach der Lösung für eine Aufgabe ermitteln die Agenten über mehrere Bearbeitungsschritte hinweg bestimmte Rollen. Wenn die Fähigkeiten des Agenten mit denen von der geforderten Rolle übereinstimmen, ist der Agent in der Lage die Aufgabe zu übernehmen. Dabei kann der Fall auftreten, dass eine Rolle von mehreren Agenten erfüllt wird oder eine Aufgabe durch mehrere Agenten parallel zu bearbeiten ist. Dann muss der anfragende Agent selbstständig eine entsprechende Entscheidung treffen. Dabei haben die Agenten die Möglichkeit, miteinander zu verhandeln.

2.7 Referenzmodell für Agentenplattformen

Die Stiftung für intelligente, physische Agenten (FIPA; engl. Foundation for Intelligent Physical Agents) ist ein Standardisierungsgremium für Agenten und Agentensysteme [Odellá]. Die FIPA wurde 1996 in der Schweiz als eine nicht gewinnorientierte Organisation gegründet. Ihr Anliegen besteht in der Entwicklung von Softwarespezifikationen für heterogene und interagierende Agenten sowie Multiagentensysteme. Daher befasst sich die Stiftung im Detail mit der Kommunikation, Interaktion und dem Management von Agenten sowie dem Transport von Agentennachrichten. Dazu gehört die Standardisierung von Agentenplattformen, welche die einzelnen Agenten ausführen. Darüber hinaus erfolgen Festlegungen zur Interoperabilität von Agentenarchitekturen mit anderen Netzwerkarchitekturen. Die von der FIPA am meisten angewandte Spezifikation ist die des Agenten Managements und der Agenten Kommunikationssprache (ACL; engl. Agent Communication Language).

Um die Ergebnisse in einem weiter gefassten Kontext der Softwareentwicklung zu setzen und mit anderen Technologien zu verbinden, schloss sich die FIPA im Jahr 2005 dem weltweiten Berufsverband von Ingenieuren aus den Bereichen Elektrotechnik und Informatik (IEEE; engl. Institute of Electrical and Electronics Engineers) an. Zu den Mitgliedern der FIPA gehören unter anderem Firmen wie Boeing, Siemens und Toshiba, aber auch Forschungseinrichtungen wie die Rheinisch-Westfälische Technische Hochschule Aachen, die Universität Zagreb und die Queen Mary University von London.

Die zentralen Aspekte der FIPA Standardisierungsbemühungen betreffen grundsätzlich alle industriellen und kommerziellen Interessen, die zur Akzeptanz von agentenorientierten Systemen von Bedeutung sind. Zur FIPA Konformität gehört das Agenten Management Referenzmodell und das Agentenplattform Referenzmodell [Odellb]. Abbildung 2.10 verdeutlicht diese festgelegte Spezifikation. Die wesentlichen Komponenten des Modells werden im Folgenden einzeln charakterisiert^[1]. Agentenplattformen und die einzelnen Komponenten auf der Plattform sind über das Nachrichten Transport System verbunden. Agenten kommunizieren direkt mit weiterer Software, die nicht Bestandteil des MAS ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.10: FIPA-Specifikation: Agent Management Referenzmodell (Vgl. [Odellb])

Agenten Management System

Das Agenten Management System (AMS) dient zur Verwaltung der Agenten, welches White-Page Service genannt wird. Jede Plattform besitzt genau ein AMS. Alle Agenten auf der Plattform registrieren sich beim AMS und erhalten eine plattformübergreifende, eindeutige Agentenbezeichnung (AID; engl. Agenten Identifier). Diese setzt sich aus dem eindeutigen Namen des Agenten und der Adresse der Plattform zusammen. Das AMS überwacht den Lebenszyklus der Agenten und ermöglicht die Migration auf andere Plattformen. Dazu sind zueinander kompatible Plattformen notwendig. Dies wird durch die FIPA Spezifikationen festgelegt, sodass die Agenten sich stets in einer gleichen Umgebung befinden. In Abbildung 2.11 ist der Lebenszyklus eines Agenten auf der Plattform dargestellt. Es zeigt die Zustandsübergänge eines Agenten während dessen Existenz im MAS.

[...]

---

^[1] Weitere Details befinden sich auf der FIPA Website [Odella].