Crowd Simulation

(Auch als PDF-Version verfügbar)

Inhaltsverzeichnis

  1. Kontinuierliche Simulation
  2. Diskrete Simulation:
    1. Zelluläre Automaten
    2. Partikelsysteme, Multiagentensysteme
  3. Verhaltensmodellierung:
    1. Anforderungen
    2. Implementierung
  4. Ausstattung der Umgebung:
    1. Aktionspunkte
    2. Anziehende und abstoßende Punkte
    3. Intelligente und interaktive Objekte
  5. Kollisionserkennung
  6. Wegsuche
  7. Kommunikation zwischen Individuen?
  8. Herdenbildung
  9. Gruppendynamik
  10. Kontrolle der Simulation
  11. Darstellung
  12. Weiterführende Adressen

Einleitung

Crowd Simulation, Artificial Life (AL) und Künstliche Intelligenz (KI)

Die Simulation eines aus einzelnen autonomen Individuen zusammengesetzten Systems gehört zum Kerngebiet der Simulation künstlichen Lebens (AL). Bei diesen Individuen, im Zusammenhang der Simulation oft auch als Agenten bezeichnet, kann es sich um Menschen, Tiere, Fahrzeuge oder auch generalisierte Gebilde wie Haushalte handeln. Charakteristisch für die Agenten ist ein Verhalten, das sich nicht allein durch Naturgesetze beschreiben läßt, sondern auch Methoden der KI erfordert.

Aufgrund des Fehlens allgemein anerkannt exakter Modelle zur Beschreibung solcher Systeme beschränkt sich die Überprüfung derartiger Simulationen meist nur darauf, ob sie im Rahmen der Erwartungen lauffähig ist und schlüssige Ergebnisse berechnet. Dafür ist in vielen Anwendungsbereichen die Echtzeitfähigkeit von großer Bedeutung. Die einer Crowd Simulation zugrunde liegenden Techniken und Regeln werden deshalb bevorzugt nach Effizienzkriterien ausgewählt. Von Vorteil ist, daß hierbei in vielen Fällen auf schon bewährte Algorithmen aus anderen Gebieten zurückgegriffen werden kann.

Bedarf

Die Simulation vieler zusammen agierender Individuen besitzt ein weitgefächertes Anwendungsspektrum:

Kontinuierliche Simulation

Zur Simulation von Gasen und Flüssigkeiten mittels (Differential-)Gleichungssystemen existieren schon länger ausgereifte und effiziente Verfahren mit einem soliden theoretischen Unterbau. Es liegt also nahe, diese auch zur Crowd Simulation einzusetzen. Nichtphysikalische Effekte müssen dabei durch Potentiale, Energien oder Felder nachgebildet werden.

Alle in der Praxis verwendeten Verfahren arbeiten auf einem in diskrete Zellen aufgeteilten Raum. Der Zustand einer Zelle gibt die Anzahldichte der darauf befindlichen Individuen und ggf. weitere Eigenschaften wie deren mittlere Geschwindigkeit wieder. In reinen Strömungssimulationen wird nur die unmittelbare Umgebung einer jeden Zelle in den dazugehörigen Berechnungen verwendet.

Die Stärken dieses kontinuierlichen Modells liegen in seiner umfangreichen Analysierbarkeit, was eine leistungsfähige Datenaufbereitung in Hinsicht auf Extremstellen, Mittelwerte, Schwankungen, etc. ermöglicht. Sich einstellende Gleichgewichte lassen sich berechnen, zudem läßt sich die Genauigkeit der Berechnungen (aber nicht des zugrundeliegenden Modells) exakt kontrollieren.

Diese Art der Modellierung eignet sich allerdings nur für wenige Einsatzgebiete, da sie das Konzept unabhängiger, verschiedener Individuen vollkommen ignoriert.

Diskrete Simulation

Zelluläre Automaten

