© Copyright JASSS

  JASSS logo ----

Catherine Dibble and Philip G. Feldman (2004)

The GeoGraph 3D Computational Laboratory: Network and Terrain Landscapes for RePast

Journal of Artificial Societies and Social Simulation vol. 7, no. 1
<http://jasss.soc.surrey.ac.uk/7/1/7.html>

To cite articles published in the Journal of Artificial Societies and Social Simulation, please reference the above information and include paragraph numbers if necessary

Received: 10-Jan-2004      Accepted: 10-Jan-2004      Published: 31-Jan-2004


* Abstract

Our GeoGraph 3D extensions to the RePast agent-based simulation platform support models in which mobile agents travel and interact on rugged terrain or on network landscapes such as social networks of established organizational teams or spatial networks at any scale from rooms within buildings to urban neighborhoods to large geographic networks of cities. Interactive GeoGraph 3D visualizations allow researchers to zoom and pan within the simulation landscape as the model runs. Model-specific 3D representations of agents flock together on terrain landscapes, and teleport or travel along links on network landscapes. Agents may be displayed on network nodes either as individual agents or as dynamic 3D bar charts that reflect the composition of each node's population. Batch modes support scientific control via fully separated random number series, customized parameter combinations, and automatic data collection for many thousands of simulation runs. This paper introduces the GeoGraph 3D computational laboratory and briefly describes three representative GeoGraph models along with basic GeoGraph 3D capabilities and components.

Keywords:
Simulation tools, Geographic Simulation, Network Landscapes, Epidemic Control, 3D Landscapes, GeoComputation, small-world

* Introduction

1.1
Human interactions of many kinds are increasingly structured by social, organizational, communication, and transportation networks. Yet tools to model, understand, and predict dynamic human interactions and behavior on richly structured network and three-dimensional geographic terrain landscapes have lagged far behind. A network landscape differs from a social network because the nodes represent established groups or geographic places rather than individual agents. Each agent on a network landscape is free to move from one node to another in the landscape.

1.2
For example, organizational agents may transfer from one team to another, while the teams themselves retain their identity within the organizational structure. Similarly, agents in spatial networks may move from one lecture hall to another, from one street corner to another, from home to work to market places, or from one city or country to another. Agents who share a given node at any given time may be assumed to be completely connected (as in a social network clique), randomly connected, or selectively connected according to model-specific characteristics of the agents.

1.3
Our GeoGraph 3D extensions to the RePast agent-based simulation platform support models in which mobile agents travel and interact on 3D rugged terrain and network landscapes. GeoGraphs contribute to spatially integrated social science research by allowing us to develop models that include not only heterogeneous agents and site-specific characteristics, but also the complementary organizational and geographic landscapes that mediate each agent's mobility, exchanges, and encounters.

1.4
GeoGraph computational laboratory tools are designed to support controlled experiments for agent-based organizational and geographic simulations through their ability to generate richly structured parameterized families of synthetic network or rugged landscapes, or of complementary Geographic Information System (GIS) derived empirical network or rugged geographic landscapes. GeoGraphs support the development and rigorous scientific use of simulation models grounded in interesting network structures such as spatial small-world networks, spatial scale-free networks, hybrids between the two, and GIS representations of real-world landscapes.

1.5
This paper provides a brief introduction to GeoGraphs through three representative GeoGraph models for controlling epidemics, for controlling civil violence, and for coordinating socially-networked team members in geographic space to illustrate and briefly introduce key GeoGraph capabilities and components. Remaining sections summarize GeoGraph landscapes, agents, scaling, usage, and further development.

* Three Representative GeoGraph Models

2.1
The GeoGraph 3D Computational Laboratory is intended to provide a fully general suite of tools for developing models of mobile heterogeneous agents on richly structured organizational and geographic landscapes. Prototype GeoGraph models have been developed for diverse applications, including:
  • epidemiological studies of infectious disease transmission among mobile agents,
  • spatio-temporal dynamics and nonlinearity of civil violence activities such as riots, looting, or genocide,
  • command, control, and communication structures for effective peacekeeping teams facing riots and related dynamic and distributed problems of civil unrest,
  • epidemiological studies of domestic US malaria risk in conjunction with climate models of global warming (Root 2003),
  • settlement patterns, sector migration, and long-run regional development,
  • the effects of globalization processes on both epidemiology and regional settlement patterns, and
  • visualization and modeling of dynamic social networks and trading games on geographic landscapes.

