Modelling and Simulations Agent-Based

Agent-Based

Modelling and Simulations

Simulation

Agostino Poggi

System, Model & Simulation

♦ System

 An actual or theoretical system in which distinct entities interact

♦ Model

 A reproduction of the system at an appropriate level of granularity

♦ Simulation

 Designing a model of a system, executing the model on a computer, and analyzing the execution output

Simulation Activities

Simulation Goals

♦ Imitate the operation of a real-world process or system over time

♦ Prediction

 Model should produce quantitatively correct predictions depending on its input values

♦ Explanation

 Qualitatively significant results are sufficient for

understanding the reaction of the system to input values

When Is Appropriate (1/3)

♦ Enables the study of an experimentation with the internal interactions of a complex system, or of a subsystem within a complex system

♦ Informational, organizational and environmental changes can be simulated and the effect of those alterations on the model’s behavior can be

observer

♦ Knowledge gained in designing a simulation model can be of great value toward suggesting

improvement in the system under investigation

When Is Appropriate (2/3)

♦ By changing simulation inputs and observing the resulting outputs, valuable insight may be obtained into which variables are most important and how variables interact

♦ Can be used as a pedagogical devices to reinforce analytic (exact) solution methodologies

♦ Can be used to experiment with new designs or policies prior to implementation, so as to prepare for what may happen

♦ Can be used to verify analytic solutions

When Is Appropriate (3/3)

♦ Requirements for a machine can be determined by simulating its different capabilities

♦ Simulation models designed for training, allow

learning without the cost and disruption of on-the- job learning

♦ Animation shows a system in simulated operation so that the plan can be visualized

♦ Modern systems (factories, service organizations, computing systems, …) are so complex that the

interactions can be treated only through simulation

When Is Not Appropriate (1/2)

♦ Simulation should not be used when the problem can be solved using common sense

♦ Simulation should not be used if the problem can be solved analytically

♦ Simulation should not be used, if it is easier to perform direct experiments

♦ Simulation should not be used, if the costs exceeds savings

♦ Simulation should not be performed, if the resources or time are not available

When Is Not Appropriate (2/2)

♦ If no data are available, not even estimate simulation is not advised

♦ If there is not enough time or persons are not available, simulation is not appropriate

♦ If managers have unreasonable expectation or the power of simulation is over estimated, simulation may not be appropriate

♦ If system behavior is too complex or cannot be defined, simulation is not appropriate

Advantages (1/2)

♦ Studies about systems can be done in the design stage

♦ Models are run rather than solver

♦ New policies, operating procedures, decision rules, information flow can be explored without disrupting the ongoing operations of the real system

♦ New hardware designs, physical layouts,

transportation systems can be tested without committing resources for their acquisition

♦ Hypotheses about how or why certain phenomena occur can be tested for feasibility

♦ Time can be compressed or expanded allowing for a speedup or slowdown of the studied phenomena

Advantages (2/2)

♦ Insight can be obtained about the interaction of variables

♦ Insight can be obtained about the importance of variables to the performance of the system

♦ Bottleneck analysis can be performed finding indication where work-in-process, information

materials and so on are being excessively delayed

♦ A simulation study can help in understanding how the system operates rather than how individuals think the system operates

♦ What-if questions can be answered (useful in the design of new systems)

Disadvantages

♦ Model building requires special training

♦ Simulation results may be difficult to interpret

♦ Simulation modeling and analysis can be time consuming and expensive

♦ Simulation is used in some cases when an analytical solution is possible or even preferable

Simulation Model

♦ Allows to study the behavior of a system as it evolves over time

♦ Takes the form of a set of assumptions concerning the operation of the system

♦ Assumptions are expressed in relationships between the entities of the system

 Mathematical relationships

 Logical relationships

 Symbolic relationships

System Components

♦ Entity

 Is an object of interest in a system

♦ Attribute

 Denotes the property of an entity

♦ Activity

 Is a process causing changes in a system

♦ State

 Is a collection of variables necessary to describe a system at any time

♦ Event

 Is an instantaneous occurrence that may change the state of the system

Modelling Dilemma

Simplicity

Generality

Lack of error (accuracy of results) Realism

(design reflects observations)

System Environment

♦ External components which interact with the

system and produce necessary changes are said to constitute the system environment

♦ In modeling systems, it is necessary to decide on the boundary between the system and its

environment

♦ This decision may depend on the purpose of the study

System Adjectives (1/2)

♦ Endogenous

 Is used to describe activities and events occurring within a system

♦ Exogenous

 Is used to describe activities and events in the environment that affect the system

♦ Closed

 Is used for defining a system for which there is no exogenous activity and event

System Adjectives (2/2)

♦ Open system

 Is used for defining a system for which there are exogenous activities and events

♦ Continuous

 Is used for defining a system in which the changes are predominantly smooth

♦ Discrete

 Is used for defining a system in which the changes are predominantly discontinuous

Model Types

♦ Mathematical model

 Represents a system through a symbolic notation and mathematical equations

♦ Static model

 Represents a system at a particular point of time

