Transcript agent-based simulation and model integration

AGENT-BASED SIMULATION
AND MODEL INTEGRATION
Agent-based Simulation (ABS)
Model Integration
OR/MS <-> OR/MS
ABS <-> ABS: Bio-terrorism and
traffic models
ABS <-> OR/MS:


ABS as Continuous Experimentation
Artificial labor market for US Army
recruiting
CHARACTERISTICS OF
AGENT-BASED SIMULATION
Simulation composed of one or more classes of agents
Each agent corresponds to one or more autonomous entities in
the simulated domain
Agents have behaviors, often defined by a set of simple rules
(computational models of behavior)
Agents can adapt dynamically
Agents can communicate with environment and with each other
“Bottom up”, emergent behavior results from nonlinear
interactions of agents
Inductive vs. deductive (computational explanation)
Complexity emerges from simplicity
MODEL INTEGRATION
“The creation of complex models by the reuse
and composition of existing validated models”
Models may be from many different
paradigms:
Optimization
Econometric forecasting
Discrete event simulation
Agent-based simulation
Monte Carlo simulation
System dynamics
-
Database
Neural networks
Partial diff. eqns
Network flow
Markov chains
etc, etc.
TYPES OF MODEL INTEGRATION
Black Box: independent solvers;
parameter passing
Communicating Processes: partially
interwoven solvers; parameter passing
ABS as Continuous Experimentation : All
models work from the same synthetic
environment
MODEL INTEGRATION EXAMPLE:
OR/MS <-> OR/MS
Demand
Forecasting
Volume
Volume
[Multiple regression]
Transshipment
Manufacturing
[Linear programming]
[Discrete event simulation]
Mfg_Expense
Pricing
Dist_Expense
[Optimization]
Price
Mfg_Expense
Volume
Financial
[Monte Carlo
simulation]
Net Income
Revenue
Dist_Expense
MODEL INTEGRATION: ABS <-> ABS
(INTRA-PARADIGM)
Example 1: Measured Response bio-terrorist
ABS developed at Purdue University uses 3
underlying models:
Epidemiological (smallpox, ebola)
Traffic/transportation: mobility of the populace
Crowd psychology
Example 2: TrafficLand ABS developed at
University of Aachen for modeling commuter
traffic
What are the obstacles to integrating these two
ABS?
MEASURED RESPONSE: AN ABS
FOR BIO-TERRORISM
Measured Response (MR) is a synthetic
environment that simulates the
consequences of a bio-terrorist attack in
fictitious mid-sized cities.
MR is developed on the Synthetic
Environment for Analysis and Simulation
(SEAS) platform.
SEAS allows the creation of fully
functioning synthetic economies that mirror
the real economy in all its key aspects by
combining large numbers of artificial agents
with a relatively smaller number of human
agents to capture both detail intensive and
strategy intensive interactions.
Over 450,000 artificial agents mimic the
behavior of the citizens such as the feeling
of well-being in terms of security (financial
and physical), health, information, mobility,
and civil liberties.
MR models the rate of transmission of
infections as a function of population
density, mobility, social structure, and life
style using an explicit spatial-temporal
model.
It uses the movement of individuals and the
exposure of susceptible individuals to
infected individuals to model the spread of
disease.
Model human behavior, emotions,
mobility, epidemiology, and well being
Calibrate the models based on
theoretical results
Validate the results against
empirical data
TrafficLand: AN ABS FOR
COMMUTER TRAFFIC
Simulates commuters’ decision-making and
behavior
Commuters have options between work and
home based upon
Expected travel times
Personal characteristics
Interactions with other commuters
Heterogeneous agents
CHALLENGES OF ABS INTEGRATION : Agent
Representation in Measured Response
Plan to continue education
Other employment interests
Can't get out if don't like the Army
Commitment too long
Doesn't allow enough contact with family/friends
No personal life in Army
Want to stay close to home
Do not want to be deployed overseas
Other military services more appealing
Be behind my civilian peers in career
Army pay very low
Have financial ability to pay for college
Army too dangerous
Basic training/boot camp too difficult
Army life too difficult
Family/friends have negative attitude of Army
Army has no role to play in global environment
Army conflicts with religious beliefs
Total
(202)
4.13
4.00
3.61
3.60
3.51
3.47
3.42
3.34
3.26
3.25
3.20
3.15
3.15
3.14
3.12
2.74
2.73
2.32
1st
Brigade
(36)
4.34
4.28
3.62
3.49
3.57
3.54
3.44
3.40
3.32
3.44
3.24
3.49
3.32
3.09
3.20
2.63
2.48
2.23
2nd
Brigade
(26)
3.69
3.58
3.76
3.96
3.81
4.12
3.65
3.58
3.72
3.50
4.04
3.08
3.38
3.58
3.16
3.12
2.96
2.38
3rd
Brigade
(47)
4.32
4.26
3.37
3.57
3.42
3.26
3.19
3.16
2.91
3.14
3.02
3.24
3.17
2.89
2.91
2.35
2.57
2.35
5th
Brigade
(53)
4.16
3.81
3.71
3.58
3.44
3.43
3.46
3.27
3.36
3.12
3.04
2.88
3.10
3.11
2.96
2.71
3.00
2.23
6th
Brigade
(40)
3.97
4.00
3.64
3.54
3.44
3.26
3.49
3.42
3.17
3.24
3.00
3.16
2.87
3.21
3.50
3.13
2.61
2.46
Decision Factors form the second helix
1
= Highest mean score
= 2nd highest mean score
= 3rd highest mean score
Gene information is
extracted from the
data to accurately
represent the
behavior of the agent
1
1
0
0
1
0
Gene2
Gene type: Education
Gene value: 0011 - High School
Gene1
Gene type: Gender
Gene value: 0001 - Male
CHALLENGES OF ABS
INTEGRATION: Agent
Representation in TrafficLand
Agents consist of:
Sensors: collection of observations
L-graphs: dynamic semantic networks
Sets of individual strategies
Preferences: pre-specified or inherited
Satisfaction measures for strategies
Action-executing modules
CHALLENGES OF ABS INTEGRATION
(INTRA-PARADIGM): Agent Communication
Intelligence
Security
Financial
Life
Communication
Exposure
S
Savings
Group
E
Health
Liberty
D
Safety
Print
X
Rumor
Electronic
U
True
Person
C
Infected
Environ.
T
Immune
Food
Basic
I
Behavior Primitives
Water
Shelter
I
nitiate
Do Nothing
S
earch
Well Being
E
valuate
Communicate
Carrier
D ecide
E X ecute
U pdate
Environment
DNA-like Behaviors, Ports, and Channels architecture allows accurate
representation of an agent’s intelligence and behavior
C ommunicate
T erminate
CHALLENGES OF ABS
INTEGRATION
(INTRA-PARADIGM): Agent
Communication in TrafficLand
Agents communicate via:
Direct messages
Usage of resources
Inheritance of characteristics and abilities
CHALLENGES OF ABS INTEGRATION
(INTRA-PARADIGM)
Agent Representation
Conceptual models for agents are completely different in MR
and TL;
Genes in MR are attributes; genes in TL are strategies
How to map individual agent in MR to one in TL and vice versa
Agent Behavior
Agent behavior in MR is function of attributes
Agent behavior in TL is dynamic based upon sensor data
Agent Communication
Inconsistent ACLs between MR and TL
How does an agent in TL communicate with an agent in MR?
Bottom Line: ABS have low level of reusability in
traditional sense; “Black box” integration may be best
we can hope for (if applicable)
MODEL INTEGRATION:
ABS <-> OR/MS
(INTER-PARADIGM)
Problems are less intractable in this situation
Several options exist:
Black box: ABS as just another model with data
aggregated to the right granularity (e.g., ABS as
demand forecast model in previous example)
OR/MS models as determinants of agent behavior
OR/MS models as ABS calibrators / validators
ABS as Continuous Experimentation: ABS as
platform for OR/MS models which work in the
virtual world established by the ABS
ABS AS “BLACK BOX”
Demand
Forecasting
Volume
[Agent-based
simulation]
Manufacturing
Volume
Transshipment
[Linear programming]
[Discrete event simulation]
Mfg_Expense
Pricing
Dist_Expense
[Optimization]
Price
Mfg_Expense
Volume
Financial
[Monte Carlo
simulation]
Net Income
Revenue
Dist_Expense
MEASURED RESPONSE:
MATHEMATICAL MODELS AS
DETERMINANTS OF AGENT
BEHAVIORS
Agent based Computational Environment
Genomic Computing
Behavior and Mobility Modeling
Epidemiological Modeling and Calibration
Person in the Loop
MEASURED RESPONSE:
EPIDEMIOLOGICAL MODEL
AS CALIBRATOR OF ABS
S
I
R
Susceptible-Infected-Recovered (SIR) model for
population N=S+I+R with no disease mortality.
Mass action transmission process, rate b, linear
recovery rate g.
dS
I
 b
