Agent-based Modeling and Simulation

S. Taylor

• Publisher: Palgrave Macmillan
• Year: 2014
• Print ISBN: 9781349497737, 9781137453624
• eBook ISBN: 9781137453648
• Topic: Business
• Subtopic: Business Strategy
• Index: Business

Operational Research (OR) deals with the use of advanced analytical methods to support better decision-making. It is multidisciplinary with strong links to management science, decision science, computer science and many application areas such as engineering, manufacturing, commerce and healthcare. In the study of emergent behaviour in complex adaptive systems, Agent-based Modelling & Simulation (ABMS) is being used in many different domains such as healthcare, energy, evacuation, commerce, manufacturing and defense. This collection of articles presents a convenient introduction to ABMS with papers ranging from contemporary views to representative case studies. The OR Essentials series presents a unique cross-section of high quality research work fundamental to understanding contemporary issues and research across a range of Operational Research (OR) topics. It brings together some of the best research papers from the esteemed Operational Research Society and its associated journals, also published by Palgrave Macmillan.

1

Introducing agent-based modeling and simulation

Simon JE Taylor

Brunel University, UK

1 Modeling & simulation

The manager of an Accident and Emergency (A&E) service (or Emergency Room) has a problem. The waiting room of her Unit is always full of patients waiting to see her clinical staff. Patients arrive, are checked in by a receptionist and then wait until they are seen by a nurse. If an arriving patient is in obvious distress then the patient is seen as soon as a nurse is available. The nurse records their medical details, discusses them with a doctor and then proceeds with a range of possible actions to treat the patient or to pass the patient on to another department. How can the manager understand how to reduce the number of patients waiting to see the nurse? Should she hire more nurses? Are doctors in short supply? Are nurses waiting for information from other departments? What about alternative arrival arrangements—should the reception team have clinical skills to make an earlier assessment of patients’ needs? Modeling & simulation (M&S) makes it possible for the A&E manager to create a verifiable and valid computer model of her system and to simulate it under different experimental conditions to understand what is causing the lengthy waiting times and the possible impact of different strategies to alleviate them.

M&S draws from disciplines such as mathematics, operational research, computer science, statistics, physics and engineering and encapsulates a wide range of methods and technologies that enable the investigation and analysis in broad set of application areas such as biology, commerce, defence, healthcare, logistics, manufacturing, services, supply chains and transportation. Although the roots of M&S can arguably be traced back to the origins of the Monte Carlo method in Buffon’s needle experiment in 1777 (corrected by Laplace in 1812—the experiment is commonly called as the Buffon-Laplace Needle Problem), advancements in simulation and computer technology made during World War II provided the foundation for modern day M&S (Goldsman, Nance and Wilson, 2010). In the 1950s these techniques and technologies were applied to the investigation of industrial systems. Two key simulation techniques emerged from these efforts: discrete-event simulation (DES) and system dynamics (SD).

