GeoSegregation

Geoinformationssysteme (GIS) und Multi-Agenten-Simulation (MAS) sind ein Forschungsfeld des vom Land Nordrhein-Westfalen geförderten Forschungsschwerpunktes nextPlace der Hochschule Ostwestfalen-Lippe.

Im Rahmen des Forschungsschwerpunktes soll ein sogenannter Atlas der Region entwickelt werden, in welchem u.a. Ideen und Konzepte aus dem Forschungsfeld prototypisch in Software umgesetzt werden. In diesem Aufsatz wird ein erster Prototyp beschrieben, welcher die Simulation eines Agenten-basierten Modells (ABM) mit Daten aus einem GIS und der 3D-Kartendarstellung eines Web-Frameworks miteinander kombiniert.

Demo

Der Prototyp der Web-Applikation GeoSegregation kann hier gesta:rtet werden.

Grundlagen

Zum besseren Verständnis der Beschreibung des Prototyps seien folgende Grundlagen erwähnt.

ABM und GIS

Agenten-basierte Modelle (ABM) dienen vielfach als empirische Lösungshilfe für eine Vielzahl von Problemen aus diversen Anwendungsfeldern. Ursprünglich wurden in ABM 2-Dimensionale Rastergitter (engl. grid) zur Berechnung von raumbezogenen Simulationen verwendet. Diese Darstellung ist für die Abbildung von Entitäten wie z.B. Straßen und Häusern der realen Welt nur bedingt geeignet. In GIS haben sich vektor-basierte geometrische Formen für Entitäten etabliert und bieten sich somit ebenfalls als Datengrundlage für ABM an.

Schellingsche Segregationsmodell

Das Schellingsche Segregationsmodell [Schelling1971] ist ein etabliertes Modell um die Entmischung von unterschiedlichen Elementen (z.B. Personen) in einem Beobachtungsgebiet (z.B. Gebäude in einer Stadt) zu simulieren. Es wird in einer Vielzahl von unterschiedlichen Arbeitsfeldern, wie z.B. der Soziologie oder auch Werkstoffkunde, angewendet.

In Crooks [2009] wird eine Software-Implementierung für das Schellingsche Segregationsmodell vorgestellt, welches Agenten-basierte Simulationen auf Geodaten der realen Welt abbilden kann. Dabei werden Agenten (Personen) auf Gebäude einer Karte (Systemumgebung) zufällig verteilt sowie einer roten oder blauen Gruppe zugeteilt. Im Laufe der Simulation bewerten die Personen ihre Zufriedenheit bezogen auf einen gegeben Schwellwert und den prozentualen Anteil an Personen der gleichen Gruppe ihrer Nachbarschaft. Ist dieser Schwellwert unterschritten, suchen sie sich ein freies Gebäude auf der Karte und ziehen um.

Verwandte Arbeiten

Zahlreiche Forschungsvorhaben beschäftigen sich mit GIS und ABM. Stellvertretend seien [GisAgents2016] und [Mars2016] genannt.

Ausgehend von der Motivation und den erarbeiteten Grundlagen sind Anforderungen an den Prototypen abgeleitet worden. Diese Anforderungen bilden die Basis für den konzeptionellen Entwurf des Prototyps.

Entwurf

Ausgehend von der Motivation und den erarbeiteten Grundlagen sind Anforderungen an den Prototypen abgeleitet worden. Diese Anforderungen bilden die Basis für den konzeptionellen Entwurf des Prototyps.

Nicht-funktionale Anforderungen

Für den Prototypen sollen möglichst verfügbare Komponenten genutzt und nur in Ausnahmefällen dediziert implementiert werden. Die Simulation soll gleichzeitig von einer beliebigen Anzahl Nutzern im Browser ausgeführt werden können.

Funktionale Anforderungen

Die oben genannte Implementierung des Schellingschen Segregationsmodells soll Simulationen basierend auf echten Gebäudedaten der Region Ostwestfalen-Lippe ausführen können. Die Anzahl und die Verteilung der Personen zu einer Gruppe sollen über Parameter einstellbar sein. Ebenso der allgemeine Schwellwert der Zufriedenheit einer Person bezogen auf die Gleichheit zu seiner zugehörigen blauen bzw. roten Gruppe in der unmittelbaren Nachbarschaft. Weiterhin kann die Zugehörigkeit eines Gebäudes zu einer Nachbarschaft definiert werden.

Die Simulation soll auf einer Karte visualisiert werden. Der zeitliche Ablauf der Simulationsschritte soll gesteuert werden können. Entsprechende Visualisierungen sollen den Zustand einer Person, eines Gebäudes und der gesamten Systemumgebung pro Simulationsschritt veranschaulichen.

Software-Architektur

