Where Are We
Up to this point, we have developed code that can read a model into memory
and write it back out again, detecting a variety of errors in the model.
The only point of writing the model out is to verify that the model has
indeed been read correctly.
This highway network model could be used for many purposes:
- We could use the model (augmented with map coordinates)
to display a map, the way Google Maps does.
- We could use the model to provide driving directions by running a
shortest path algorithm over the model.
- We could use the same model to run a simulation of traffic loading to
allow testing of the consequences of various proposed road improvements.
The logic circuit model we mentioned could also serve many purposes:
- We could use the model (augmented with 3-d coordinates)
to display the layout of the electronic components of a computer system.
This might be an intermediate point in chip design.
- We could use the model to run a simulation of a system of logic gates
in order to test the logical design of a new chip.
A neuron network model could also serve many purposes:
- We could use the model (augmented with 3-d coordinates)
to display a map of the physical anatomy of the neurons in an organism.
A neuroanatomist could use this model to express the results of study
of the actual organism.
- We could use the model to run a simulation of the activity of the nervous
system of the organism. This would allow us to compare our understanding of
how the nervous system works with actual measurements.
The model we have been referring to as an epidemic model is actually just
a model of a community.
- It could be used to generate traffic for a vehicle simulation as it models
people traveling homes, schools, workplaces and stores.
- The same model could be used to simulate the spread of news through a
pre-modern community that did not have newspapers or the Internet.
- The same model could be used to model the spread of an epidemic
through a community, the particular goal that motivated our discussion of
this model.
Our goal for the projects in this course is to build simulations, and the
time has come to discuss this in more detail.
Simulation
An old bumper sticker I picked up at a simulation conference said:
"Simulationists do it continuously and discretely."
The sticker was a joke because, while members of the general public reading
the sticker might guess one subject (sex), the actual statement is entirely
true when you read "it" as a reference to computer simulation.
There are two broad categories of simulation:
- Continuous simulation typically involves use of differential
equations to describe the behavior of a physical system, and the simulation
itself involves the numerical solution of those equations.
Continuous simulation models are common in fields as distinct as analog
electonics, weather forecasting and macro economics.
Here at the University of Iowa, the Hydraulics Institute is largely devoted
to continuous simulation of fluid flow. Their building was built in the era
when their research was largely done using actual tanks of water and even
water from the Iowa River, but today,
much of their work is done on computers, simulating not only water flow but
also atmospheric flow.
- Discrete-event simulation typically involves systems where the
behavior of the system can be described in terms of a sequence of events.
Between events, nothing happens, but at each event, parts of the model interact
to make changes in the simulation variables.
Discrete event simulations are common in fields as distinct as logistics
and digital logic simulation.
Almost all simulation models are based on simplifying assumptions. Most
physics models assume that air is a vacuum and that the earth is flat.
You can build bridges with these assumptions, although for medium and large
bridges, it is worth checking how the bridge responds to the wind. (The
Tacoma Narrows Bridge disaster of 1940 shows what can happen if you forget
the wind when
you design a large bridge -- it's in Wikipedia, watch the film clip.)
Our distinction between continuous and discrete models is also oversimplified.
There are mixed models, for example, where the set of differential equations
that describe the behavior of a system changes at discrete events. At each
such event, you need to do continuous simulations to predict the times of the
next events.
A Highway Network Model
In a highway network, the events we are concerned with are:
- Arrival at intersection:
When a car arrives at an intersection, it may have to wait for other cars
in the intersection to clear the intersection (we can simplify the model a bit
if we assume that cars spend only a fixed short time in the intersection),
and a car may have to wait for the light to change. If it does not have to
wait, the next event for that car is a road-entry event for the road the
car's navigation algorithm selects.
- Entry to road:
When a car leaves the intersection, it unblocks the intersection, allowing
another car to pass through (if one was waiting); it does this by scheduling
an entry-to-road event for that car. It also schedules the arrival
at intersection event for this car at the other end of the road this car is
entering. The time until the car arrives at the next intersection can be as
simple as just the travel-time for that road, or it can be a function of the
number of cars in the road, slowing down as the road grows more congested.
In addition, the time can depend on random factors or on such things as the
driver's simulated personality.
- Stoplight change:
Each intersection with a stoplight has a light that changes periodically
by scheduling stoplight changes at that intersection. With each change,
a different road (and the queue of waiting cars for that road) is unblocked,
allowing cars in that queue to proceed by scheduling a road-entry event for the
first waiting car.
Of course, the model can vary considerably in complexity. A simple model
might have a fixed travel time on each road segment, while a more complex
simulation might model congestion by having the travel time get longer if the
population of a road segment exceeds some threshold, where that threshold may
itself depend on the unpopulated travel time.
In a crude model, each car might make random navigation decisions at each
intersection. A more complex model might have each car follow a fixed route
through the road network, while a really complex model might include cars
with adaptive navigation algorithms so that drivers can take alternate
routes when congestion slows them on the path they originally planned.
A Digital Logic Model
In a network of digital logic gates connected by wires, we might have the
following events:
- Input to a logic gate changes:
The values of the other inputs to that gate are checked, using the rule
for that gate to compute the new output. For and gates, for example, if both
inputs are true, the output is true, otherwise it is false. But, gates do not
compute their outputs instantaneously, so if the new output differs from the
previous output, a change of the output of the gate is scheduled to happen
at a future time based on the time delay of this gate. In real logic used
in modern microprocessors, this delay is a fraction of a nanosecond.
- Output of a logic gate changes:
When the output of a logic gate changes, this change is transmitted to all of
the inputs connected to that output by wires, but wires do not transmit this
change instantly. In a perfectly straight wire in a vacuum with no conductors
nearby, the change travels down the wire at the speed of light. In real wires,
the top speed is closer to half that, and if the signal is being propagated
through the body of an integrated circuit chip, it can be 1/10 the speed of
light. So, the input changes at the far end of a wire are scheduled to take
place some delay after the output of a gate injects a change into a wire.
The key element in the above that needs extra discussion is that if the output
of a gate is changed and then changed back very quickly, no output change
actually occurs. That is, there is a shortest pulse that the gate can
generate on its output.
A Neural Model
In a neural network model, with neurons connected by syapses, we might have the
following events:
- Primary synapse fires:
The voltage of the neuron at this time is computed, and then it is incremented
by the strength of this synapse. If the resulting voltage is above the
neuron's threshold, the neuron fires. This schedules synapse-fire events at
each outgoing synapse to occur at future times determined by the delay of each
synapse.
- Secondary synapse fires:
The strength of the destination primary synapse is adjusted by the strength
of this secondary synapse. Secondary synapses that operate this way can serve
as the basis of long-term memory because they can turn primary synapses on and
off.
The key element in the above that needs extra discussion is how the
voltage on a neuron changes with time. Between events, the voltage on a
neuron decays exponentially, slowly leaking away unless it is pumped up by a
synapse firing. So, for each neuron, we record:
- The voltage, v
- The time at which that voltage was known t
Now, if we want to know the voltage at a later time t', we use this
formula:
v_{t'} =
v_{t} ×
e^{k(t'–t)}
Of course, once you compute the voltage at the new time t',
you record the new voltage and the new time so you can work forward from that
the next time you need to do this computation. The constant k
determines the decay rate of the neuron (it must be negative).
In a simple model, all the neurons might have the same threshold and the
same decay rate, and all synapses might have the same strength.
More complex models allow these to be varied.
In simpler models, the voltage on a neuron goes to zero when that neuron
fires. In more complex models, the threshold has its own decay rate and the
threshold goes up when the neuron fires.
In complex models, the strength of a synapse weakens each time it fires because
the chemical neurotransmitter is used up by firing. During the time before
the next firing, the neurotransmitter can build up toward its resting level.
This allows the neural network to get tired if it is too active. (You can
actually see this effect at work in your visual pathways. Look at a bright
light and then look away, and you will see a negative afterimage that fades
as the synapses that were overexcited recharge.)
An Epidemic Model
In an epidemic model, where people move between places and their contact
patterns spread some disease, we have the following basic events:
- Person arrive at place:
The person is added to the list of people who might be infected because they
share that place, and if the person is contageous, the count of infected people
in that place is incremented.
When a person arrives at a place, the person might also schedule the return
trip home, but it is equally practical to schedule the return trip at the very
same time that the outgoing trip is scheduled, so at the start of the day,
an employee might schedule both their trip to work and their return trip that
afternoon. On arrival home, each person might look through the list places
they are associated with to find the next place on the list that they might
want to visit and schedule that outgoing trip.
- Person departing from place:
The person is removed from the list of people who might be infected because
they share that place, and if the person is contageous, the count of infected
people at that place is decremented. The distribution of travel times is
used to schedule the person's arrival at their destination.
Any time a person arrives or departs from a place, the number of infected
people in that place during the interval since the last arrival or departure,
times the length of that interval, times the probability of infection per unit
time for the place, gives the probablity that any person in that place during
that time will be infected.
- Person is infected:
Schedule the time the person's state will change from latent to
infectious.
- Person becomes infectious:
Schedule the time the person's state will change from infectious to
symptomatic, or possibly recover without exhibiting symptoms.
- Person becomes symptomatic:
Schedule the time the person's state will change from symptomatic to
bedridden, or possibly recover. The symptomatic state is when you know
you have something but you keep going about your affairs trying to tough
it out.
- Person becomes bedridden:
Schedule the time the person's state will change from bedridden to
either recovered or dead. Bedridden people cease obeying their schedules
and stay home.
- Person becomes recovered:
On recovery, people resume obeying their schedules, and resume traveling to
places.
- Person becomes dead:
Wherever that person is, remove them from that place, including from the
list of people at that place and the count of infectious people there,
and do not schedule any further activity for that person.
The above outline is appropriate for a "slow disease," that is, one where,
when you begin to feel bad while at work or school, you stay until the end of
the day before going home and staying home until better. The model would need
modification for a "fast disease," whith a sudden onset that sends people
home in midday.