Spätestens seit Conways "Game of Life" gehören zelluläre Automaten zu den Standardverfahren in der Imitation künstlichen Lebens. Auch hier wird ein in Zellen aufgeteilter Raum verwendet, der Zustand einer Zelle wird in jedem Zeitschritt mithilfe der benachbarten Zellen, also lokal, berechnet. Der Zellenzustand kann entweder wie im klassischen zellulären Automat nur aus diskreten Werten bestehen oder auch um kontinuierliche Werte und globale Parameter erweitert sein. Bei geeigneter Wahl der Zustände ist sogar die Nachbildung einzelner Individuen möglich. Komplexe Verhaltensweisen lassen sich allerdings nur mit übermäßig hohem Aufwand realisieren.

Beispiel: Verkehrssimulation mit 1D-Automat

Mit folgenden Regeln läßt sich eine einfache Verkehrssimulation durchführen:

Raum-Zeit-Diagramm eines 1D-Automatens

Jede Zeile entspricht einem Zeitschritt, der grün hervorgehobene Bereich stellt den Ausgangszustand dar. Schwarze Felder entsprechen einzelnen Fahrzeugen. Zum besseren Verständnis wurden die simulierte Bewegungen dreier einzelner Fahrzeuge sowie der Bereich einer sich auflösenden Verkehrsstockung nachträglich eingezeichnet. Die momentane Geschwindigkeit eines Fahrzeugs läßt sich an der horizontalen Komponente der blauen Linien ablesen.

Das obige Beispiel kann hier praktisch ausprobiert werden: Gesetzte Felder entsprechen den Fahrzeugen, pro Druck auf den Button wird ein Zeitschritt berechnet.

Diskrete Simulation

Partikelsysteme, Multiagentensysteme

Am flexibelsten sind Verfahren, die sich vom Konzept des Raumes lösen und stattdessen direkt einzelne Agenten simulieren. Diese können als Partikelsystem oder auch als ein System aus unabhängig voneinander berechneten Agenten (Multi Agent System) realisiert werden. Prinzipiell sind beide Verfahren gleich leistungsfähig. In der Praxis sind Partikelsysteme etwas effizienter zu implementieren, Agentensysteme dafür leichter um individuelle Eigenschaften und Funktionen erweiterbar.

Vereinfachungen

Der Raum auf dem sich die Agenten befinden ist zuerst einmal beliebig wählbar. Dies erlaubt reichhaltige Verhaltensweisen, vergrößert aber auch den Rechenaufwand für viele Aktionen enorm. Um dennoch viele Agenten gleichzeitig simulieren zu können, bietet es sich an, anstelle eines normalen Partikelsystems eine Partikelwarteschlange zu verwenden. Bei diesem werden nur noch diejenigen Agenten bearbeitet, bei denen eine bedeutende Zustandsänderung eintritt. Dazu ist allerdings ein Modell erforderlich, bei dem einzelne Agenten nicht in jedem Zeitschritt unbedingt aktualisiert werden müssen.

Eine beliebte Technik ist es, zusätzlich den Raum wieder in diskrete Zellen aufzuteilen und die dadurch entstehenden Nachbarschaftseigenschaften zur Verringerung des Rechenaufwands heranzuziehen. Mitunter wird ein auf diesem Raum arbeitender zellulärer Automat zur dynamischen Berechnung ortsgebundener Eigenschaften mit einem Partikel- oder Multiagentensystem kombiniert.

Diskretisierung des Raumes

Bei der Aufteilung des Raumes sind reguläre Gitter wegen der einfacheren Verwendung vorteilhaft. Verbreitet sind vor allem leicht in Ortskoordinaten umrechnenbare quadratische und kubische Gitter, da sie für frei bewegliche Objekte ideal sind. Im zweidimensionalen Fall sind auch hexagonale Unterteilungen sinnvoll: Diese kommen nicht nur der Kreisform am nächsten, sie haben darüber hinaus gegenüber rechtwinkligen Gittern den Vorteil, daß die Mittelpunkte aller umgebenden Felder gleich weit entfernt sind.

Verhaltensmodellierung

Anforderungen