2.2
This section presents brief introductions of the first three GeoGraph application models listed above, in order to illustrate key GeoGraph modeling capabilities:
  • synthetic random networks, with hybrid small-world and scale-free shortcuts,
  • synthetic grid networks, with hybrid small-world and scale-free shortcuts,
  • agent mobility on GeoGraph network landscapes,
  • agent interactions such as spreading infectious diseases, deciding to riot, arresting rioting agents within view, or following orders from other agents, and
  • implementation and visualization of command and control social networks among geographically mobile agents.

Controlling Epidemics of Infectious Diseases

2.3
We have developed a suite of tools in GeoGraphs that can be used to explore the spatially explicit behavior of any SEIR (Susceptible, Exposed, Infected, or Removed) epidemiological model among heterogeneous spatially mobile agents, at any scale from hospital corridors to international travel. Incubation period and sick period are measured in days of duration from infection and onset of sickness, respectively. Contagious delay is measured in days from infection. These three taken together, along with additional parameters for contagious period, support modeling for any directly communicable infectious disease. Experimental controls can modify all of the parameters above as they are calibrated to the best data available for a specific disease.

2.4
Similarly, these general epidemiological models can be run for any demographic and spatial distribution of heterogeneous agents across any GeoGraph landscape. In particular, the same heterogeneous agent population with the same or different distribution of epidemiological characteristics or stochastic behaviors can be run on any landscape from an aspatial soup (i.e., one node, to check the GeoGraph model against standard aspatial mathematical models), to any set of synthetic GeoGraph small-world and scale-free landscapes, to any real-world landscape derived from data from a Geographic Information System (GIS) and calibrated according to the best demographic (e.g. census) data available for that region.

2.5
The simulations are fully developed and are running in our laboratory at the University of Maryland this winter. We expect to be able to answer the following sorts of questions for any infectious disease affecting any population on any network landscape:
  • Given urban population distributions and inter-city transportation networks, which cities are at greatest risk from epidemics of known or of unknown geographic origins?
  • Which cities should have priority for public health interventions such as vaccinations or isolation and quarantine enforcements in order to serve as effective epidemiological "firebreaks" for the region?
  • Which airline flights, train routes, or highways should be blocked or carefully monitored (e.g. by deploying infrared fever sensors as for SARS) in order to best control the epidemic with the least disruption to transportation services and economic activity?
The answers to such questions identify which cities or inter-urban transportation links should be targeted to receive limited re-enforcements for epidemiological interventions. Our model serves as a strategic national or international complement to other simulation models developed to identify strategic epidemiological interactions within a given county or city such as the Brookings and Johns Hopkins Dark County Model (Epstein et al. 2002) or the social network micro-simulation model for Eugene, Oregon that is under development at Los Alamos National Laboratory (Eubank 2002).

2.6
Each risk or intervention strategy can be identified both for potential epidemics, where the geographic origin of the epidemic is unknown a priori, and for actual epidemics, where the initial geographic origin and epidemic extent are already known. We are in the process of adding life-cycle dynamics to GeoGraph agents in order to model epidemics where rates of morbidity and mortality are specific to the sex or age of individuals. In each case, carefully designed computational laboratory experiments can help policy makers to understand relative risks and the expected effectiveness of specific interventions. Such experiments can provide far better information about what to expect from complex stochastic spatio-temporal dynamic events such as epidemics. Yet this simply provides better information about the best approaches under difficult conditions; nothing short of a crystal ball can predict with certainty what will actually occur in each situation.

Figure 1
Figure 1: A GeoGraph model of SARS, where individual agents travel between communities and bar charts for each community show the epidemiological status of its population. Green agents are healthy, pink are infected, red are sick, gray are dead, and white are recovered and immune. The model includes super-spreader events and seasonally adjusted infectivity. Gray links are base links, such as highways or trains, yellow links are high-speed shortcuts in the landscape such as airline routes.

Dynamics of Civil Violence