Abbildung 1 zeigt die konzeptionelle Sicht auf die Software-Architektur der Anwendung GeoSegregation. Die Anwendung ist nach einer klassischen verteilten Web-Anwendung mit einer 3-Schichten-Architektur (engl. tier) aufgebaut: der Präsentationsschicht, der Anwendungsschicht sowie der Datenverarbeitungsschicht [vgl. Lui2005]. Jede Schicht baut direkt auf der darunterliegenden Schicht auf. Durch Etablierung von definierten Schnittstellen wird lose Kopplung sowie starker Zusammenhalt der einzelnen Module in der Anwendung gewährleistet.

 

Abbildung 1: Software-Architektur, konzeptionelle Sicht

Abbildung 1: Software-Architektur, konzeptionelle Sicht

Implementierung

Diese Architektur ist prototypisch umgesetzt und die in Abbildung 1 orange markierten Module sind implementiert.

Daten

Als Grundlage für die Simulation dienen Gebäudedaten der Stadt Detmold. Diese liegen als ESRI-Shape-Datei vor und werden in der Datenverarbeitung eingelesen und dem Simulationsmodell zur Verfügung gestellt. Ein Gebäude besteht aus geografischen Koordinaten welche zusammen die Grundfläche als Polygon abbilden. Weiterhin hat ein Gebäude Kenntnis über seine Nachbarn, entsprechend dem vom Nutzer gewählten Radius.

Anwendung

Die Web-Anwendung ist  eine Java-basierte Spring Model-View-Controller (MVC) Web-Anwendung [vgl. Arthur2005]. Ein Controller bietet eine REST-Web-Schnittstelle (engl. Application Programming Interface, API) [Fielding2000] zur Interaktion mit der Simulation an. Die lose Kopplung zwischen Simulation und Darstellung ermöglicht die Bereitstellung der Simulation auf verschiedensten Endgeräten für eine große Anzahl an Nutzern.

Eine Übersicht und Bewertung über verfügbare Simulationsumgebungen und Frameworks für ABM ist u.a. in [Railsback2006] skizziert. Die Simulation des Prototyps basiert auf dem MASON-Agenten-Framework mit einer Erweiterung für geografische Daten und Berechnungen [Luke2005]. Die Agenten in der Simulation sind die Personen welche ein Haus beziehen können. Die Simulation wird schrittweise ausgeführt. In jedem Schritt kann eine Person ihren Zustand bezogen auf die aktuelle Nachbarschaft prüfen und ggfs. umziehen. Der Faktor für die Zufriedenheit ist vom Nutzer vor Beginn der Simulation definiert.

Präsentation

Die Simulation wird im Web-Browser präsentiert. Bekannte und etablierte Web-Technologien und Frameworks wie HTML, Java-Script, jQuery, Bootstrap [vgl. Sin2012] bilden den Rahmen für die Präsentation. Als Framework für die Darstellung der Karte wird Cesium [Cesium2016] genutzt. Cesium ist eine Open-Source Java-Script-Bibliothek zur Darstellung von geografischen Daten in 3D Karten. Die Bibliothek wurde in den Prototyp integriert und um spezifische Funktionen zur Darstellung der Daten der Simulation erweitert.

Abbildung 2 zeigt einen Screenshot der Web-Anwendung vor Beginn der Simulation. Eine Steuerkontrolle für die Simulation sowie zur Ansicht wurde etabliert. Die Simulationsdaten (Häuser und Gebäude) können über die Zeit entsprechend dargestellt werden.

Abbildung 2: Bildschirmfoto der Anwendung vor Simulationsbeginn

Abbildung 2: Bildschirmfoto der Anwendung vor Simulationsbeginn

Pro Simulationsschritt werden ca. 5 Sekunden veranschlagt. Mit jedem Schritt wird ein Abbild des Zustandes der Simulation von dem Server an den Client übertragen. Dazu fragt der Web-Client den aktuellen Zustand für den nächsten Schritt an (engl. poll). Alternativ wären hier auch andere Kommunikationsmuster denkbar, wie z.B. dass die Simulation den Client nach Beendigung eines Simulationsschrittes aktiv benachrichtigt (engl. push). Die Zeit kann über einen Schieberegler eingestellt werden. Die Umzüge der Personen auf der Karte werden animiert dargestellt. Abbildung 3 zeigt einen Screenshot mit dem Ergebnis der Simulation.

Abbildung 3: Bildschirmfoto der Anwendung nach Simulationsende

Abbildung 3: Bildschirmfoto der Anwendung nach Simulationsende

Abbildung 4 zeigt einen Screenshot in welcher die Ansicht von der 2/3D-Karte zu einem sogenannten Raum-Zeit-Würfel [Hägerstrand1970] gewechselt ist. In der Darstellung als Raum-Zeit-Würfel bildet jede Schicht oberhalb der Erdoberfläche des Zustand des Simulationsmodell nach einem Schritt dar und stellt die verbliebenen Unzufriedenen dar.

