Lexikon

Multiagentensimulation

Voraussetzung für jede erfolgreiche Simulationsstudie ist, dass ein Modellierer einen Teil der Wirklichkeit so in einem Modell abbildet, dass das Modell diesen Ausschnitt für das Simulationsziel ausreichend genau widerspiegelt. Es gibt verschiedene Paradigmen und Techniken zur Formulierung eines Modells. Multiagentensimulation(auch agentenbasierte oder agentenorientierte Simulation) ist dabei eine relativ neue Form der Modellierung und Simulation, die gerade bei komplexen Modellen, z.B. von Gesellschaften, ihr Potential ausschöpfen kann.

Multiagentensimulation beruht auf der Formulierung des Modells als Multiagentensystem, d.h. als System, das aus interagierenden, autonomen Agenten besteht, in einer Umwelt, die ebenfalls Bestandteil des Modells ist. Das Spektrum agentenbasierter Modelle reicht dabei von Modellen, die nur auf einem abstrakten Konzept eines ,,Agenten“ beruhen, bis zu Modellen, die menschliche Akteure als intelligente Agenten nachbilden. Im Folgenden soll kurz behandelt werden, was unter einem Agenten bzw. Multiagentensystem zu verstehen ist, um darauf aufbauend die Prinzipien der Multiagentensimulation zu besprechen. Mittlerweile gibt es gute Lehrbücher im Bereich der Multiagentensysteme, auf die für eine ausführlichere Diskussion des Agentenbegriffs verwiesen werden kann (z.B. [7, 10], siehe auch [8]).

Im Prinzip ist ein Agent eine Einheit (Computerprogramm, Roboter, ...), die sich in einer Umwelt befindet und in der Lage ist in dieser autonome Aktionen durchzuführen, um ihre Ziele zu erreichen. Ein simulierter Agent ist also ein aktiver Bestandteil eines Modells. Er zeichnet sich durch verschiedene Merkmale aus [4]. Ein (simulierter) Agent

  1. verändert nicht nur sich selbst, sondern wirkt auf seine Umwelt und bleibt in dieser persistent. Aktionen geschehen dabei nicht nur als passive Antwort auf Umwelteinflüsse.
  2. agiert in Relation zu seiner Umwelt – er verändert sie nicht nur, sondern bezieht Information aus ihr.
  3. besitzt einen beschränkten Wahrnehmungs- und Aktionsradius (Lokalität).
  4. verfügt über ein nichttriviales Verhaltensrepertoire.

Ein Multiagentenmodell ist ein Multiagentensystem in einer simulierten Umwelt und virtuellen Zeit, das ein reales Multiagentensystem nachbilden soll. Es besteht damit aus mehreren Agenten. Durch ihr Verhalten und ihre Interaktionen untereinander und mit ihrer Umwelt entstehen Muster und Verhalten auf einer höheren, aggregierten Ebene. Organisationsstrukturen können dabei ebenfalls Bestandteil eines Modells sein. Besonders interessant – z.B. in sozialwissenschaftlichen oder biologischen Domänen – sind Simulationen, bei denen die Entstehung von Organisationsstrukturen oder sozialen Netzwerken auf der Basis der Agenteninteraktionen erklärt bzw. untersucht werden. Nicht nur in solchen Anwendungsgebieten ist die Interaktion zwischen den Agenten ein zentraler Aspekt eines Multiagentenmodells.

Ein weiterer nicht zu unterschätzender Teil eines Multiagentenmodells ist die simulierte Umwelt. Im Prinzip besteht die Umwelt für einen einzelnen Agenten aus den anderen Agenten des Multiagentensystems und aus weiteren Bestandteilen, die sowohl lokale als auch globale Phänomene beschreiben können: Ressourcen können dabei Einheiten sein, die zwar über eine eigene Dynamik verfügen, wie z.B. nachwachsende Rohstoffe, aber dennoch im Modell nicht aktiv sind, sondern passiv abgeerntet werden. Globale Eigenschaften, wie z.B. die Umgebungstemperatur, beeinflussen simulierte Agenten im gesamten System und müssen dementsprechend explizit modelliert werden. Das Umweltmodell stellt die Constraints für das Agentenverhalten, denn nur was in der Umwelt vorgesehen ist, kann auch wahrgenommen oder manipuliert werden. In Modellen adaptiver Agenten gibt die Umwelt oft auch das Ziel vor, an das sie sich durch evolutionäre Mechanismen oder ,,reinforcement“ Lernen entsprechend dem Feedback aus der Umwelt anpassen. Insbesondere in solchen Szenarien muss die Umwelt sorgfältig behandelt werden, da anderweitig schnell Artefakte produziert werden, die die Aussagekraft der Simulation schrumpfen lassen.

