Who's Your Neighbor?

Neighbor Identification for Agent-based Modeling Using Mathematica

Charles M. Macal

Argonne National Laboratory

Champaign, IL
October 12-14, 2006

Abstract

Agent-based modeling and simulation (ABMS), based on the cellular automata paradigm, is an approach to modeling complex systems comprised of interacting autonomous agents (Macal and North, 2005). Agent behaviors are modeled explicitly, using a range of behavioral models and representation schemes at appropriate levels of detail. ABMS promises to have far-reaching effects on the way that researchers use electronic laboratories to do their research and businesses use computers to support decision-making. Computational advances make possible a growing number of agent-based applications across many fields. Applications range from modeling agent behavior in the stock market and supply chains, to predicting the spread of epidemics and the threat of bio-warfare, from modeling the growth and decline of ancient civilizations to modeling the complexities of the human immune system, and many more. Mathematica is a viable platform for agent-based simulation (Gaylord 1998) and is especially useful for prototype model development (Macal 2004; Macal and Howe, 2005).

Open questions for using Mathematica in agent-based simulation focus on scale-up issues encountered in simulating large numbers of agents. Specifically, how many agents can be included in a workable agent-based Mathematica simulation? One of the basic tenets of agent-based modeling and simulation is that agents only interact and exchange locally available information with other agents located in their immediate proximity or neighborhood of the space in which the agents are situated. Generally, an agent's set of neighbors change rapidly as a simulation proceeds through time and as the agents move through the space. Depending on the topology defined for agent interactions, proximity may be defined by spatial distance for continuous space, adjacency for grid cells (as in cellular automata) or by connectivity in social networks. Identifying an agent’s neighbors is a particularly time-consuming computational task and can dominant the computational effort in a simulation. Two challenges in agent simulation are (1) efficiently representing an agent’s neighborhood and the neighbors in it, and (2) efficiently identifying an agent’s neighbors at any time in the simulation. These problems are addressed differently for different agent interaction topologies. Gaylord (1998) describes an efficient approach for agent neighborhood representation and neighbor identification using Mathematica for agents on a lattice with general neighborhood configurations. Other techniques must be used when agents are able to move freely in space. An example of agents moving in free space is the classic Boids model by Reynolds (1987, 2006). This paper extends agent neighborhood simulation techniques from the lattice topology to continuous space, specifically (ℝ^2).

The problem of agent neighbor identification is similar to problems that occur in several other contexts. These include collision detection in computer simulation or visualization, finding the nearest object or k-nearest neighbors to a query object in a spatial database, finding a clear path through an obstacle field in robotic planning, and aircraft proximity detection in a controlled terminal airspace. Techniques for the analysis and representation of spatial data are applicable to these problems (Samet 1990). A naïve implementation of a neighbor identification algorithm consists of enumerating all agents as neighbor candidates for each agent, which results in an O((n^2)) algorithm, which quickly becomes computationally expensive when n is the number of agents. Alternative algorithms are based on hierarchical (quad trees) or non-hierarchical data structures (grid cells), which are theoretically more efficient. We explore implementing hierarchical and non-hierarchical data structures using efficient implementations in Mathematica, based on Maeder (2000), that are designed to address spatial data, specifically in the context of agent-based simulation. The algorithms are evaluated and compared according to computation times for neighborhood creation, neighbor identification and agent updating. Applications to real-time agent simulations, which visualize simulations in real simulation time such as the Boids model, and batch agent-based simulations, which visualize simulations as a post-processing step, are presented.

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Outline

Agents and Their Neighborhoods

Boids Model: Run Repast-Mathematica Simulation

tPause=10000(* 200 time to pause simulation, in step *);
{tt,res}=Timing[Simulate[numAgents=33,motion->straightLine (* brownian straightLine *),drawCollisionQ->False]];
Print["ave. time per agent-period = ",ScientificForm[tt/numAgents/tNow],"  Periods:  ",tNow,"  No. Agents:  ",numAgents];

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Introduction

– How many agents can be included in a workable agent-based simulation?

– Agent’s set of neighbors changes rapidly as a simulation proceeds through time and as agents move through space

– Adjacency for grid cells (as in cellular automata)

– Connectivity in social networks

– Spatial distance for continuous space: This study concerned with 2-dimensional continuos space, (ℝ^2)

Identifying an Agent’s Neighbors

1. Select a subset of agents as candidate neighbors for evaluation in such a way that the subset includes the agent’s actual neighbors

2. Evaluate the candidates on the proximity criteria.