Kernstück der realistischen Simulation eines Individuums ist die Nachbildung seiner Aktionen und Reaktionen. Diese basieren wiederum auf der Imitation von individuellen Zielen, Wahrnehmungen und Gefühlen. Für langfristige Aktionen kann es erforderlich werden, Wissen, Gedächtnis oder gar Lerneffekte mit zu berücksichtigen. Zusätzlich zu den selbsständig berechneten Verhaltensweisen ist es in vielen Fällen wünschenswert, das Verhalten mit Skripten zu erweitern oder gezielt von außerhalb interaktiv zu steuern.

Die Modellierung des Verhaltens kann auch Daten für die Darstellung liefern: Man denke nur an die Darstellung einer Begrüßung, die Wirkung verschiedener Gesichtszüge anhand der gerade vorherrschenden Emotionen und akustischen Informationen wie verschieden laute Schritte, Ausrufe oder Atemgeräusche.

Implementierung

Im wesentlichen gibt es drei verbreitete Verfahren zur Aktualisierung des Zustands eines Agenten:

Aus Gründen der einfacheren Entwicklung und besseren Effizienz bieten sich weitere Modifikationen an:

Beispiel einfachen Verhaltens: The Sims

Die einzelnen Personen in der Alltagssimulation "The Sims" baut im Wesentlichen auf folgendem Schema auf:

Haupteigenschaften

Grundalgorithmus

  1. Wähle zu verbessernden Zustand aus der Menge der Eigenschaften der Person aus
  2. Gehe zu Objekt oder anderer Person, welche diesen Zustand verbessern kann
  3. Führe dazugehörige Aktion aus
  4. Aktualisiere die durch die Aktion beeinflußten Zustände

Ausstattung der Umgebung

In der realen Welt stellt die Interaktion mit der Umgebung als auch mit anderen Individuen ein Hauptmerkmal des Lebens dar. Dies läßt sich modellieren, indem man einzelne Bereiche und Individuen um folgende Merkmale bereichert:

Aktionspunkte

Unter Aktionspunkten versteht man Objekte, die gezielt bestimmte Verhaltensregeln ansprechen. Vorhandene Ziele eines Agenten sind oftmals an spezielle Aktionspunkte gekoppelt. Je nach Bedeutung des Aktionspunktes kann dieser auch über Begrenzungen verfügen und, z.B. für einen Fahrstuhl, nur eine bestimmte Anzahldichte/Traglast gleichzeitig zulassen, so daß er nicht mehr allen Agenten gleichzeitig zur Verfügung stehen kann.

Anziehende und abstoßende Punkte

Außergewöhnlich interessante Objekte als auch solche, mit denen ein Kontakt wenig begehrenswert erscheint, lassen sich mit Hilfe attraktiver und abstoßender Potentiale erstellen. Üblich sind hierfür mit zunehmender Distanz asymptotisch monoton abfallende Funktionen, die als Maximum einen endlichen oder unendlichen Wert annehmen. Unendliche Werte stellen abstoßende Punkte, die nie erreicht werden sollen, oder Attraktoren, die wie ein Schwarzes Loch nicht mehr verlassen werden können, dar.

Die Gewichtung des Potentials kann je nach Agent variieren und sich von Verhaltensregeln gesteuert bei diesen dynamisch verändern - etwa, um nachlassendes Interesse an einem Gegenstand zu modellieren. Ein und dieselbe Funktion kann dadurch sowohl ein starkes als auch schwaches, anziehendes und abstoßendes Objekt zugleich simulieren.

Intelligente und interaktive Objekte

Tritt ein Agent mit einem Objekt in Kontakt, so kann sich neben dem Zustand des Agenten auch der des betreffenden Objekts ändern. Dies betrifft nicht nur die Interaktion zweier Individuen, sondern auch Objekte, die nicht beliebig oft aufgesucht werden können; aufsammelbare Gegenstände als auch jegliche Art von simulierten Automaten wie z.B. ein Fahrstuhl.

Es bietet sich an, nicht explizit zwischen passiven Objekten und Agenten zu unterscheiden. Dies vereinfacht den Systementwurf enorm, kann aber je nach Modellwelt den Rechenaufwand enorm steigern, da dann auch unveränderte passive Objekte in jedem Zeitschritt bearbeitet werden.

Kollisionserkennung