Fundamental to both techniques is how we represent a system and how it changes over time. Early work in DES by K.D. Tocher (Tocher, 1960; Tocher 1963; Hollocks, 2008) recognized how a system could be modeled as a set instantaneous state changes in time (events) organized into activities. Each activity has a start event and an end event. Entities pass through a simulation engaging in interdependent cycles of various activities (eg, parts passing through a set of machining activities). Early representations of these cycles were referred to as wheel charts or activity cycle diagrams. Today, some commercial DES software still echo Tocher’s work and allow modelers to represent systems as networks of queues and activities (sometimes called a queuing network model or process model). Law (2014) and Robinson (2014) are good textbooks for those wanting to find out more about this technique. Independently, Forrester introduced a different approach to analysing industrial systems by considering a system as consisting of cyclical interdependent subsystems or causal loops, and created the foundations of SD simulation (Forrester, 1961). Instead of a network of queues and activities, SD can represent a system as a set of causal loops in a causal loop diagram that describes how the components of the system interact (and importantly feedback). The use of stocks and flows allow an SD model to be quantified and simulated. A stock is an entity that can increase or decrease in amount as it passes through a flow that defines the rate of change. See Sterman (2000) for more details on SD. Both DES and SD are supported by many software tools and languages (up-to-date lists of indicative software can be found on Wikipedia http://en.wikipedia.org/wiki/List_of_discrete_event_simulation_software and http://en.wikipedia.org/wiki/List_of_system_dynamics_software). Jahangirian, et al (2009) review M&S across a range of disciplines and Taylor, et al (2009) profile M&S publishing trends. Nance and Sargent (2002), Robinson (2005), Hollocks (2006), Forrester (2007) and Richardson (2011) present reviews and reflections on the history aspects of M&S.

DES and SD are two powerful techniques that can be used to model and simulate a huge range of systems. However, in complex adaptive systems, where the behaviour of the system ‘emerges’ from the interaction of large numbers of entities, these techniques can be difficult to use. As will be seen in the collection of papers in this OR Essentials, agent-based modeling and simulation (ABMS), the third major M&S technique, began to evolve in the late 1980s driven by the need to conveniently study complex adaptive systems. The next section introduces its key concepts.

2 Agent-based modeling and simulation

One of the best introductions to ABMS is Macal and North’s Tutorial (Macal and North 2010; Chapter 2 in this collection) and this section uses their definitions to outline ABMS. They introduce ABMS as having roots in the investigation of complex systems (Waldrop, 1993; Flake, 2000), complex adaptive systems (Holland, 1992; Lansing, 2003) and artificial life (Langton, 1995). Arguably, therefore, ABMS has evolved as a ‘natural’ response to the needs of complex systems modeling. A question that a student interested in this subject should always keep an open mind as to which modeling technique(s) could be used to study a system. As will be seen in this collection, ABMS allows some systems to be represented in a more rational and comprehensible way than would be the case with other M&S techniques. In DES we focus on how entities pass through a network of queues and activities, in SD we focus on stocks (entities), their flows and their interdependence, and in ABMS we focus on the agents and their relationships with each other and their environment. For example, in the scenario that began this introduction, the A&E Unit could be represented by all the three techniques. However, the queuing network structure that most A&E Units have maps more easily to DES. A DES of an A&E Unit could be used to investigate appropriate staffing levels to reduce patient waiting time. A SD model could then be used to study the relationships within the host hospital to provide those staffing levels with respect to the rest of the hospital as these could be appropriately represented as stocks and flows. As will be seen, it might be argued that ABMS is more difficult to use in these two M&S scenarios. However, if we wanted to study the response time of an ambulance service, where the correct representation of ambulance behaviour and the impact of the service’s environment, then ABMS allows us to conveniently model and simulate these elements. For balance the following literature illustrates how both DES and SD can be applied to the same settings. Eatock, et al (2011) use DES, Lane, Monefeldt and Rosenhead (2000) use SD and Laskowski and Shamir (2009) use ABMS to model an A&E Unit. Gunal and Pidd (2011) use DES and Harper (2002) uses SD to model wider hospital performance; Meng, et al (2010 and Chapter 4 of this book) use ABMS to study hospital-wide infection management. With new advancements in distributed simulation and simulation software supporting multi-paradigm modeling it is becoming increasingly easier to create hybrid simulations consisting of combinations of DES, SD and ABMS. Swinerd and McNaught (2014) discuss the use of ABMS and SD to model the diffusion of technological innovation, Djanatliev, et al (2014) investigate ABMS and SD for health technology assessments, Anagnostou, et al (2013) demonstrate how ABMS and DES can be used for simulating emergency services, and Viana, et al (2014) use DES and SD to model infection spread. For further examples of simulation in healthcare, Brailsford, et al (2009), Mustafee, Katsaliaki and Taylor (2010) and Gunal and Pidd (2010) provide reviews of a wide range of examples. Taylor, et al (2012), Taylor, et al (2013a), Taylor, et al (2013b) and Taylor, et al (2013c) discuss contemporary grand challenges for M&S and consider the future of ABMS.

What is an agent-based model? An agent-based model typically has four aspects:

• A set of autonomous agents—each agent has a set of attributes that describe the state of the agent and a set of specified behaviours (rules that govern the behaviour of the agent) that define how an agent behaves in response to changes in its environment and, perhaps, towards a set of goals or objectives (eg, in an evacuation scenario we might be interested in understanding how people might leave a building and therefore wish to model individuals as agents. Their attributes might represent the speed at a person moves, the location of the person in the building; their behaviours might be the strategy that they use to move along corridors, how confused they might be, etc; and their goals might be which exit they are aiming for).
• A set of agent relationships—each relationship defines how each agent interacts with other agents and its environment. This also implies how each agent is ‘connected’ to other agents, that is an ‘underlying topology of connectedness’ (eg, how people interact as they attempt to leave the building).
• The agent’s environment—the ‘world’ in which the agents exist, that is the minimum set of ‘global’ variables or structures that are needed to define how the agents react to their environment (eg, the fire alarm, the building that the students are walking through, the capacity of each corridor, etc).
• A ’system’ is therefore composed of the set of agents, the environment and their relationships. A system has a clearly defined boundary with well-defined inputs and outputs (if appropriate) (eg, the building that is being studied for evacuation).

An agent-based model is created using an appropriate programming language, software tool or toolkit such as those described in the articles of this OR Essentials. These tools typically provide facilities to simulate an agent-based model by repeatedly executing the behaviours and interactions of the agents. For example, in our evacuation simulation, each student agent would have a description of how they react to the alarm, to other students and the various parts of the building. The first cycle of simulation would simulate the first movement of the students towards an exit and each student’s reaction to other students. Each subsequent cycle would continue to progress the students through the building.

When would it be appropriate to use ABMS rather than alternative techniques? There are many views expressed on this matter (see, for example, Brailsford (2014); Chapter 16 of this collection). However, the decision when to use an ABMS approach is often confused with when to use ABMS technology. For example, following the GC Panel at the 2013 Winter Simulation Conference (Taylor, et al 2013c), there was a rather lively discussion about whether or not a general purpose DES package could be used for ABMS rather than using a specially designed ABMS toolkit. The two views were essentially that a DES package could, depending on the package, be used for ABMS but an ABMS toolkit has dedicated support for agent-based simulation that would have to be recreated in the DES package. What was common to both views was that both were taking an ABMS approach and that the debate was which simulation software to use. Today, simulation software is very advanced and some DES software can be made to behave in an ABMS-like manner with some effort. Indeed, some simulation packages can support multi-modeling and support ABMS, DES and SD.

The papers of this OR Essentials collection will help in understanding what is really meant by ABMS. However, the following section expands each of the above elements of ABMS and might be taken into account when deciding to use ABMS.

2.1 Agents

An agent is autonomous, is self-directed and can function independently of other agents and the environment. An agent has a clear boundary between itself, other agents and its environment. It is a clearly identifiable ‘individual’ that is self-contained and uniquely identifiable. Each agent can be distinguished from every other agent by its attributes. These attributes form an agent’s state, typically a collection of variables. The state of an agent-based simulation is the collection of every agent’s state and the environment. Agents interact with and react to other agents and their environment. An agent bases its decisions through that interaction. Agent behaviours may be represented by simple collections of if-then-else rules, complex artificial intelligence techniques (neural networks, genetic programs, machine learning, etc) (Russell and Norvig, 1998), or even by sub-models (which in turn may be other forms of M&S). As an agent-based simulation progresses, the interactions of an agent with itself, other agents and the environment change the agent’s state. In an agent-based simulation there might be several different types, or classes, of agents.

2.2 Agent relationships

Agent relationships or interactions can be simple or extremely complex. A general principle of modularity exists and factors such as coupling and cohesion that exist in software engineering are in play. For example, if two types of agent have an extremely complex and tightly coupled relationship where their functional boundary is difficult to define, then the two types of agent might be better conceptualized as a single agent. Agent relationships must be clearly specified and the boundaries between agents must be clear. The reason for this is that agents must be capable of autonomy—an agent must be capable of making its decisions based on its own state and that of the environment. Not all agents must interact with every other agent. If an agent needs to make a decision based on the state of another agent then it must interact with that agent to discover it. Connections between agents can be described by the ‘topology’ of the agent-based model, that is, a logical or physical (or both) map of the agents and their interconnectivity. This topology can change during the simulation.

2.3 Agent environment

The environment is the elements of the system that agents interact with and is not considered as being an agent in its own right, that is, it is passive and global (it does not actively assert behaviour and it potentially affects all agents). It may have a simple or complex boundary, depending on the system being modeled.

3 Overview of OR Essentials: agent-based modeling and simulation

To further introduce ABMS and related key issues, this edition of the ...

Table of contents

• Cover
• Title
• Copyright
• Contents
• List of Figures and Tables
• 1 Introducing agent-based modeling and simulation
• 2 Tutorial on agent-based modeling and simulation
• 3 Some insights into the emergence of agent-based modeling
• 4 An application of agent-based simulation to the management of hospital-acquired infection
• 5 An agent-based simulation approach for the new product diffusion of a novel biomass fuel
• 6 Agent-based modeling and simulation of urban evacuation: relative effectiveness of simultaneous and staged evacuation strategies
• 7 Towards the development of a simulator for investigating the impact of people management practices on retail performance
• 8 A multi-agent simulation of the pharmaceutical supply chain
• 9 Workflow scheduling using multi-agent systems in a dynamically changing environment
• 10 Credit risk: an agent-based model of post-credit decision actions and credit losses in banks
• 11 The development of new infantry tactics during the early eighteenth century: a computer simulation approach to modern military history
• 12 A generic testing framework for agent-based simulation models
• 13 Successful approaches for teaching agent-based simulation
• 14 Discrete-event simulation is alive and kicking!
• Index