Worin unterscheidet es sich von anderen Simulationsansätzen?

Multiagentensimulation wird in einer wachsenden Zahl von Anwendungsgebieten benutzt. Dies sind teilweise Gebiete, in denen zuvor Simulationen nicht oder nur marginal angewendet wurden, aber auch Domänen, in denen sich bereits andere Simulationsparadigmen etabliert haben.

Die klarste Unterscheidung kann man zwischen Makrosimulation (Differentialgleichungsmodelle, System Dynamics, etc.) und agentenbasierter Simulation ziehen, da letztere eine Form der Mikrosimulation ist. Populationsgrößen oder andere Zustandsvariablen des Gesamtsystems werden durch die Simulation des Verhaltens und der Interaktion der einzelnen Bestandteile ersetzt. Eine Makrosimulation eines Bahnhofs besäße Zustandsvariablen, wie die Anzahl der aktuell Wartenden oder die aktuelle Fußgängerdichte. Anstatt Bewegungen zu behandeln, würden diese Variablen unter Annahme von Homogenität fortgeschrieben. In einer agentenbasierten Simulation kann man jeden Fußgänger individuellmit seinen Zielen und Wunschgeschwindigkeiten behandeln. Generell müssen Agenten keine Individuen sein, sondern können durchaus komplexere Einheiten mit Zustandsvariablen nachbilden. Interessant sind auch Mehrebenenmodelle (siehe [1]).

In eher technischen Anwendungsgebieten werden prozessorientierte Simulationsformen, wie Warteschlangenmodelle oder Petrinetze oder objektorientierte Simulationen eingesetzt.Während sich die agentenbasierte Simulation von ersteren vor allem dadurch unterscheidet, dass sie deutlich mehr Freiheitsgrade im Modelldesign zulässt (für eine ausführliche Diskussion siehe [5]), entspricht die Unterscheidung zwischen objektorientierter und agentenbasierter Simulation eher der Trennung zwischen objektorientierter und agentenorientierter Software. Multiagentensimulation ist auf einer konzeptionellen Ebene flexibler, das Bild eines Agenten unterstützt variable Interaktionen, Entscheidungsautonomie des Agenten, etc. Mitte der 90er Jahre war vor allem das Potential der agentenbasierten Simulation im Bereich der variablen Strukturen entscheidend für entsprechende Erweiterungen bekannter objektorientierter Ansätze. Modelliert man die Fußgänger in einer Bahnhofssimulation mit Warteschlangen ist es z.B. schwierig das Wechseln vonWarteschlangen vor Zugtüren oder das Umplanen von Wegen zu modellieren. Modelliert man mit Agenten, geht man von deren Entscheidungen in Reaktion auf die Strukturen der Umwelt aus; flexible Entscheidungen sind dadurch einfach zu modellieren.

Zelluläre Automaten [9] werden manchmal mit agentenbasierter Simulation gleichgesetzt. Es gibt aber Unterschiede, die agentenbasierte Ansätze flexibler zeigen: Die Basiseinheit eines zellulären Automaten ist eine räumliche Einheit, die mit für den gesamten Automaten einheitlichen Regeln auf der Basis der Zustände der Nachbarzellen den eigenen Zustand aktualisiert. Agenten in einem Multiagentensystem können völlig unterschiedliche Regelsätze besitzen, müssen nicht gleich groß sein, können sich im simulierten Raum bewegen usw. Letzteres würde bei einem zellulären Automaten die Zustandsänderung von mindestens zwei Zellen erfordern, was nur recht kompliziert gelöst werden kann. Zelluläre Automaten findet man häufig bei Multiagentensimulationen als Umweltmodell, um z.B. ein räumlich heterogenes Ressourcenwachstum abzubilden. In einer Fußgängersimulation mittels zellulären Automaten würde ein Fußgänger durch einen entsprechenden Zustand einer Zelle, der z.B. die Geschwindigkeit codiert, und nicht als Agent mit seinen individuellen Fähigkeiten repräsentiert. Zusammenfassend kann man sagen, dass die Multiagentensimulation über folgende Vorteile gegenüber traditionelleren Simulationstechniken verfügt:

  • Direkte und intuitive Modellierung flexibler und lokaler Interaktionen zwischen aktiven Einheiten – mit und ohne expliziter Repräsentation von Raum;
  • Vergleichsweise einfache Integration von mehreren Modellierungs- und Beobachtungsebenen;
  • Simulation von emergenten Phänomenen und Nicht- Linearitäten;
  • Einfache Behandlung von variablen Strukturen;
  • Beliebiger Detaillierungsgrad des Modells;
  • Angemessene Modellierung (intelligenten) menschlichen Verhaltens