♦ Dynamic model

 Represents a system as it changes over time

♦ Deterministic model

 Represents a system for which a specific set of outputs always corresponds to the same set of inputs (it does not contain random variables)

♦ Stochastic model

 Represents a system having one or more random variables as inputs that lead to random outputs

Simulation Types Classification

♦ Discrete versus continuous time

♦ Stochastic versus deterministic

♦ Macro versus micro

Discrete Event Simulation

♦ Model

 Finite state machines, queues, Petri nets, …

♦ Execution

 Read the “queue” of events and trigger new events as each event is processed

♦ Applications

 Diagnosing, business decisions, networks analysis, …

Continuous Dynamic Simulation

♦ Model

 Partial or ordinary differential equations

♦ Execution

 Periodic numerical resolution of equations

♦ Applications

 Flight simulators, electrical circuits, …

Monte Carlo Simulation

♦ Model

 Can be almost anything

♦ Execution

 Generate inputs randomly from the domain and perform a deterministic computation on them

♦ Applications

 Physics, engineering, applied statistics, …

Cellular Automata

♦ Model

 Regular n-dimensional grid of cells whose state is function of the state of their neighborhood

♦ Execution

 Periodic application of rules which determine state of a cell as a function of neighboring cells

♦ Applications

 Theoretical computer science, mathematics, biology, physics, engineering, cryptography, …

Macro Simulation

♦ Model

 Complete system is modeled as one monolithic entity

• Populations are averaged together

• Model attempts to simulate changes in these averaged characteristics for the whole population

♦ Execution

 Periodically update the state variables describing the system

♦ Applications

 Naturally applies to systems that can be modeled

centrally and in which the dynamics are dominated by physical laws

Micro Simulation

♦ Model

 Explicitly attempts to model specific behaviors of specific individuals

♦ Execution

 Periodic communication between individuals

♦ Applications

 Most appropriate for domains characterized by a high degree of localization and distribution and dominated by discrete decisions

Simulation Techniques

♦ By hand

♦ Spreadsheets

♦ Computational mathematics systems

♦ Programming in general purpose languages

♦ Simulation languages

♦ Simulation environments

Simulation Paradigms

Lotka-Volterra Prey Predator Model

Size of the prey population at time t

Size of the predator population at time t

Evolution of prey population Evolution of predator population

Simulation Time

♦ Simulation execution consists in stepping through time while updating the variables in the model

♦ In continuous-time models (e.g., differential

equations) time steps can be reduced indefinitely

♦ In discrete-time models time is quantized somehow

 Leap through time using event scheduling

 Employ small time increments using time slicing

Simulation Steps

♦ Problem formulation

♦ Setting of objectives and overall project plan

♦ Model conceptualization

♦ Model translation

♦ Model validation and verification

♦ Documentation and reporting

Problem Formulation

♦ Every study begins with a statement of the problem, provided by policy makers

♦ Analyst ensures its clearly understood

♦ If it is developed by analyst, policy makers should understand and agree with it

Objectives

♦ Objectives indicate the questions to be answered by simulation

♦ At this point a determination should be made

concerning whether simulation is the appropriate methodology

♦ Objectives must be made explicit through the definition of a project plan

Project Plan Definition

♦ A statement of the alternative systems

♦ A method for evaluating the effectiveness of these alternatives

♦ Number of days required to accomplish each phase of the work with the anticipated results

♦ Number of people involved

♦ Cost

Model Conceptualization

♦ Construction of a model of a system is probably as much art as science

♦ Art of modeling is enhanced by an ability

 To abstract the essential features of a problem

 To select and modify basic assumptions that characterize the system

 To enrich and elaborate the model until a useful approximation of results

♦ Thus, it is best to start with a simple model and build toward greater complexity

♦ Model conceptualization enhance the quality of the resulting model and increase the confidence of the model user in the application of the model

Model Translation

♦ Real-world systems result in models that require a great deal of information storage and computation

♦ It can be programmed by using simulation languages or special purpose simulation environments

♦ Simulation languages are powerful and flexible

♦ Simulation environments can reduce development time

Validation

♦ It is the determination that a model is an accurate representation of the real system

♦ Crucial for guaranteeing that output of simulation will say something meaningful

♦ Achieved through calibration of the model, that is an iterative process of comparing the model to actual system behavior and their discrepancies

Verification

♦ Is the process of confirming that the model is correctly implemented

♦ Model is tested to find and fix errors in the implementation of the model

♦ There are many techniques that can be utilized to verify a model

♦ In particular, many software engineering

techniques used for software verification are applicable to simulation

Validation & Verification Process

Validation & Verification Procedures

Instruments for Output Analysis

Program Documentation

♦ Can be used again by the same or different analysts to understand how the program operates

♦ Further modification of the model will be easier

♦ Model users can change the input parameters for better performance

Process Documentation

♦ Gives the history of a simulation project

♦ Result of all the analysis should be reported clearly and concisely in a final report

♦ Enable to review the final formulation and

alternatives, results of the experiments and the recommended solution to the problem

♦ Final report provides a vehicle of certification

Some Main Simulation Tools