Damit eine Interaktion zwischen Objekten stattfinden kann muß zuerst einmal überprüft werden, ob sich diese an der gleichen Position befinden. Der naive Ansatz, für jedes Objekt die Distanz zu allen anderen Objekten zu prüfen führt zu quadratischem Gesamtaufwand, was nur für gering besiedelte Welten sinnvoll ist.

Im eindimensionalen Fall bietet es sich an, die Objekte anhand ihrer Position in einer Liste zu sortieren. Die Ermittlung der benachbarten Objekte eines Objektes ist damit in konstanter Zeit möglich. Unter der realistischen Annahme, daß sich die Objekte nicht beliebig schnell bewegen, läßt sich auch die jeweilige Listenposition in konstanter Zeit aktualisieren. Dies führt zu linearem Gesamtaufwand.

Ansonsten kann man die Welt wieder wie schon bei den zellulären Automaten in Zellen aufteilen. In jeder Zelle werden Verweise auf die darin befindlichen Objekte gespeichert, so daß für jeden Agent nur noch die Objekte in den benachbarten Zellen geprüft werden müssen. Für gleichverteilte Objekte ergibt sich ein linearer Gesamtaufwand. Wenn einzelne Zellen dicht besiedelt sind steigert sich dieser enorm, die Zellengröße sollte demnach so gewählt werden, daß stets nur ein kleiner Teil aller Objekte sich darin befinden wird.

Dieses Problem umgeht man, wenn jede Zelle nur ein einziges Objekt enthalten kann. Die dazu nötigen geringe Zellengröße führt allerdings zu enormer Zellenanzahl mit entsprechendem Speicherbedarf. Demnach empfiehlt sich dieses Verfahren vorwiegend für sehr dicht besiedelte Simulationen.

Baumstrukturen wie Quadtrees oder Octrees gehen dagegen stets effizient mit dem Speicherplatz um. Eine Änderung der Objektposition ist dafür mitunter vergleichsweise kostspielig; der Gesamtaufwand kann in ungünstigen Fällen bis zu quadratischer Ordnung anwachsen.

Wegsuche

Anforderungen

Ziel der Wegsuche ist es, einen möglichst optimalen Weg von einem Startpunkt zu einem Zielpunkt zu finden. Die Optimierungskriterien wie benötigte Zeit und Energie können sich bei verschiedenen Suchanfragen ändern, auch soll bei der Wegsuche das begangene Terrain auf Kriterien wie Höhenunterschiede und verschiedene Untergründe berücksichtigt werden. Idealerweise erfolgt die Wegsuche derart, daß unerwünschte Kollisionen mit anderen aktiven Objekten vermieden werden.

Implementierung

Gängige auf Zellen arbeitende Verfahren sind der A*- und der Duftstoff-Algorithmus. Beide beruhen auf der Wahl des lokalen Optimums. Während der A*-Algorithmus jedoch mit einer Schätzung des restlichen Weges arbeitet basiert der aufwendigere Duftstoff-Algorithmus auf der Rückwärtsverfolgung eines sich vom Zielpunkt ausbreitenden simulierten Lockstoffes.

Ein anderer Ansatz simuliert die Wahrnehmung der Agenten. Hierbei wird innerhalb von einem bestimmten Suchradius diejenige Richtung gewählt, die am günstigsten dem Ziel entgegen zu führen scheint. Je nach Gelände und Suchradius kann der daraus resultierende Weg beliebig stark vom optimalen Weg abweichen oder überhaupt nicht gefunden werden. Dafür gibt er die Orientierung in freiem und unbekanntem Gelände gut wieder.

Der Aktionsradius, die Sichtweite als auch die Geschwindigkeit kann sich an das Gelände anpassen. Insbesondere beim vorhergehenden Ansatz ist es zudem sinnvoll, Geschwindigkeit und Sichtradius daran anzupassen, wie stark die gewählte Richtung tatsächlich zu dem Ziel weist.

