The Exploratory Advanced Research Program

A Primer for Agent-Based Simulation and Modeling in Transportation Applications

CHAPTER 1: Agent-Based Modeling and Simulation

Basic Concepts

ABMS is a modeling approach for simulating the actions and interactions of autonomous individuals, with a view to assessing their effects on the system as a whole. An essential idea of ABMS is that many phenomena, even complex ones, can be understood as systems of autonomous agents that follow rules of interaction.⁽¹⁾ Repetitive, competitive interactions between agents are major features of ABMS, which rely on the power of computers to explore dynamics out of the reach of pure mathematical methods. In a traditional discrete event simulation, entities follow a sequence of processes, which are defined from the top-down system perspective. In contrast, ABMS defines the local behavior rules, usually simple, of each entity from a bottom-up perspective. In accordance, simulation results reveal the emerging behaviors of a system as a whole, based on the behavior formations of the underlying entities. The main roots of ABMS are in modeling human social and organizational behavior and individual decisionmaking.⁽²⁾

What Is an Agent?

There is no universal definition of the term agent, as agent could refer to different components when studying different objectives in different paradigms. Some may consider any type of distinguished parts of a program (e.g., model, system, or subsystem), or any type of independent entity (e.g., organization, firm, or individual people), to be an agent. As shown in figure 1, the agent is programmed to react to other agents and the computational environment in which it is located,⁽³⁾ with a behavior rule ranging from primitive reaction decisions to complex adaptive AI.⁽⁴⁾ [figure 1]

According to Macal and North,⁽⁴⁾ an agent in a typical ABMS could be defined as follows:

• Identifiable, self-contained, and discrete with a set of characteristics and rules governing its behaviors and decisionmaking capability. The discreteness requirement implies that an agent has a boundary, and one can easily determine whether something is part of an agent, is not part of an agent, or is a shared characteristic.
• Situated, living in an environment with which it interacts along with other agents. Agents have protocols for interaction with other agents, such as for communication, and the capability to respond to the environment. Agents have the ability to recognize and distinguish the traits of other agents.
• Goal-directed, having goals to achieve (not necessarily objectives to maximize) with respect to its behaviors. This allows an agent to compare the outcome of its behavior relative to its goals.
• Autonomous and self-directed. An agent can function independently in its environment and in its dealings with other agents, at least over a limited range of situations that are of interest.
• Flexible, having the ability to learn and adapt its behaviors based on experience, which requires some form of memory. An agent may have rules that modify its rules of behavior.

Scope of ABMS

Agent-based models consist of agents that interact within an environment. Agent-based modeling has been called by various names in the broad base of its applications, which could refer to completely different methodologies. In a computing scientific domain (e.g., AI or distributed autonomous systems), agent-based modeling typically refers to a computational method and simulation for studying the actions and interactions of a set of autonomous entities. It is also called a multi-agent system (MAS) or agent-based system. In non-computing-related scientific domains (e.g., ecological science or life science), Agent-Based models usually refer to the individual-based models.

In social sciences, agent-based modeling could refer to an actor in the social world. In recent years, in agent-based social simulation (ABSS) that mimics social phenomena, the concept of autonomous agents has become well-known. Davidsson⁽⁵⁾ classifies research areas in ABSS into social aspects of agent systems (SAAS), multi-agent-based simulation (MABS), and social simulation (SocSim). This classification depends upon different combinations of focus areas, which include agent-based computing, computer simulation, and social science. First, SAAS focuses more on social science and agent-based computing and includes the study of norms, institutions, organizations, cooperation, and competition, among others. Second, research in the intersection between computer simulation and agent-based computing is referred to as MABS and uses agent technology for simulating any phenomena other than social phenomena. Third, SocSim is in the intersection between social science and computer simulation and corresponds to the simulation of social phenomena on a computer that uses typically simple models of the simulated social entities, such as cellular automata. In transportation research and applications, which are the focus of this primer, the keyword of agent-based modeling is mostly seen referring to an individual-based model and simulation or an autonomous computing method.

Although agent-based modeling is a diverse research paradigm applied in completely different ways in a large and widely spread scientific field, all eventually tie together in the domain of agent-based computing.⁽⁶⁾ The term ABMS in this primer covers all semantics referenced above.