Spezifische Aspekte der Multiagentensimulation

Selbstverständlich gibt es auch Aspekte bei der Multiagentensimulation, die besondere Sorgfalt und Methoden erfordern. Die wichtigsten sind die oft fehlende Verbindung zwischen Makro- und Mikroebene und – auch als Konsequenz daraus – der oft unklare Detaillierungsgrad auf der Mikroebene. Daneben gibt es eine Reihe von Problemen, die schon dadurch entstehen, dass Multiagentensimulationen schlichtweg größer sind als vergleichbare andere Simulationen. Diese drei Punkte werden im Folgenden näher ausgeführt:

Obwohl es als ein großer Vorteil der agentenbasierten Simulation gesehen wird, dass ein beobachteter Agent direkt als simulierter Agent modelliert wird, besteht dennoch oft Unsicherheit darüber, welches Verhalten auf der Mikroebene zum gewünschtenMakroverhalten passt. Meistens sind empirische Daten oder das zu untersuchende Phänomen auf der aggregierten Ebene messbar bzw. vergleichbar. Beispiele sind soziale Netzwerke oder Populationseigenschaften, die als nicht-lineares Phänomen aus der Interaktion der Agenten entstehen. Modelliert wird aber das lokale Agentenverhalten. Sind die Phänomene auf der aggregierten Ebene nicht direkt aus den Verhaltensweisen und Interaktionen der einzelnen Agenten ableitbar, sondern entstehen erst während der Simulation, spricht man von Emergenz. Die wichtigste Konsequenz ist dabei, dass es keinen Top-Down-Weg der Bestimmung des Agentenverhaltens gibt, d.h. das Agentenmodell kann nicht aus dem zu generierenden Phänomen der Makroebene abgeleitet werden. Stattdessen ist ein Bottom-Up-Verfahren notwendig, bei dem ausgehend von Theorien oder Beobachtungen die Agentenmodelliert werden, um dann zu testen, ob das erwünschte Phänomen in der Simulation beobachtet werden kann. Das bedeutet im Endeffekt, dass die Kreativität des Modellierers entscheidend ist. Oft entspricht dieses Bottom-Up-Vorgehen einem Try-And-Error-Verfahren.

Mit dem schwierigen Makro-Mikro-Link ist das Problem verbunden, den richtigen Detaillierungsgrad des Modells zu finden. Durch das freie Design ist prinzipiell jeder Detaillierungsgrad möglich. Allerdings ist das Einbauen von Details, nur weil man es kann, keine gute Modellierungsstrategie; sondern es sollte vom Ziel der Simulationsstudie ausgehend bestimmt werden. Jedes zusätzlich eingebaute Detail produziert zusätzliche Annahmen und Komplexität im Modell, die auf Kosten der Verständlichkeit, Analysierbarkeit und auch der praktischen Simulierbarkeit desModells gehen.

Wie oben erwähnt, ist eine Multiagentensimulation eines Phänomens meist aufwendiger als mit einem anderen Paradigma. Jeder einzelne Agent muss aktualisiert und im Speicher gehalten werden. Dabei ist das Verhalten der Agenten komplexer als das von Zellen oder von Elementen, die nur über einen Zufallsprozess gesteuert werden. Demzufolge ist der Aufwand an Speicher und Laufzeit höher, was man auch daran sehen kann, dass sich die Multiagentensimulation erst mit wachsender Leistungsfähigkeit der Rechner verbreitet hat. Ab einer bestimmten Größe des Modells spielt das konkrete Design und die Implementierung eine Rolle, zum Beispiel wenn die Simulation an die Grenzen der Speicherkapazität kommt oder die Laufzeit die Grenze des Erträglichen erreicht. Auch die Kalibrierung, d.h. das Einstellen der Modellparameter – die abhängig von dem Detaillierungsgrad des Modells sehr zahlreich sein können –, ist davon betroffen und erfordert innovative Ansätze, um mit möglichst wenigen Simulationsläufen eine sinnvolle Einstellung finden zu können.

Anwendungsgebiete und erfolgreiche Beispiele

