Transcript ABM Utility Talk January30/08

The Utility of Agent Based Models:
Applications to Epidemics, Epizootics,
Preparedness Planning, etc.
— Opportunities for Research
Robert D. McLeod [email protected]
Professor ECE University of Manitoba
Internet Innovation Centre (IIC)
Dept. Electrical and Computer Engineering
University of Manitoba
© IIC, Jan. 2009
Internet Innovation Center
Overview

Part One: ABM Introduction


Motivation: Interest in modeling complex systems
Part Two: Examples of ABM Utility



Epidemic modeling: Discrete Space Scheduled Walker
Epizootic modeling:
Patient Access and Emergency Department Waiting Time
Reduction

Part Three: Extensions and Opportunities

Summary/Discussion
Interspersed with pop science references and questions
Internet Innovation Center
1
Overview

Goals (Future) : A high utility ABM simulator


Epidemic, preparedness, recovery, mitigation, policy
Goals (Today): Garner Interest toward a MITAC$ grant


Apply as a seed project May/09, w/blessing(collaboration)
Looking for $20K as matching funds (sources or leads)
Internet Innovation Center
2
Part 1: Book Reviews/Motivation

“World Without Us”: Alan Weisman

“Pandemonium”: Andrew Nikiforuk

“The Numerati”: Stephen Baker

“Super Crunchers”: Ian Ayres

“The Tipping Point”: Malcolm Gladwell

“The Black Swan”: Nassim Taleb

“Fooled by Randomness”: Nassim Taleb

“The Man Who Knew Too Much: Alan Turing and the
Invention of the Computer”: David Leavitt
Internet Innovation Center
3
Part 1: Agent Based Modeling

General Interests in Complex Systems and
Modeling

Much of this research resulted from a
Programming Challenge

Make the “equations” as simple as possible, but
not simpler, Albert Einstein

ABM is computational modeling essentially devoid
of governing equations

ABMs are pure mathematics.

Is that a G.H. Hardy reference? No, it’s a G. Boole reference.
Internet Innovation Center
4
Making models more useful
“You can observe a lot by watching:”― Yogi Berra
“Prediction is very difficult, especially
about the future:” Niels Bohr
“In the country of the
blind the one-eyed
man is King”: ―
Desiderius Erasmus
Internet Innovation Center
How?: Data Mining
and Statistical
Inferencing
Refs: Wikipedia
5
Part 2: Agent Based Modeling Utility

App1: Epidemic modeling - DSSW Model


App2: Epizootic modeling


A nice attribute about ABMs in general is that
they are ideal idea communication vehicles
An extension to areas where ABMs have not
been fully exploited
App3: Modeling an Emergency Department

Another area where ABM utility can be
demonstrated
Internet Innovation Center
6
App1: Initial Specification for Epidemic
Modeling

Basis idea: Data mine where possible the basic tenets of
people-people interactions. (Often Disparate Sources)


Topology: Data mined from maps
Behaviour: Data mined from demographics

Our approach develops models based on “real” network
topologies and “scheduled” walkers.

The goal of the research is to shed additional light on the
problems associated with very complicated phenomena
through “data-driven” modeling and simulation and
statistical inference.
Internet Innovation Center
7
The Model

Data mining is a common theme in modern information
technology:




Analytical methods may not exist or are overly complex.
Data exists and can be readily extracted.
Statistical methods can now more easily deal with the vast
amount of data that is available (or becoming so).
Our work here is an attempt to help promote data-driven
epidemic simulation and modeling:


Where data is available we demonstrate its utility, where
unavailable we demonstrate how it would be utilized.
Unavailable data refers to practical or political limitations on
access, rather than technical or theoretical availability.
Internet Innovation Center
8
“Where”: Topological Data Sources
Google Earth with Overlays
Google Maps
Correct by construction small world topologies
Internet Innovation Center
9
“Who and When”

Of similar importance to location (where), is the agents
(who) are being infected.

This is data that is generally technically available but
may be practically unavailable.

Our model attempts to illustrate how the data would be
used if available.

