 |
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 biowarfare, 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 dominate 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 a. 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 a) 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 postprocessing step, are presented.
|
|
For the newest resources, visit Wolfram Repositories and Archives »