It is worth noting that an agent-based system could also be a software method, such as defined by the Institute of Electrical and Electronics Engineers' Foundation for Intelligent Physical Agents, an international agent standard. The ABMS agents in this primer exclude the software method, in which agents (including mobile agents) are lightweight software proxies that roam over the World Wide Web and perform various functions.⁽⁶⁾

Backgrounds of ABMS

ABMS evolved from AI and computer science but is now being developed independently in research centers throughout the world. The history of ABMS can be traced back to John Von Neumann, who conceived and developed a device later known as cellular automata.

In the 1970s, John Conway developed the Game of Life, a two-dimensional (2D) cellular automata shown in figure 2.⁽⁷⁾

A cell has two states, alive and dead; the state of a cell depends on the state of the neighbors of the previous time step. Conways's game engendered great interest in the emergence of complexity from simple rules.

Interest continued to grow and diversify in the 1990s with the appearance of various tools, particularly Swarm and NetLogo in the mid-1990s and Recursive Porous Agent Simulation Toolkit (Repast) and AnyLogic in 2000.

In the mid-1990s, Joshua Epstein and Robert Axtell⁽⁹⁾ developed Sugarscape, an artificially intelligent ABSS, which captures fundamental concepts of social sciences. At each grid point on a plane, sugar grew at a constant rate. A set of agents, with a fixed, randomly determined level of vision and metabolism, find and eat sugar on the sugarscape. If sugar at one place was exhausted, the agent then moved to a new location where it had the maximum sugar within its vision. This simple system of rules led to migration phenomenon. More rules created additional interesting results. Epstein and Axtell added spice, a second resource similar to sugar. This showed that with barter economies, agents had a higher chance of survival. They added sex and, when there was sufficient sugar, the agents would reproduce. This led to age pyramids, tribal growth, and other demographic features. Other rules led to combat and other evocative results. Sugarscape showed how simple rules could create a complex society in a bottom-up manner, as shown in figure 3, and inspired further growth in agent-based modeling. In the late 1990s, computer power advanced significantly, and ABMS became widespread.

The field of CAS is sometimes referenced as providing the historical roots of ABMS. CAS draws its primary inspiration from biological systems and is concerned mainly with how complex adaptive behavior, as shown in figure 4, emerges in nature from the interaction among autonomous agents.⁽¹⁰⁾ One of the fundamental contributions made to the field of CAS, and to ABMS as well, was John Holland's identification of the four properties-aggregation, nonlinearity, flows, and diversity-and three mechanisms-tagging, internal models, and building blocks-that compose all CAS. Essentially, these items have aided in defining and designing ABMS as they are known today.⁽¹⁰⁾

The Need for ABMS

The ABMS approach allows one to represent and analyze a complex problem (e.g., system dynamics) beyond the reach of mathematics or traditional modeling tools. Advances in database technology (allowing a finer level of granularity) and computational power allow one to compute large-scale microsimulation models that would not have been possible even recently.⁽¹¹⁾ This feature of ABMS has contributed to the field of computer simulation by providing a new paradigm for the simulation of complex systems with many interactions between the entities of the system.⁽⁵⁾ In microsimulations, the structure is viewed as emergent from the interactions between the individuals, whereas in macrosimulations, the set of individuals is viewed as a structure that can be characterized by a number of variables.

Bonabeau⁽²⁾ summarized the benefits of ABMS over other modeling techniques as follows:

• ABMS captures emergent phenomena.
• ABMS provides a natural description of a system.
• ABMS is flexible.

Specifically, ABMS is superior in modeling the following situations:

• The interactions between agents are complex, nonlinear, discontinuous, or discrete.
• Space is crucial, and agents' positions are not fixed.
• Population is heterogeneous, and each individual possesses different characteristics.
• The topology of the interactions is heterogeneous and complex.
• Agents exhibit complex behavior, especially involving learning, interactions, and adaptation.

Challenges in ABMS

Despite the substantial benefits of ABMS discussed in the previous section, there are several challenges associated with ABMS. Samuelson⁽¹²⁾ pointed out that many complex ABMS deal with sufficiently sensitive issues, in which validation becomes problematic, and this difficulty increases as models become more complex. In addition, simulating detailed behaviors of underlying agents could be extremely intensive in computation and therefore become time-consuming.⁽²⁾ Although the computing power is growing at an impressive pace, the high computational requirements of ABMS remain a problem when it comes to modeling extremely large systems.