An agents’ schedule (when) is also of critical importance.
This data is more typically inferred rather than explicitly
available, but as we are primarily creatures of habit
reasonable assumptions can be made.
Internet Innovation Center
10
“What”

The what here is typically a disease, either bacterial or
viral, communicated with an associated probability of
contraction when in contact with an infectious agent.

Example 1 of “stochastic” behaviour:


Example 2 of “stochastic” behaviour:


Modified schedule when ill: Low mobility when sick or getting
sick. (agent “decides” to stay home)
Weighted random schedule. (Don’t feel like going to work today)
Example of contact:

Physical touch, third party (door knob), cough.
Internet Innovation Center
11
Implementation

Based on the model as described above, it should be
clear that our underlying simulation model is that of a
Discrete-Space Scheduled Walker (DSSW), in contrast
to other models that are more traditionally based on
random or Brownian walkers on artificial topologies.

We attempt to capture the most important aspects of
real-people networks, incorporating (by construction)
notions such as “small world” networks, scale free
networks, “it is what it is”.
(nota bene)
Internet Innovation Center
12
“What if”
I live here
I take this bus
I work here
Internet Innovation Center
13
City of Winnipeg, population: 635,869
The User Interface to DSSW
• Parameters for simulation are
set up in a number of files and the
user can step or loop through the
simulation at any given rate.
• During the simulation, a
number of plots and statistics
are collected and logged to a
web server where the user
can then further analyze the
simulation run.
Internet Innovation Center
14
Analysis

Some data that is available on
the corresponding web server
Internet Innovation Center
15
Seasonal Variations

Seasonal variations are well
known and provide fairly well
“labeled” data for comparison

The figure illustrates the type of
data available

Comparison allows for
a tuning of parameters
to more closely reflect
actual data collected
for a particular disease
Internet Innovation Center
16
Mutations
“tipping point”
“Seasonal Variation”


A mutation to a deadlier strain or a sudden variation in the
mode of transmission (e.g. virus shift or drift, bioterrorism)
Other uses of the simulator would be in helping to evaluate the
extent of inoculations or policies in the event of a simulated
outbreak. This will allow for epidemiologists to “partially close
the loop” when evaluating policy. (ABM utility, ref. CDC)
Internet Innovation Center
17
App1: DSSW Summary




Introduced a reasonable method of epidemic modeling,
taking advantage of opportunities for data mining and
scheduled walkers.
The basic characteristic of the model is to extract and
combine real topographic and demographic data. This
work shows that model creation using real data is indeed
feasible, and will likely result in better characterization of
the actual dynamics of an epidemic outbreak.
Further work will focus on refining the model, and
validating the afore-mentioned conjecture.
Complementary to “equation based approaches”
Internet Innovation Center
18
App2: ABM Potential for Epizootics


Epizootics: “outbreak of disease affecting many animals”
Agent based modeling of epizootics.
 Domestic, feral, and/or natural
“ABBOTSFORD, B.C. - The H5
avian influenza virus has been
confirmed on a commercial turkey
farm in British Columbia's Fraser
Valley, and as many as 60,000
birds will be euthanized, the
Canadian Food Inspection Agency
said Saturday.”
January 24/09
Internet Innovation Center
19
ABM Potential for epizootics


Nicely “constrained” problem: Many Intensive Livestock
Production Operations are nearly “Farrow to Fork”
Best chances of ABM demonstrated utility  Cattle, swine and poultry
e.g. A pork producer should be interested in
the potential of an ABM as a tool in modeling
a swine production environment.
Extendable beyond a single farm to an entire
region including transport and processing.
Allow CFIA to Model: Bio-security measures
Figure 3
Internet Innovation Center
20
Similar ABMs for Poultry




Broiler grow-out
intensive unit
production.
Similar epizootic
concerns
Man made pathogen reservoir
Similar problems in other
monocultures
Internet Innovation Center
21
Mobility and Infection Longevity
Percent dead
100%
Mobility/Longevity Impact
Substantive shift in the “Percolation
Threshold”
Percolation threshold is like a tipping point
Mobility has a big effect:
“The mobility threshold for disease is a
critical percolation phenomenon for an epizootic”
5%
42%
Internet Innovation Center
Population
22
Percolation with mobility.
Our study was a very preliminary attempt to use ABMs for ILPO
Although crude, clearly illustrates the
impact of mobility on disease spread
Provides design feedback on ILPOs
w/o mobility
with mobility
Disease Spread
Internet Innovation Center
23
App3: ABMs for Patient Access