S
dt
N
dI
I
 b S  gI
dt
N
dR
 gI
dt
ABS AS CONTINUOUS
EXPERIMENTATION
Simulation as a persistent process
Continuous availability of a virtual, or synthetic,
environment for decision support (ex: artificial labor
market)
Continuous, “near real time” sensor data from real world
counterpart (via data warehouse)
“Parallel worlds” interaction
Agents in the ALM developed using existing OR/MS
models as data mining tools from the data warehouse
Calibrate the ALM using existing OR/MS models
ABS as test bed for OR/MS models
ABS AS CONTINUOUS EXPERIMENTATION: PARALLEL WORLDS
Time
Compression
Simulation Loop
Synthetic
Environment
Behavior
modeling,
demographics,
and calibration
Decision Support Loop
Near exact replica
of the “real” world
SEAS architecture
Supports millions of
Artificial agents
Learn: Explore, Experiment,
Analyze, Test, Predict
Assess
SCM
ERP
CRM
Data
Warehouse
Real World
Environment
Data collection,
association,
trends, and
parameter
estimation
Implement
DECISION
XML Interfaces
UNIX/ORACLE
Real World and
Simulation Databases
The user(s) can
seamlessly switch
between real and
virtual worlds
through an
intuitive user
interface.
ABS AS CONTINUOUS
EXPERIMENTATION
DATA WAREHOUSE
PROGRAMMING AGENTS:
Data Mining using
Econometric Models,
Neural Networks, etc
to Specify Preferences
CALIBRATING AGENTS:
OR/MS models to
Validate Market
Behavior
OPTIMIZATION MODEL:
“Where are the best
locations for Recruit
Stations?”
ARTIFICIAL LABOR MARKET
DEMAND MODEL:
“What will be the recruit
pool by race, gender,
and location next year?”
ABS AS CONTINUOUS
EXPERIMENTATION: USAREC
ARTIFICIAL LABOR MARKET
Agent-based simulation designed to
capture the dynamics of a labor market
Agents represent individuals, or cohorts,
in the labor market
Humans play role(s) of organizations
Agents programmed with “rules of
engagement” + genetic structure
ABS AS CONTINUOUS
EXPERIMENTATION: DESIRABLE
ATTRIBUTES OF AN
ARTIFICIAL LABOR MARKET
Scalable
Agent Compression Ratio = (# Agents / # Individuals)  1.
Decomposable
Markets can be segmented by any criteria, e.g., by region,
by life style, by race, by gender, etc.
Evolutionary
Agents adapt to environment and to markets
Interaction with Real Counterpart
Agents learn from behavior in the real environment
Persistent
Always available
Laboratory for new OR/MS model development
USAREC AGENT PROCESS
Process
Channel
Port
Adjust factor
strengths
Budget amount
Recruiter
number
…
Port
Season = Spring
GDP = 1.5%
…
Port
Ports and channels structure allow us to have access to each agent in the Synthetic
Environment – e.g. we can implement self service, targeted advertisement, etc.
USAREC AGENT UNIVERSE
Only considered 1.4 million individuals,
age 17-21, interested in Army
Modeled 100,000 agents to represent
this population
Agent compression ratio = 14
Agent DNA consists of (age, gender,
race, mental_category, education,
region)
SUMMARY
ABS <-> ABS Integration
Reusability of simulations tends to be low
Integration most likely to occur at “black box” level
Integration of ABS requires consistent agent
representation and communication protocols
ABS <-> OR/MS Integration
OR/MS models link to ABS rather than to one another
May promote more consistency amongst models
Integrated data
ABS can serve as integrative environment for using
OR/MS models for data mining, calibration, and new
analysis
BACKUP SLIDES
AGENT-BASED SIMULATION
Characteristics of ABS
ABS and DES (discrete event simulation)
ABS and System Dynamics
ABS and Virtual or Synthetic
Environments
COMPARISON OF AGENT-BASED
and DISCRETE EVENT SIMULATION
DES relies upon probability distributions and
equational representations
“Bottom up” (ABS) vs. “Top down” (DES)
COMPARISON OF ABS and
SYSTEM DYNAMICS
ABS
System Dynamics
Process: Inductive
Process: Deductive
Unit of analysis: agent /
individual
Unit of analysis: feedback
loop / structures
Focus: Exploratory
research
Focus: Confirmatory
research
CHALLENGES TO
MODEL INTEGRATION
Model Representation: develop a uniform
representation usable across paradigms
exs:
structured models (Geoffrion)
metagraphs (Blanning and Basu)
graph grammars (C. Jones)
Model Communication : develop a
mechanism for models to “communicate” with
one another (e.g., pass variables)
CHALLENGES TO
MODEL INTEGRATION
Model Selection / Composition (Web
services problem): which model(s) are the
most appropriate for a problem and how do
we sequence the solvers?
Paradigm “Tunnel Vision”
Algorithm vs. Representation Focus