In a similar vein, Jennings⁽¹³⁾ identified two major drawbacks associated with ABMS:

• The patterns and the outcomes of the interactions are inherently unpredictable.
• Predicting the behavior of the overall system based on its constituent components is extremely difficult (sometimes impossible) because of the strong possibility of an emergent behavior.

Another issue of ABMS in the social science field is that it often involves human agents with potentially irrational behavior, subjective choices, and complex psychology. All of these factors are difficult to measure, quantify, calibrate, and sometimes justify.⁽²⁾

ABMS Applications

Practical ABMS is actively being applied in many areas. Examples of applications include the modeling of organizational behavior and psychology,⁽¹⁴⁾ team working,⁽¹⁵⁾ supply chain management and logistics,⁽¹⁶⁾ consumer behavior,⁽¹⁷⁾ social networks,⁽¹⁸⁾ distributed computing, transportation management,⁽¹⁹⁾ and environmental study.⁽²⁰⁾ In these applications, and in the example shown in figure 5, the system of interest is simulated by capturing the behavior of individual agents and their interconnections. Agent-based modeling tools can be used to test how changes in individual behaviors will affect the system's emerging overall behavior.

ABMS has also been applied to various domains in social and society studies, including population dynamics,⁽²¹⁾ the spread of epidemics,⁽²²⁾ biological applications, civilization development,⁽²³⁾ and military applications.⁽²⁴⁾

In their review, Macal and North⁽⁴⁾ classified these ABMS applications into two categories, as follows:

• Small, elegant, minimalist models-Minimalist models are based on a set of idealized assumptions, designed to capture only the most salient features of a system. These are exploratory electronic laboratories in which a wide range of assumptions can be varied over a large number of simulations.
• Large-scale decision-support systems-Decision support models tend to be large-scale applications, designed to answer a broad range of real-world policy questions. These models are distinguished by including real data and having passed some degree of validation testing to establish credibility in their results.

A short list of ABMS applications summarized by Macal and North is presented in table 1.

Table 1. Agent-based modeling applications (Source: Macal & North⁽⁴⁾)

An Example of ABMS in the Supply Chain

For this section, the researchers use an example from Macal and North⁽¹¹⁾ to illustrate the general components of an agent-based model, and general methods of modeling an agent-based system, in the supply chain context.

Consider a generic supply chain system consisting of five stages: factories, distributors, wholesalers, retailers, and customers. Each stage is modeled by a set of individual entities, or agents, which interact with each other to form a supply chain network, as shown in figure 6.

For simplicity, the suppliers are ignored. There is only one commodity, no transformation of goods is made, and no assembly of materials into products is required. The flows of goods and information in the form of orders between stages (agents), as well as physical shipments, are included in the model. The flows of payments and the complexities of pricing, negotiation, and financial accounting that this would entail are not included in this simple model.

Local rules, or behaviors, of the agents that model the flows of goods are specified as follows:

• The customer places an order with the retailer.
• The retailer fills the order immediately from its respective inventory if it has enough inventories in stock.
• The retailer routinely makes an order, and receives a shipment from the upstream wholesaler, to keep its inventory at a certain desired level. The retailer needs a specific local ordering rule to decide how much to order from the wholesaler. The rule could be based in part on estimating future customer demand by using a demand-forecasting rule.
• Similarly, each wholesaler receives a shipment from the upstream distributor, forecasts future demand by the downstream retailer, and places an order with the distributor. This process continues up the chain to the factory who decides on how much to put into new production.

The goal of the agents at each stage (retailer, wholesaler, and factory) is to manage their inventory at an optimized level such that their net costs are minimized (or net gains are maximized). When inventories are low, there is a chance of losing profits because of running out of stock. When inventories are large, agents have to maintain high inventory holding costs. Agents control their inventory level by following their local rules and by processing local information, such that their own benefits are maximal. Local rules dominate the operating mechanism of the system, because none of the agents can access global information (e.g., information other than an agent's neighborhood), none of the agents has a global view of the supply chain, and none of the agents is interested in optimizing the system as a whole. Through local rules of individual entities in this supply chain system, it is expected to observe the emergent behavior, which ultimately could exhibit an equilibrium state for agents at each stage.

In this example, local information refers to the experienced order histories that have been received from neighborhood agents (upstream and downstream), local rules are the set of rules to maintain a desired inventory level, and emergent behavior refers to the equilibrium for each agent.