Methods for reducing hospital Emergency Department
waiting times and patient diversion.

Useful for closing the loop when evaluating policy decisions

Useful across a regional hospital authority for load balancing
(patient diversion policies)
Agent based simulation of Emergency Department

Models patient flow through the modeling of individuals

(patients, doctors, service agents (registration, triage)
Internet Innovation Center
24
Emergency Department Scenario
Basic ED setting
with data collection
resources
illustrated.
i.e. Empirical data
collected here
could be used in
the ED and patient
diversion simulator.
E.g. Modification of
patient arrival and
treatment times.
Provide initial
conditions for
simulation
Internet Innovation Center
25
Metropolitan Multiple ED Scenario
Integrated telecom
backbone for a regional
health authority.
Data backhauled to a
central server (CORE) for
processing, simulation, and
policy optimization.
Illustrates use of simulation
enhanced patient diversion
policy.
e.g. Ambulances and walk
in patients.
Internet Innovation Center
26
Simulation “Proof of Concept”

Visual Simulation Suite Screenshot

Object oriented (OO), open-source, visual simulator to analyze and forecast
emergency department waiting times.

EDs can be instantiated with various resources, patient loads and associated
triage levels
Internet Innovation Center
27
Simulation Scenarios

City wide scenarios

Two EDs with two doctors, two EDs with three doctors,
two EDs with four doctors.

Effect of different staffing levels is compared when there is no
communication (i.e. no patient diversion)

Same basic scenario is used to compare patient diversion
models.
Internet Innovation Center
28
Simulation Scenario (Patient Diversion)

Patient diversion modeled using Random Early Detection
(RED) algorithm from Telecommunication Network
Engineering.

After a threshold in queue length is reached, the probability of
a patient being diverted increases from 0.

Random RED, patients diverted to random ED


Requires local ED information only
Guided RED, patients probabilistically sent to EDs with fewer
patients waiting

Requires city wide communication and coordination
Internet Innovation Center
29
Simulations and results

Varying the number of Doctors, no patient diversion
Two Doctors
Queue Lengths:
For fewer doctors
queue lengths are
longer.
Three Doctors
Four Doctors
Internet Innovation Center
30
Simulations and results

Varying redirection policy, averaged across all EDs
No diversion
Queue Length:
Scenario with the
most information
sharing
experiences the
shortest queues
without additional
resource
allocation
Diversion to
random ED
Probabilistic diversion to less busy ED
Internet Innovation Center
31
Demonstration:

Video on YouTube

Extensions:


Machine Learning for Policy and Provisioning
Use the model as a starting environment for modeling the spread of an
infectious disease within a Hospital.
Internet Innovation Center
32
Making models more useful
Agree
“All models are wrong
but some models are
useful.”
― George E.P. Box,
Statistician
“Truth is ever to be
found in the simplicity,
and not in the
multiplicity and
confusion of things.”
― Sir Isaac Newton
Perhaps truth can actually be found in the multiplicity
and confusion of things! ― Us
Ref: Wikipedia
Internet Innovation Center
33
Part 3: Possible Extensions and data
Mining Opportunities



At present DSSW epidemic ABM appears mainly well
suited to “egalitarian” type diseases
 “Who agnostic” disease
Here we present a few extensions and opportunities well
suited to mining of disparate sources for epidemic
modeling
Extensions of utility to secondary/tertiary interest groups
 Manitoba Hydro, Peak of the Market, Manitoba EMO,
Public Safety, etc.
 Preparedness planning, mitigation and recovery
Internet Innovation Center
34
Data Mining Comment:



Data Mining is the process of processing large amounts
of data and picking out relevant information. (wiki defn:
common notion)
Here data mining is 2 phase.
Mine “what to mine”
 Mining “what to mine”
 Mining the “what”
Data Fusion: combine
data from multiple
sources
Internet Innovation Center
Data Mining
Data
Fusion
35
DSSW Extensions: Hierarchy


Incorporate Hierarchy
 Intracity and Intercity
 Basic modality remains: data-driven models of
discrete space- and time- walkers, mined from
available sources.
Cities are largely autonomous
 Allows for the problem to remain tractable and allow
for efficient modes of computation (parallelism can be
exploited).
Internet Innovation Center
36
Extensions: Extracting Patterns of
Behaviour


Patterns of behavior can be taken from tracking
technologies that are in place albeit not mined for use in
epidemic modeling.
 E.g. Financial Transaction Profiling
 Usually mined to detect fraud
 E.g. Cell phone tracking, “where are you” services
 By default the service provider already knows
where you are, even more so with GPS
Obstacle: Privacy
Internet Innovation Center
37
Related Research: Extracting Patterns
of Behaviour


Consumer wireless electronics: MAC snooping and
tracking. (non obvious data source)
 Bluetooth headsets (ingress and egress of signalized
arterials)
 Similar protocols for WiFi
 Device-enabled Kiosks and vending machines
Security cameras and systems with person detection
 Monitoring for behaviour patterns those of illegal
activities and terrorist threats
Internet Innovation Center
38
Related Research: Extracting Patterns
of Behaviour from Demographics
Clickable(minable) neighborhood demographic information:
http://www.toronto.ca/demographics/profiles_map_and_index.htm
Internet Innovation Center
39
Related Research: Extracting Patterns
of Behaviour continued


Tracking subway ridership.
 Token data mining of ridership
 Their Objective: Bioterrorism impact
Mining online transportation information systems
 Helsinki public transport
 Their objective is to provide information for riders,
ours would be using this data to model the movement
of people with a city for disease modeling and its
possible spread
Internet Innovation Center
40
Related Research: Real-time Helsinki
Public Transport Information
Internet Innovation Center
41
Related Research: Ubiquitous Vehicle
Tracking Cameras
Modeling Arterials
for traffic flow.
ITS data useful for
epidemic modeling
Similar data is
available for air
traffic.
Ref: http://www.edmontontrafficcam.com/cams.php
Internet Innovation Center
42
Related Research: Extracting Patterns
of Behaviour (Economic Impact)

Economic Impact: Costs associated with implementing
policy. (ref: Brookings)
 Specifically, the economic impact of restricting air
travel as a policy in controlling a flu pandemic.
 Models global air travel and estimates impact and
cost associated with travel restrictions.
 E.g. 95% travel restriction required before
significantly impairing disease spread
 Not a surprise (also they removed edges not
vertices, cf. percolation)
Internet Innovation Center
43
Related Research: Extracting Patterns
of Behaviour (Economic Impact)
Internet Innovation Center
44
Related Research: Google’s Flu trends


Researchers "found that
certain search terms are
good indicators of flu
activity.
Google Flu Trends uses
aggregated Google
search data to estimate
flu activity in your state
up to two weeks faster
than traditional systems"
such as data collected
by CDC.
Internet Innovation Center
45
Related Opportunity: Google’s Gmail





Google mail (gmail) provides an example of data
mining to extract coarse spatial behaviour patterns.
gmail, web/mail server has a reasonable estimate of
your activity status (busy, available, idle, offline, etc.).
In addition to status, your web browser's IP address
also provides coarse-grained information of where you
are logged in.
If I access gmail from a mobile device, this is also
known to various degrees.
Eric Schmidt, CEO of Google, said, "From a
technological perspective, it is the beginning."
Internet Innovation Center
46
Other sources of information/concern

Occasional/periodic mass gatherings

E.g. Olympics or other special event that may perturb an
overall or global simulation
E.g. The Hajj
 Largest mass pilgrimage in the world.
 2007 an estimated 2-3 million people participated.
 Conditions are difficult and thus it offers an
opportunity for a large scale disease such as
influenza to take hold.
 These people then disperse to their home countries,
many via public transport, and could easily influence
the spread and outbreak of the disease.

Internet Innovation Center
47
Mass Gatherings: Hajj
Tawaf, circumambulation of the
Ka’bah
Mosque at Ka’bah
Internet Innovation Center
48
Related Research: Extracting Patterns
of Behaviour (RFID tracking)

Although not as explicit or readily attainable, the
potential to extract “patterns of behavior” and
“interactions of agents” at critical institutions such as
hospitals can be made more feasible through the use of
RFID tracking.

As RFID sensor networks move from inventory solutions
to enhanced applications, data collected from RFID
tracking at clinics and hospitals can be envisioned as an
input to DSSW. (e.g. WiFi Campus tracking)
Internet Innovation Center
49
Preparedness, planning and mitigation

Preparedness planning: A massive undertaking but one
in which an ABM city model could be useful in providing
planners with policies and some degree of expectation
how goods and services could be provisioned in the
event of a catastrophe.

This aspect can be “catastrophe agnostic”

Simple investigations as to how long food/fuel/medical
supplies would last and could be distributed will be
modeled
Internet Innovation Center
50
Preparedness, planning and mitigation

Provisioning of resources extempore will lead to an
aggravated and worsening disaster.

Models can become an effective tool for any city.
 Specific model to their region

Allowing for provisioning not only of supplies but for
inoculation services as well as temporary hospital
and/or mortuary facilities.
Internet Innovation Center
51
Preparedness, planning and mitigation
Power generation: Remote
maintained by “healthy”
individuals: Stakeholders Hydro
Easily Isolated: Transportation wise
Stakeholders: MEMO
Food production/provisions: Local
Stakeholders: Peak of the Market
Water Supply: Remote: MEMO
Result: Pandemic Lag if Prepared
Internet Innovation Center
52
Multiple Hospital Model Patient
Diversion : Future Work

Incorporate empirical data mined from sources such as
Google/Globis real-time traffic to estimate delays the
ambulance would experience enroute
Internet Innovation Center
53
Summary



Presented our Agent Based Modeling approach to high
“utility” simulation.
 Emphasis on data mining of spatial topologies and
agent behavior patterns
Presented several indirect data sources
 Often no obvious connection to epidemic modeling
Presented potential extensions: Utility of ABMs
 Epidemics, Epizootics, ED Wait times
 Opportunities in preparedness planning, mitigation
Internet Innovation Center
54
Ideally one would like to model
everything: (someday will)





Threats: epidemic natural or bio-terrorist. (In progress)
 Model impact of policy
Model Food Supply:
 Intensive unit production facilities through from birth
to slaughter. (Proposal submitted, www.pork.org)
Model Food and Fuel Supply and Distribution:
 Guidelines for stock provisioning.
Model infrastructure: Transportation, water, power.
 Model impact of policy (Amenable to ABMs)
Assess interest in moving forward, from tertiary groups.
Internet Innovation Center
55
Exploring research opportunities

Being “devoid” of equations, agent based models allow
for a tradeoffs between specificity and utility.

We would like to be part of a larger modeling effort and
want to explore that possibility. Extend models beyond
epidemics to related areas of direct interest to Manitoba.

Trying to get an interested parties to provide some
degree of matching funds to apply for a MITACS seed
grant. May 2009.

Total matching funds we are targeting is 20K, providing
70K of funding if successful.

Leverage other efforts: Possible with some traction here
Internet Innovation Center
56
Dissemination efforts:

Epi-at-home.com: Future home of Epidemic ABM open
source project (DSSW)

Bio-inference.ca: Future home of ABM and data mining
opportunities (non obvious sources)



Epizootic, patient access, preparedness planning
Facebook group: “Pandemic Awareness Day”

Exploring social networks as an information tool

A non invasive information portal (50+ members)
A growing number of papers/proposals/talks.
Internet Innovation Center
57
IIC Contact: U of M ABM initiatives
Bob McLeod
Professor ECE
University of Manitoba
Internet Innovation Center
E3-416 EITC
University of Manitoba
Winnipeg, Manitoba
R3T 5V6
Acknowledgements:
Too many to list
Email: [email protected]
http://www.iic.umanitoba.ca
Internet Innovation Center
58