2.7
Agent behavior for this prototype model of rumors and looting is derived from the grid-based Brookings Civil Violence model (Epstein et al. 2001). Each square citizen agent decides whether or not to loot depending upon the net balance of his or her perceived hardship, individual risk aversion, and the subjective legitimacy of the current regime. Finally, the decision to loot or not at any given moment is also a function of the balance between the agent's attitudes and his or her context-specific perceived probability of arrest if looting. An agent's individual perception of the probability of arrest depends upon the distance to the nearest peacekeeper(s) and upon the ratio of currently active looters to peacekeepers within the agent's immediate neighborhood.

2.8
In the Brookings model, civilian agents and peacekeepers each occupy one cell of a square grid, and move at most to neighboring cells. Our simple prototype extends the Brookings model by allowing both civilian agents and peacekeepers to move around on any network landscape, by allowing multiple agents per node, and by allowing agents to interact both directly and indirectly. Figure 2 illustrates the example here, which includes an undulating mesh network enhanced by several spatial small-world shortcuts. The ring around each agent shows how far it can see.

2.9
Future versions of this model will incorporate the endogenous diffusion of rumors among civilian agents. We have already implemented sophisticated models of diffusion among heterogeneous mobile agents as part our epidemiological models of infectious diseases. This additional capability to model rumors among civilian agents could support strategic research regarding the effective use of counter-information for the prevention or control of looting, rioting, and other forms of civil violence among civilian agents.

2.10
Similarly, future models could combine this Rumors and Looting model of civilian unrest with the GeoGraph model for effective coordination of peacekeeping teams, which we present in the next section.

Figure 2
Figure 2: GeoGraph Rumors and Looting extensions to the grid-based Brookings Civil Violence model (Epstein et al. 2001). Red squares are looting civilians, green squares are peaceful civilians, gray squares are temporarily arrested civilians; blue dots are peacekeepers; rings around agents show how far each can see. Yellow lines are shortcuts in the landscape.

Social Networks Connecting Geographically Mobile Team Members

2.11
GeoGraphs have a series of classes that allow for the creation and observation of teams of agents that behave as social hierarchies. For each layer of responsibility in the organization, there can be a specific type of Hierarchy Agent that fills that role. In addition to the normal capability of a GeoGraph Agent, these agents have additional capabilities that allow for command and message passing to follow a chain of command. To support this, the simulation can show visualizations of these communication links in a variety of contexts, ranging from lines drawn between the members of the group, to group coloration, to tree views that show the hierarchy by group member name, command, and status. These displays are linked, so that selecting an agent in one display highlights that agent in the other displays.

2.12
The prototype implementation of this GeoGraph teams capability models competing warlords in an urban setting. Each warlord selects a home base to work from, and then sends his lieutenants forth to gather food from unoccupied nodes, to raid food from occupied nodes, to attack other agents, or to defend a node. The lieutenants in turn command their soldiers to gather food, deliver food, or attack a node. The warlords make their decisions based on the amount of food other warlords have and on the history of attacks by other warlords.

2.13
Although simple, this prototype illustrates the basic capabilities of a simulation that supports a command and control structure: Warlords can be designed to focus on the strategic picture; how to maximize their food stores and prestige among other warlords. Lieutenants are designed to take strategic level commands and convert them to a more limited set of tactical commands for the foot soldiers. The soldiers in turn are only concerned with handling the immediate task at hand.

2.14
As in any command and control hierarchy, communications between agents may be imperfect. An agent may not heed its superior, communication between an agent and its superior may be spotty, or the agent's situation on the ground may interfere with the agent's obedience of its order. GeoGraph team models support this reality by allowing for noisy communication links between individuals, where each agent may make decisions based on local information as well as on a remote command. This in turn supports the study of command and control structures for effective team performance; to optimize command and control networks and procedures for teams facing uncertain conditions and distributed dynamic events such as civil violence during peacekeeping operations. For example, see DeCanio, Dibble, and Amir-Atefi (2000, 2001) for related genetic algorithm optimizations of task-specific and multi-task organizational structures.

Figure 3
Figure 3: Full-screen top view of the main GeoGraph Teams simulation window. This is a dynamic simulation with agents moving around the landscape in order to address pillars of resources or targets. Gray pillars are stocks of food or other resources to be looted or protected, targets of opportunity to be attacked, or other trouble to be addressed. In this example, pillars represent food and agents are indigenous Warlord Generals, Lieutenants, and Soldiers.