Ein Hauptanwendungsgebiet der Multiagentensimulation ist die sozialwissenschaftliche Simulation. Gilbert und Troitzsch [1] bemerken sogar, dass sie dort mittlerweile das am häufigsten verwendete Simulationsparadigma ist. Abstrakte Theorien über gesellschaftliche Phänomene werden dabei ebenso getestet wie konkrete Szenarien zur Land- oder Wassernutzung. Man könnte an dieser Stelle eine Reihe sehr bemerkenswerter Modelle erwähnen, aus Platzgründen sei nur auf die Online-Zeitschrift JASSS (Journal of Arti.cial Societies and Social Simulation, jasss.soc.surrey.ac.uk/JASSS.html verwiesen.

Ebenso erfolgreich ist die Verwendung in der ökonomischen Simulation, von der Entscheidungsunterstützung bei Supply Chains bis hin zu Marktsimulationen. Auch die Modellierung von Fertigungssystemen oder Krankenhäusern mit agentenbasierter Simulation ist attraktiv und vorteilhaft (siehe [3]). Ein weiteres Anwendungsgebiet, in dem menschliches Entscheiden simuliert wird, ist die Verkehrssimulation. Dabei werden simulierte Fahrer oder auch Fußgänger mit Fähigkeiten ausgestattet, die eine intelligente Informationsverarbeitung und eine entsprechende Reaktion auf die aktuelle Situation ermöglichen. In der Biologie und Ökologie kann man Parallelen zwischen individuenbasierter und agentenbasierter Simulation finden [2]. Sie wird immer häufiger (und immer erfolgreicher) bei Simulationen von heterogenen Populationen, dynamischen Nahrungsbeziehungen etc. eingesetzt. Die größte Innovation, die agentenbasierte Simulation für die Biologie bietet, ist die Simulation der Evolution neuer Verhaltenscharakteristika und von individuellem Lernen. Auch in militärischen Anwendungsbereichen wurde agentenbasierte Simulation schon relativ früh eingesetzt, zu Trainingszwecken oder um Menschen in virtuellen Manövern zu ersetzen. Dabei liegt der Schwerpunkt auf der Glaubwürdigkeit der künstlichen Charaktere.

Ein wachsendes Einsatzgebiet der agentenbasierten Simulation findet man bei Computerspielen und in der Filmindustrie. Ein Beispiel mit großer Publizität war die Generierung von Massenszenen im zweiten Teil der ,,Herr der Ringe“-Trilogie. Die für die Modellierung individueller Agenten entwickelte Software MASSIVE (http://www.massivesoftware.com) wurde inzwischen in weiteren Filmen eingesetzt.

Auch in eher Standardanwendungsgebieten konnte die Multiagentensimulation überzeugen, z.B. bei der agentenbasierten Simulation der Ein- und Auslagerungsvorgänge in Hochregallagern zum Testen komplexer Kontrollsoftware [6]. Dabei war nicht die Genauigkeit der Abbildung der dynamischen Prozesse relevant, sondern die schnelle Erstellung und Verständlichkeit der Modelle. Ein weiteres – oft zitiertes – Beispiel für einen erfolgreichen Einsatz ist die Optimierung der Steuerung von Fracht bei der South West Airline (siehe www.nutechsolutions.com/).

Insgesamt kann man sagen, dass die Multiagentensimulation neue Möglichkeiten in bekannte Anwendungsgebiete bringt, aber auch neue Wege für die Simulation erschließt.

Literatur

1. Gilbert, N., Troitzsch, K.: Simulation for the Social Scientist. Open University Press (2005)

2. Grimm, V., Railsback, S.: Individual-based Modeling and Ecology. Princeton University Press (2005)

3. Kirn, S., Herzog, O., Lockemann, P., Spaniol, O. (eds.): Multiagent Engineering. Springer (2006)

4. Klügl, F.: Multiagentensimulation – Konzepte, Anwendungen, Tools. Addison Wesley (2001)

5. Klügl, F., Oechslein, C., Puppe, F., Dornhaus, A.: Multi-Agent Modelling in Comparison to Standard Modelling. Simul. News Eur. 40, 3–9 (2004)

6. Triebig, C., Credner, T., Klügl, F., Fischer, P., Leskien, T., Deppisch, A., Landvogt, S.: Agent-based Simulation of High-Bay Warehouses. In: Pechoucek, M. et al. (eds.) Multi-Agent Systems and Applications IV, Proc. of CEEMAS 2005, LNCS 3690, Springer, pp. 653–656

7. Weiss, G. (ed.): Multiagent Systems – a Modern Approach to Distributed Artificial Intelligence. The MIT Press (2000)

8. Weiss: Agentenorientiertes Software-Engineering. Informatik-Spektrum 24(2), (2001)

9. Wolfram, S.: A New Kind of Science. Wolfram Media Inc. (2001)

10. Wooldridge, M.: An Introduction to Multiagent Systems. John Wiley & Sons (2002)

Autorin und Copyright

Dr. Franziska Klügl
Universität Würzburg, Institut für Informatik
Am Hubland, 97074 Würzburg
E-Mail: kluegl@informatik.uni-wuerzburg.de

© Springer-Verlag 2006