– Here, explore implementing hierarchical and non-hierarchical data structures

– Use Mathematica to build efficient implementations designed to address spatial data specifically in the context of agent-based simulation

Structure of an Agent-based Simulation in Mathematica

1. Agent Representation

agentPattern=agent[id_String,x_,y_,vx_,vy_,col_,sz_,fil_,v0_,sel_,nColl_,ty_,target_,orient_,leat_]

2. Agent Population

(* generate agent population *)
numAgents=12;
agentsX=Table[
agent[
"#"<>Which[i<10,"00"<>ToString[i],i<100,"0"<>ToString[i],True,ToString[i]](* unique identifier *),
Random[Integer,{0,panelFrameSizeX}](* x-position *),
Random[Integer,{0,panelFrameSizeY}](* y-position *),
velX=Sign[Random[Real,{-1,1}]]*speedBndInit(* speedBndInit Random[ndist=NormalDistribution[speedBndInit,0.10*speedBndInit];] *);
velX*speedFac(* x-velocity *),
velY=Sign[Random[Real,{-1,1}]]*speedBndInit(*  *);
velY*speedFac(* y-velocity *),
RGBColor[Random[Real,{0,0.8}],Random[Real,{0,0.8}],Random[Real,{0,0.8}]](* color *),
Random[Integer,{sizeInitMin,sizeInitMax}](* size *),
True(* filled *),
N[(Sqrt[(velX^2)+(velY^2)])](* initial speed *),
False(* selected status *),
0(* agent type *),
0(* agent type of targets *),
TargetNone(* agent curently targeted by agent *),
Which[Abs[velX]>0,ArcTan[(velY/velX)],velY>0,(π/2),velY<0,((3 π)/2),True,Random[Real,{0,2 π}]](* orientation *),
{}(*  *)
],{i,numAgents}];

agentStats[agentsX,neighborhoodRad];
Print[ColumnForm[agentsX]];

3. For each time period of the simulation, update agent states based on agent neighbors.