Um den Aufwand der Wegsuche zu minimieren empfiehlt es sich, vorberechnete Informationen in der Karte zu speichern (statische KI). Dazu gehört neben der Markierung von Sackgassen auch die Speicherung kompletter Wegenetze, so daß die Wegsuche nur noch die Strecke zwischen Start- und Zielpunkt sowie dazugehörigen Punkten auf dem schon gespeicherten Wegenetz berücksichtigen muß. Das Wegstück auf dem vorberechneten Netz kann entweder mit bekannten Graphenalgorithmen wie z.B. von Dijkstra ermittelt werden oder als schon fertige Liste auf der Karte verfügbar sein.

In sehr einfach strukturierten Umgebungen genügen Kurven niederer Ordnung zwischen Ausgangspunkt und Ziel sowie Schnittpunktberechnungen mit potentiellen Hindernissen für die Wegsuche. Kollisionen werden je nach Anforderung an die Simulation durch variieren der Kurve oder zufällige Wahl einer neuen Richtung gelöst.

Indirekte Kommunikation zwischen Individuen

Die Nachbildung von vorausschauendem Handeln gehört zu den aufwendigsten Bereichen der KI, selbst wenn alle Daten der anderen Objekte direkt einsehbar sind und somit auf die Nachbildung der individuellen Wahrnehmung weitgehend verzichtet werden kann. Einzig praktikabel im Umfeld der Simulation großer Mengen ist derzeit die Interpolation und Extrapolation der Daten anderer Objekte in Abhängigkeit von der Zeit für eine bessere Kollisionsvermeidung oder die Anpassung individueller Ziele. In den meisten Fällen wird man daher Intelligenz nur auf einer niedrigeren Stufe imitieren.

Fallbeispiel: Entgegenkommende Objekte bei engen Passagen

Schon einfache Situationen wie enge Durchgänge erfordern einen umfangreichen Aufwand zu deren korrekter Erkennung. Der triviale Ansatz, bei sich gegenseitig blockierenden Agenten die Auflösung des Konflikts dem Zufall oder dem allgemeinen Verhalten (z.B. "der Klügere gibt nach" oder "der Stärkere gewinnt") zu überlassen, eignet sich nur für die Simulation primitiver Lebewesen.

Mit einigen Kompromissen läßt sich das Problem aber durch den Einsatz von Aktionspunkten lösen: Entweder man platziert an den Enden des Durchgangs jeweils Aktionspunkte, die die Funktion unsichtbarer Pförtner übernehmen, oder man deklariert den gesamten Durchgang als Gebiet mit einem auf ein einziges Objekt beschränktem Fassungsvermögen. Zu beachten ist allerdings, daß die Agenten den Durchgang weiterhin als solchen erkennen müssen und ggf. warten können.

Herdenbildung

Bisher ging es vorwiegend um die Simulation einzelner Individuen. Jedoch gehören auch gemeinsam handelnde Gruppen zum Alltag. Dies läßt sich in der Modellierung des Verhaltens mit berücksichtigen:

Implizit

Im einfachsten Fall benötigt man keine weiteren Regeln, sondern nur geeignete Ausgangszustände, um eine Herde zu simulieren. Gleiche Ziele und dieselbe Bewegungsrichtung genügen, damit unabhängige Agenten als Herde wahrgenommen werden. Problematisch ist allerdings die schwierige Kontrolle der Simulation, da schon geringe Unterschiede der Ausgangszustände und des Verhaltens zu völlig verschiedenen Ergebnissen führen können. Für interaktive Anwendungen ist dieser Ansatz deshalb nicht geeignet

Explizit

Erweiter man den Zustandsvektor eines Agenten um die Zugehörigkeit zu einer Gruppe, sind Verhaltensregeln möglich, welche speziell das Verhalten als Herdenmitglied betreffen. Die Zugehörigkeit kann entweder statisch bei Programmstart vorgegeben sein oder sich als Resultat von Wahrnehmung und Verhaltensregeln ergeben.

Ein Beispiel für die Regelmenge als Herdenmitglied:

Strebe zur MitteStrebe zur Mitte, falls die Herde zu weit weg ist
Vermeide EngeHalte Abstand zu den anderen Mitgliedern
Folge den AnderenFolge der allgemeinen Richtung
Diese Regeln sind anhand der Entfernung zur Herde verschieden gewichtet und erweitern die normalen Verhaltensregeln zur Wegfindung.