Abbildung 4: Bildschirmfoto der Simulation nach Simulationsende, Darstellung als Raum-Zeit-Würfel

Abbildung 4: Bildschirmfoto der Simulation nach Simulationsende, Darstellung als Raum-Zeit-Würfel

Zusätzliche Filtermöglichkeiten zum Hervorheben des Zustandes gewählter Personen sind gegeben, so werden in Abbildung 4 nur die pro Schritt noch unzufriedenen Personen dargestellt. Wie erwartet nimmt deren Anzahl im Verlauf der Simulation ab.  Weiterhin können die Nachbarn eines Gebäudes hervorgehoben werden sowie fachliche Zusatzinformationen gezeigt werden, wie in Abbildung 5 dargestellt.

Abbildung 5: Bildschirmfoto der Simulation, Detailansicht mit Nachbarn eines gewählten Gebäudes

Abbildung 5: Bildschirmfoto der Simulation, Detailansicht mit Nachbarn eines gewählten Gebäudes

Fazit und Ausblick

Der Prototyp nutzt aktuelle Web-Technologien und ist modular aufgebaut. Er bietet Schnittstellen sowohl für die Integration von verschiedensten Datenquellen als auch zur Präsentation der Simulation auf verschiedenen Endgeräten. Die Umsetzung ist innerhalb von ca. zehn Personentagen erfolgt und liefert einen ersten Eindruck über mögliche zukünftige Weiterentwicklungen am Forschungsschwerpunkt.

Erweiterung des Schellingschen Modells

Das zugrundeliegende Simulationsmodell kann vielfach erweitert werden. So können z.B. weitere geografische Daten, wie z.B. die Topographie, in die Berechnung und Entscheidung der einzelnen Agenten einfließen.

Erweiterung des Frameworks

Der Prototyp könnte in eine generische Plattform für Agenten-basierte Simulationen mit (geografischen) Daten für verschiedenste Endgeräte ausgebaut werden: nextPlace –  Geographic Agent pervasive plattform (GApp). In einem ersten Ausbauschritt wird der Prototyp zu einem Framework erweitert welches von Domänenexperten genutzt werden kann um weitere Simulationen zu etablieren. Die Vision wäre, dass im Wesentlichen nur in der Anwendung das Modell passend zu MASON implementiert werden muss. Insbesondere die Integration von Daten sowie die Darstellung und Steuerung der Simulation auf verschiedenen Endgeräten ist dann bereits vorhanden und kann wiederverwendet werden. Es wird lediglich das Simulationsmodell, z.B. durch eine eigene domänenspezifische Sprache (engl. domain-specific language, DSL), spezifisch beschrieben und dann in ausführbaren Java-Code übersetzt.

Literatur

[Arthur2005]; Arthur et. al.; 2005; Spring framework for rapid open source J2EE Web application development: a case study; Proceedings of the Sixth International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing

[Cesium2016]; https://cesiumjs.org/; Zugriffsdatum: 14.06.2016; An open-source JavaScript library for world-class 3D globes and maps

[Crooks2009]; Andrew Crooks; Constructing and implementing an agent-based model of residential segregation through vector GIS; International Journal of Geographical Information Science Vol. 24, No. 5, May 2010, 661–675

[Fielding200]; Thomas Fielding; 2000; Architectural Styles and the Design of Network-based Software Architectures; Dissertation, University of California, Irvine

[GisAgents2016]; http://www.gisagents.org/; Zugriffsdatum: 14.06.2016; GIS and Agent-Based Modeling, Zugriffdatum: 15.06.2016

[Hägerstrand1970]; Torsten Hägerstrand; 1970; What about people in Regional Science?; Papers of the Regional Science Association, Volume 24, Issue 1, pp 6–21

[Lui2005]; Lui et. al.; 2005; Modeling 3-Tiered Web Applications; 13th IEEE International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems

[Luke2005]; Sean Luke et. al.; MASON: A Multi-Agent Simulation Environment; 2005; Simulation: Transactions of the Society for Modeling and Simulation International. 82(7):517-527.

[Mars2016]; http://mars-group.mars.haw-hamburg.de/; Zugriffsdatum: 14.06.2016; Multi-Agent Research & Simulation

[Railsback2006]; Railsback et. al.; Agent-based Simulation Platforms: Review and Development Recommendations; Simulations 82, 609 – 623

[Schelling1971]; Thomas Schelling; Dynamic Models of Segregation; Journal of Mathematical Sociology, 1971, Vol. 1, pp 143 – 186

[Sin2012]; David Sin et. al.; Mobile Web Apps – The Non-programmer’s Alternative to Native sApplications; 2012 5th International Conference on Human System Interactions

[Yamamoto2008]; Yamamoto et. al.; 2008; A Platform for Massive Agent-based Simulation and its Evaluation; Lecture Notes in Computer Science, Vol. 5043, pp 1-12, Jan. 2008

Kommentar hinterlassen