agentsAndNeighborsL={#,getNeighbors[#,neighborhoodRad,quadTree]}&/@agentsX;
newAgentsX=agentsAndNeighborsL/.{ag_,agentNL_List}:>agentRulesBoid[ag,agentNL];
Print[ColumnForm[newAgentsX]];

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Agent Neighbor Identification: Related Work

– Spatial Databases

- Finding the nearest object or k-nearest neighbors to a query object

- Find the closest pair of objects in a database

– Computer Simulation and Visualization: Collision detection for objects

– Robotic Planning: Finding a clear path through an obstacle field

– Mobile Communications: Neighbor detection

– AIr Traffic Control: Aircraft proximity detection in a controlled terminal airspace

({{\[FirstPage], ◂, ▸, \[LastPage]}})

For Agent-based Simulation, the Neighbor Identification Problem Has Some Unique Characteristics

– All agents need to determine all their neighbors each time during the simulation

– Complete data structure must be created each time agent locations are updated during the simulation

– Although the various data structure algorithms are applicable to the agent neighbor problem, the criteria against which they are evaluated are different.

Measure to Compare Neighbor Identification Algorithms

- THe advantage of this measure is that it will produce the same results for whatever implementation is used

– Relative times - for algorithm comparison

– Absolute times - for feasibilty of real-time computing and visualization

Experimental Design

1. Identify sets of candidate neighbors

2. All of the actual neighbors are included – no actual neighbors are missed

Algorithm 1: “All Neighbors” Algorithm

– Results in (N^2) comparisons, an O((N^2) ) algorithm

– O((N^2) ) algorithm is computationally expensive for large N

– (Symmetry) agent a is a neighbor of agent b if and only if agent b is a neighbor of agent a

– Number of comparisons: (N-1) + (N-2) + … + 1 = N (N+1) / 2 = (1/2)(N^2) + (1/2)N

– Still an O((N^2)) algorithm

Algorithm 2: Grid Cell Algorithm

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Grid Cell Algorithm Steps

Begin: Agent list

End: Updated agent list (with agents updated based on neighbor attributes)

Grid Cell Algorithm: Creating Grid Cell Tags

(* augment agent list with location-indexed grid cells *)
neighborhoodTagL=agentsX/.agent[id_,x_,y_,r___]:>{agent[id,x,y,r],
{
nx=Floor[(x/neighborhoodRad)],
ny=Floor[(y/neighborhoodRad)],
{Round[(x/neighborhoodRad)],Round[(y/neighborhoodRad)]}-{nx,ny}/.{{0,0}->3,{1,1}->1,{0,1}->2,{1,0}->4}
}
}

Grid Cell Algorithm: Creating Neighborhood Grid Cells

ruleNEQuadrant={x_,y_,1}:>({x,y,0}+#1&)/@{{0,0,1},{0,0,2},{0,0,3},{0,0,4},{0,1,3},{0,1,4},{1,1,3},{1,0,2},{1,0,3}}
ruleNWQuadrant={x_,y_,2}:>({x,y,0}+#1&)/@{{0,0,1},{0,0,2},{0,0,3},{0,0,4},{0,1,3},{0,1,4},{1,1,4},{1,0,1},{1,0,4}}
ruleSWQuadrant={x_,y_,3}:>({x,y,0}+#1&)/@{{0,0,1},{0,0,2},{0,0,3},{0,0,4},{0,-1,1},{0,-1,2},{-1,-1,1},{-1,0,1},{-1,0,4}}
ruleSEQuadrant={x_,y_,4}:>({x,y,0}+#1&)/@{{0,0,1},{0,0,2},{0,0,3},{0,0,4},{0,-1,1},{0,-1,2},{1,-1,2},{1,0,2},{1,0,3}}
ruleQuadrant={ruleNEQuadrant,ruleNWQuadrant,ruleSWQuadrant,ruleSEQuadrant}

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Algorithm 3: Quad Tree Algorithm

- There is less concern for the time to create the tree, since objects in spatial or image databases are static

- In agent simulation, the quad tree must be created at each time step

- Therefore, there is a recurring penalty for data structure creation when used in agent neighbor identification

Algorithm 3: (Point) Quad Tree Algorithm

tree:  {agent[id_String,___],{contentsNEquad_,contentsNWquad_,contentsSEquad_,contentsSEquad_}}
where the contents of any quadrant is another tree or 0, to denote a leaf of the tree.

Step 1: Create the quad tree and report:

(* Create quad tree. *)
root=createRoot[First@agentsX];
ttCreateTree=Timing[quadTree=Fold[newQuadtree[#2,#1]&,root,Rest@agentsX]][[1]];

(* Report on quad tree. *)
Print["Create quad tree: ",ttQU," for ",numAgents," agents (",ttCreateTree/numAgents,"/agent; ",If[ttCreateTree[[1]]<10^-8,"INFINITY",Floor[numAgents/ttCreateTree[[1]]]]," agents/",ttCreateTree[[2]],")"];

Step 2: Display quad tree.

(* Display quad tree. *)
treePlotData=quadTreeToGraphPlot[quadTree];
displayTree[treePlotData,Tree,agentsX[[1,1]],imgSz->450];

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Determining Neighbors from a Quad Tree

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Radial Quad Tree for the Agent Neighbor Problem

Figure illustrates dimensions of the agent neighbor problem for comparison purposes

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Comparisons of Candidate Neighbors vs. Actual Neighbors, by Algorithm

({{\[FirstPage], ◂, ▸, \[LastPage]}})

Main Results

References

Gaylord, R., and L. D'Andria, 1998, Simulating Society: A Mathematica Toolkit for Modeling Socioeconomic Behavior, TELOS/Springer Verlag:New York.

Macal, C., 2004, “Agent-Based Modeling and Social Simulation with Mathematica and MATLAB,” Proc. Agent 2004 Conference on Social Dynamics: Interaction, Reflexivity and Emergence, C. Macal, D. Sallach, and M. North (eds.), Oct. 7-9, pp. 185-204, www.agent2006.anl.gov.

Macal, C., and T. Howe, 2005, “Linking Mathematica and the Repast Agent-Based Modeling Toolkit,” Wolfram Technology Conference 2005, Champaign, IL, Oct. 6-8, http://library.wolfram.com/infocenter/Conferences/5767/.

Macal, C., and M. North, 2005, “Tutorial on Agent-based Modeling and Simulation,” Proc. 2005 Winter Simulation Conference, M. Kuhl, N. Steiger, F. Armstrong, and J. Joines (eds.), Orlando, FL, Dec. 4-7..

Maeder, R., 2000, Computer Science with Mathematica, Cambridge University Press:Cambridge.

Reynolds, C., 1987, "Flocks, Herds, and Schools, a Distributed Behavioral Model," Computer Graphics, 21(4):25-34.

Reynolds, C., 2006, “Boids,” http://www.red3d.com/cwr/boidss/.

Samet, H., 1990, The Design and Analysis of Spatial Data Structures, Addison-Wesley:Reading, MA.