Gruppendynamik

Neben der Realisierung durch spezielle Regeln kann man zusätzlich eine Gruppe als einen einzigen komplexen Agenten auffassen, dem die einzelnen Gruppenmitglieder folgen. Ein Teil der Verhaltens wird dann nicht mehr von den verschiedenen Gruppenmitgliedern, sondern von der Gruppe als einzigem Stellvertreteragenten übernommen. Neben dem höheren Realismus durch einheitlicheres Verhalten sorgt dies gleichzeitig für eine Einsparung von Rechenzeit, insbesondere bei der Wegfindung.

Falls gewünscht, kann ein einzelnes Gruppenmitglied die Rolle des Anführers übernehmen. Dessen Auswahl kann auch durch Verhaltensregeln zur Laufzeit erfolgen. Dies ist sinnvoll, falls der Anführer verloren gehen kann oder andere Gruppenmitglieder sich im Laufe der Zeit durch veränderte Eigenschaften besser dafür eignen.

Die Verwendung expliziter Gruppen ermöglicht auch einfachere Initialisierungen mit generischen Regeln wie z.B. "60% Kinder, 20% Väter, 20% Mütter". Für die Realisierung komplexer Hierarchien kann man Gruppen wiederum als Einheiten einer übergeordneten Gruppe verwenden.

Kontrolle der Simulation

Aufgrund der enormen Menge der Zustandsdaten aller Objekte ist es insbesondere zur Laufzeit kaum praktikabel, die Simulation mittels direkter Eingriffe in den Zustand einzelner Objekte zu steuern. Dazu kommt noch, daß die Ergebnisse solcher Manipulationen aufgrund von Interaktionen mit anderen Objekten letztendlich von den Erwartungen abweichen können. Andererseits gibt es im Alltag leistungsfähige sprachliche Begriffe zur Beschreibung des Verhaltens Einzelner und von Gruppen.

Es liegt somit nahe, Skriptsprachen um Befehle zu erweitern, die sich an den umgangssprachlichen Beschreibungen orientieren. In Verbindung mit selbst definierten Makros läßt sich dadurch der Aufwand zur Erstellung und Modifizierung eines Simulationslaufes auf wenige, leicht handhabbare Befehle konzentrieren.

Darstellung

Für experimentelle Zwecke genügt meist eine einfache schematische Visualisierung. Viele Echtzeitsimulationen, vor allem im Unterhaltungssektor, verlangen jedoch nach einer realistisch aussehenden Grafikdarstellung. Hier sind Methoden gefragt, die ohne allzu starke Qualitätseinbußen den Rechenaufwand der Darstellung begrenzen.

Da sich meist nur sehr wenige Agenten in unmittelbarer Nähe befinden, läßt sich die Polygonzahl gerenderter 3D-Objekte mittels LevelOfDetail stark verringern. Indem man weiter im Hintergrund liegende Objekte gleicher Orientierung nur einmal in eine Textur rendert und per Billboarding mehrfach verwendet läßt sich der Aufwand weiter drücken. Hierbei ist allerdings auf eine genügend große Anzahl unterschiedlicher verwendeter Objekte zu achten, damit der Kunstgriff nicht störend auffällt.

Sowohl für die physikalische Modelle der Agenten als auch für die beim Billboarding verwendeten Texturen kann man vorberechnete Animationen einsetzen. Deren Anzahl ist ebenfalls ein Kompromiß aus Aufwand und erreichtem Realismus.

Für die graphische Ausgabe sind zwischen 30 und 70 Bilder pro Sekunde wünschenswert. Dagegen begnügt sich die dahinterstehende Simulation meist schon mit einer wesentlich geringeren Aktualisierungsrate. Dieser Unterschied läßt sich nutzen, indem man zwischen mehreren Simulationsschritten interpoliert. Auf diese Weise läßt sich sogar aus den diskreten Schritten eines zellulären Automats eine flüssige Animation zu erzeugen.

Adressen

Mail an den Autor: webmeister@deinmeister.de

Hauptseite Programmieren Win32Asm Downloads Software Hardware Cartoons+Co Texte Sitemap