* GeoGraph Landscapes

3.1
GeoGraphs can generate geographic landscapes that are either synthetic (parameter driven) or empirical (derived from Geographic Information System or Remote Sensing data files), and which are either network landscapes or two- or three-dimensional "natural" landscapes. Full discussions of GeoGraph landscapes will be published elsewhere. This section provides a brief introduction to synthetic network landscapes and to synthetic three-dimensional fractal terrain landscapes.

3.2
GeoGraphs generalize small-world (Watts and Strogatz 1998) and scale-free (Barabási and Albert 1999) networks to synthetic spatial small-world hybrid network landscapes by:
  • adding new shortcuts rather than rewiring (airline flights don't destroy underlying roads),
  • applying Euclidean or great-circle distance metrics to shortcuts rather than the unit distances that are used for the binary networks in ordinary small-world and scale-free networks,
  • modifying shortcut distances by a contraction factor to reflect technological advantage (e.g. jet planes are typically ten times faster than cars (contraction = 0.1)) and to model globalization processes as technologies improve,
  • applying positive or negative feedback to link attachment probabilities by constructing a roulette wheel over all nodes, where probabilities of selection are either directly or inversely proportional to the shortcut distances between the two nodes, and
  • applying positive or negative feedback to link attachment probabilities by constructing a roulette wheel over all nodes, where probabilities of selection are either directly or inversely proportional the number of links already connected to each node.

3.3
For example, given a ring landscape with sixty nodes and base links connecting each neighbor along the edge of the ring, GeoGraphs could generate an effectively infinite number of richly structured irregular network landscapes simply by varying the parameter for the number of shortcuts and by varying the random number seed (geoSeed) that initializes the random number series used to determine the position for each shortcut.

3.4
GeoGraphs can also import network landscapes and corresponding territorial outline maps from Environmental Systems Research Institute's Geographic Information Systems (GIS) shape files.

Finally, GeoGraphs have a class of parameter-driven synthetic three-dimensional fractal terrain landscapes. See Figure 4 for an example.

Figure 4
Figure 4: A GeoGraph parameter-driven synthetic three-dimensional fractal terrain landscape with parameterized renewable green “tree” agents and small flocks of “deforestation” red and blue agents.

* GeoGraph Agents

4.1
The GeoGraph Computational Laboratory provides three classes of proto-agents, from which model agents may inherit specific geographic capabilities that correspond to classes of GeoGraph landscapes.
GeoAgent3D
knows how to navigate networks. It may either teleport from node to node or may be restricted to follow specific types of links within the landscape. It may evaluate nodes within a network-specific neighborhood, and may also compute shortest paths from one node to another along multiple links. It is written to utilize Node3D, which is a network enabled node. Most of the simulations extend this class, including the SARS model illustrated in Figure 1 and the Rumors and Looting model illustrated in Figure 2.
FreeAgent3D
moves between nodes without following links. It is written to utilize FreeNode3D, which is the basis for the Teams model illustrated in Figure 3.
NodelessAgent3D
is a free roaming agent. It is the least developed, yet provides the basis for the Flocking agents on fractal terrain landscapes, illustrated in Figure 4.

* GeoGraph Scaling

5.1
A GeoGraph model can represent any spatial scale, depending for visual clarity only upon suitable cartographic generalization in the representation of the landscape and of its agents. Each GeoGraph node or agent can be scaled visually from the tiniest dots to a fully detailed graphic image of anything from a shrubbery to a house to a Porsche to an elephant to any other graphical avatar. Similarly, nodes in a network landscape may be interpreted, and represented, as anything from tables in a cafè to world cities or even planets. Agents for each landscape may be scaled either in their correct proportion to the geographic scale, enlarged to facilitate visualization of the model's behavior, or reduced to avoid visual clutter.

5.2
The maximum number of nodes and agents for a GeoGraph model depends upon the fidelity of the respective node and agent classes. Specifically it depends upon the CPU time and memory requirements for the behavior and visualization of each. Interactive display of the GeoGraph landscape and its agents generally places a greater burden on the computer and thus limits the number of nodes and agents by approximately one order of magnitude compared with running the equivalent simulation with visualization of real-time data charts but with the landscape graphics hidden. For example, our SARS model can run with several thousand agents and nodes with a visible landscape. The same simulation can run with 50,000 agents in batch mode that shows only the plots for morbidity and mortality (on a 2.4 GHz Pentium 4 running Windows XP, SUN Java VM, and with 2 gigabytes of RAM). We are currently researching extensions to the core simulation engine that would allow us to run simulations for many millions of agents. We expect this capability (and clusters of computers to run such models) to become available in a year or so, depending upon research needs and upon our levels of funding.

5.3
In general, we develop and debug each model using a visual resolution and population of agents that is comfortable for visualization. After we are thoroughly comfortable with the model and have tested it extensively, we can turn off the landscape display and scale up the numbers of nodes and especially the numbers of agents for batch-mode experiments, if that turns out to be important scientifically for the model's results. Depending upon the model and upon the level of abstraction and resolution appropriate for rigorous results, very large numbers of agents can be available but are not necessarily required.

5.4
We find that the memory limitation comes from the Java Virtual Machine (~850 megabytes for SUN's Java VM (http://java.sun.com)) rather than from limitations of the computer's memory. We are especially eager to hear from colleagues whether other Java Virtual Machines are less restrictive than SUN's in their limitations on maximum memory settings.

* GeoGraph Usage

Figure 5
Figure 5: GeoGraph Components. Each of the three can be run either interactively, for visualization, or in batch mode to generate input files for many simulations at a time.

6.1
GeoGraphs are designed from the ground up to handle the additional levels of complexity involved in creating, viewing, and interacting with such richly structured landscapes and agent populations. GeoGraphs do this by breaking the creation and simulation process into three distinct stages: Creation, Modification, and Simulation. XML files containing progressively more sophisticated representations are initialized and then pipelined through the process, until they are ready for the simulation to read them in and run. In this manner, specifications for each simulation are developed in small, understandable steps.

6.2
Implementation of a new GeoGraphs model typically involves three stages:
  1. Selecting one of the available landscapes (or, for advanced developers, developing a new GeoGraph class for a different landscape) from GeoGenerator,
  2. Developing a set of model-specific agent-classes that inherit from GeoGraph base classes introduced in section 4,
  3. Developing the main simulation program for the GeoSim to describe agent behavior and control the model's initialization, simulation, and stopping rules, as you would for any agent-based simulation model, and finally
  4. Writing the GeoToYourSim ModTool translator to tell GeoGraphs which agents on the GeoGenerator landscape should be assigned to which class, and to specify initial parameters for each agent.
The approach would be similar to port an existing RePast model to GeoGraphs, except that the RePast Java classes for agent behavior and for the main model would already exist. In this case, porting would involve ensuring that the simulation agents inherit their GeoGraphically savvy behavior from one of the main GeoGraph agent classes, as well as adapting the main simulation program to call the new GeoGraph agent classes where appropriate.

6.3
For example, in order to run one or more simulations, a landscape and a simple population of generic agents is initially created through GeoGraph's GeoGenerator program, in either batch or interactive mode. Later, that population of agents is modified and extended for a specific model through the use of subsequent interactive tools. For example, to convert GeoGenerator proto-agents to epidemiological agents for our SARS model, we created a Java ModTools program we call GeoToSARS. The user then calls this ModTools program either interactively or in batch mode in order to create one or more XML simulation files for input to GeoSim, each with its own population of agents, initial conditions and agent behaviors, where each agent has the capability to move through its abstract landscape or through a GIS-derived urban or regional landscape, and to interact with other agents in the landscape. GeoSim tools for that simulation then call the single XML file (in interactive mode) or a batch of XML simulation files (in batch mode), to run the simulation(s) and produce results.

6.4
Once the file is loaded into the simulation in interactive mode, the user can fly through the running simulation, select individual agents to view their internal states, and view the interaction of the agents with each other or with their environment by choosing which landscape they wish to view through the use of dropdown menus that offer default views such as a top view, a three-quarters view, and a default view determined by the modeler. It is always possible to fly and zoom through each landscape as it runs, in addition to the default views. Finally, data from the simulation is displayed as charts or recorded to text files for further analysis.

* Summary and Further Development

7.1
Current GeoGraph 3D Computational Laboratory tools support a three stage process for interactive and batch generation, modification, and simulation of agent-based models on richly structured synthetic and GIS-derived network and terrain landscapes. GeoGraph agents know how to look around and move around on GeoGraph landscapes; they may have any RePast-programmable agent behavior in addition to their geographic capabilities.

7.2
Further developments include adding genetic algorithms at three different levels and extending GeoGraph spatial landscape capabilities from synthetic and GIS-derived 2D and 3D network landscapes to more user-friendly versions of the rugged 3D synthetic fractal landscapes and 3D natural landscapes derived from GIS Digital Elevation Models (DEMs, see http://www.terrainmap.com/rm3.html) or Triangulated Irregular Networks (TINs, see http://www.ian-ko.com/resources/triangulated_irregular_network.htm). We are also working to add initializable (via synthetic vegetation generation parameters or via Remote Sensing data layers), dynamic, and climatologically responsive immobile vegetation agents such as grass and trees to support ecological modeling of spatially explicit interactions among vegetation agents and populations of mobile human and animal agents.

7.3
For the latest information regarding GeoGraph capabilities and availability, please check our GeoGraphs Home Page at http://www.geog.umd.edu/complab/complab/geographs.shtml.

* Acknowledgements

We gratefully acknowledge helpful comments from JASSS editors, financial support from the United States Office of Naval Research for 2002-2004 under grant number N000140310062, and assistance from Nick Collier and participants of the RePast email lists. Catherine also thanks Mike Goodchild, Steve DeCanio, and Swarm colleagues for supporting her development of the original version of GeoGraphs (2D, for Swarm).

* References

BARABÁSI, A. L., and R. Albert. 1999. Emergence of scaling in random networks. Science 286, no. 5439: 509-12.

DeCANIO, Stephen J., Catherine Dibble, and Keyvan Amir-Atefi. 2001. Organizational Structure and the Behavior of Firms: Implications for Integrated Assessment. Climatic Change 48: 487-514. http://econ.ucsb.edu/~decanio/complab/papers/twotask6.html

DeCANIO, Stephen J., Catherine Dibble, and Keyvan Amir-Atefi. 2000. The Importance of Organizational Structure for the Adoption of Innovations. Management Science 46, no. 10: 1285-29. http://econ.ucsb.edu/~decanio/complab/papers/orgbar.html

DIBBLE, Catherine. 2003. "GeoGraphs Home Page." Web page. Available at http://www.geog.umd.edu/complab/complab/geographs.shtml

EPSTEIN, Joshua M., John D. Steinbruner, and Miles T. Parker. 2001. Modeling Civil Violence: An Agent-Based Computational Approach. Brookings Institution, Center on Social and Economic Dynamics, Working Paper Number 20, January 2001. http://www.brookings.edu/dybdocroot/es/dynamics/papers/cviolence/cviolence.pdf

EPSTEIN, Joshua M., Derek A. Cummings, Shubha Chakravarty, Ramesh M. Singa, and Donald S. Burke. 2002. Toward a Containment Strategy for Smallpox Bioterror: An Individual-Based Computational Approach. Brookings Institution, Center on Social and Economic Dynamics, Working Paper Number 31, December 2002. http://www.brookings.edu/dybdocroot/es/dynamics/papers/bioterrorism.pdf

EUBANK, Stephen. 2002. Scalable, Efficient, Epidemiological Simulation. Los Alamos National Labs. ACM Copyright 2002. http://www.ccs.lanl.gov/ccs5/documents/pdf/2001/LA-UR-01-5513.pdf

REPAST Developers Group. 2003. "RePast Home Page." Web page. Available at http://repast.sourceforge.net

ROOT, Elisabeth Dowling. 2003. "Modeling the impact of climate change on malaria incidence using climate models and agent-based simulation." University of Maryland.

SWARM Developers Group. 2000. "Swarm Home Page." Web page. Available at http://www.swarm.org

WATTS, D. J., and S. H. Strogatz. 1998. Collective dynamics of 'small-world' networks. Nature 393, no. 6684: 440-442.

----

ButtonReturn to Contents of this issue

© Copyright Journal of Artificial Societies and Social Simulation, [2004]