Chapter 12: State Transitions
This chapter describes how Transition Rules are used to decide what state an agent goes to next.
Transition Rules
Transition rules control the next state that the agent will assume. There are two kinds of transition rules:
Probabilistic rules
Default rules
Probabilistic Transition Rules
[ if (<test1> & <test2> & ... <testN>) then ] next(<state_name>) [ with prob(<expression>) ]
This rule means that if the agent satisfies all the tests specified,
then the probability of the agent entering the named state is the value
of <expression>
. If with prob(<expression>)
is omitted, it is equivalent
to with prob(1)
.
An example of a transition rule in a FRED program might be:
if (age > 16) then next(Dropout) with prob(0.2)
The rule says, “if an agent is more than 16 years old, then the probability of the agent’s becoming a Dropout is 20%.”
Default Next State rules
Within each state block, there may be transitions rule of the form:
default(<state_name>)
Note that this rule does not include any tests. This rule says that the
default next state is <state_name>
if none of the other next states
are selected by the other transition rules. Specifically, if the next
state probabilities for all other next states sum to a value
\(p < 1.0\), then the transition probability from the current state to
the default State is set to \((1p)\).
If more than one default transition rule is present for a given state block, the last one in the program file will apply.
For each state, the builtin default transition rule is:
state S {
default(S)
}
That is, an agent will stay in the same state if there is no other transition rule. If no explicit transition rules or default rules are included in the FRED model file, the compiler will issue a warning to remind the user that the state will transition back to itself by default.
State Transitions
Many systems are described by a statetransition matrix that defines the
probability for moving from the state that labels a row in the matrix to
any of the other states, with the individual probabilities represented
by the columns in the matrix. For example, in the matrix below, there is
a probability of 0.5 of moving from state A
to either state B
or
state C
.
A 
B 
C 


A 
0.0 
0.5 
0.5 
B 
0.1 
0.8 
0.1 
C 
0.0 
0.0 
1.0 
In FRED, only the portion of the statetransition matrix required for each agent is computed dynamically, so that the transition probabilities can vary from agent to agent and can also vary over time for an individual agent. When an agent reaches the state transition duration for its current state, the agent’s next state is computed as follows:
Compute the transition probabilities for this agent in the row of current state.
Select next state using the probability distribution for the row of the current state.
For example, given the transition matrix shown above for a given agent
in state B
, the agent would transition to state A
with a
probability of 0.1, transition to state C
with a probability of 0.1,
and remain in state B
with a probability of 0.8.
Multiple Probabilistic Rules
Suppose we have an agent in state C.i
for some condition C
that
has states n
states. For each possible next state j
, FRED
computes the probability p(i,j)
of the transition from i
to
j
as follows:
Find all qualifying rules for the given agent from state
i
to statej
. These are the rules that specify the current stateC.i
and the next statej
and for which the agent meets all the predicates in the rule.For each qualifying rule, compute the probability term for the given agent. If the probability term is omitted, the probability for this rule is 1.0.
Use the maximum probability computed for any qualifying rule as the tentative probability
p(i,j)
for the agent to transition from statei
to statej
.
Default Next State Rule and Normalization
After repeating this process for each possible next state, we have a probability vector of the form:
p(i,1), p(i,2), ..., p(i,n)
Let the total probability be the sum of the values in the vector. The
total may not equal 1.0, so the values need to be normalized to create a
valid probability distribution. But first, FRED applies the default next
state rule for state i
. Let state k
be the default next state
for state i
. The effect of the default next state is:
Note
If the total probability is < 1.0
, then add (1.0 – total)
to p(i,k)
.
Otherwise, divide all the values in the vector by the total
probability.
After applying the rule above, the values in the modified vector
<p(i,1), p(i,2), … p(i,n)>
sum to 1.0. The next state is selected by
choosing a state randomly using this vector as the probability weight
for the states.
Cautions
It is important to understand the use of transition rules. Incorrect use of transition rules can lead to unexpected results. This section highlights a few areas that require attention.
The difference between using next()
and default()
Suppose we have three states A
,B
, and C
, and we are
writing transition rules for state A
. Suppose we want to have agents
less than 10 years old transition from A
to B
with probability
0.25 and to state C
with probability 0.75; all other agents should
always transition to state C
.
The preferred code for this situation would be:
state A {
...
if (age < 10) then next(B) with prob(0.25)
default(C)
}
If an agent less than 10 years old is in state A
then the if ()
statement is the only qualifying transition rule, so the tentative
probability of going to state B
is set to 0.25. Because the total
probability is less than 1.0, the default()
next state rule applies,
and the probability of going to C
is set to 0.75 = 1.0  0.25.
If an agent 10 or older is in state A
then there are no qualifying
transition rules, so the total probability equals 0.0; In this case the
default()
transition rule applies and sets the probability of going
to state C
to 1.0 = 1.0  0.0.
The following code would lead to incorrect results:
state A {
...
if (age < 10) then next(B) with prob(0.25)
next(C) # WRONG!
}
Things work fine for agents 10 or older, but if an agent less than 10
years old is in state A
then both transition rules apply. The
if ()
statement sets the tentative probability of going to state
B
to 0.25. The next()
statement sets the tentative probability
of going to C
to 1.0. The Total is 1.25 = 0.25 + 1.0, so the
probabilities are normalized to
p(A,B) = 0.25/1.25 = 0.20
and
p(A,C) = 1.0/1.25 = 0.80
which are not the desired results.
Missing default Rule
If no default()
rule is included in a state, the default next state
is the state itself, so these two snippets are equivalent:
state A {
...
if (age < 10) then next(B)
}
state A {
...
if (age < 10) then next(B)
default(A)
}
This might lead to unexpected results if a missing default rules is applied. For example, consider this snippet:
state A {
wait(0)
if (age <= 10) then next(B) # WRONG!
}
The above code would lead to an infinite loop back to state A
for
all agents over age 10.
Example: Using Rules to Represent Health Risks
This section shows how to assign to each individual in the population a risk of having various conditions. For many health conditions, we can find tables that show the prevalence of the health condition based on demographic factors such as age, race, and sex. For example, the following table shows the prevalence of asthma in the United States based on data from the CDC:
Suppose we are creating a FRED model of asthma in which all individuals
begin the the Start
state. At the start of the simulation, we want
each individual to move to either the AtRisk
state (meaning that
they are subject to asthma attacks) or to the Negative
state
(meaning they do not suffer from asthma attacks), according to data in
the Table above.
This can be accomplished by having one transition rule per cell in the Table, as shown in the following condition:
condition ASTHMA {
transmission_mode = environmental
start_state = Start
...
state Start {
wait(0)
if (sex==male & race==white & range(age, 0, 4)) then next(AtRisk) with prob(0.037)
if (sex==male & race==white & range(age, 5, 14)) then next(AtRisk) with prob(0.095)
if (sex==male & race==white & range(age, 15, 19)) then next(AtRisk) with prob(0.094)
if (sex==male & race==white & range(age, 20, 24)) then next(AtRisk) with prob(0.065)
if (sex==male & race==white & range(age, 25, 34)) then next(AtRisk) with prob(0.065)
if (sex==male & race==white & range(age, 35, 64)) then next(AtRisk) with prob(0.059)
if (sex==male & race==white & 65<=age) then next(AtRisk) with prob(0.055)
if (sex==female & race==white & range(age, 0, 4)) then next(AtRisk) with prob(0.037)
if (sex==female & race==white & range(age, 5, 14)) then next(AtRisk) with prob(0.084)
if (sex==female & race==white & range(age, 15, 19)) then next(AtRisk) with prob(0.112)
if (sex==female & race==white & range(age, 20, 24)) then next(AtRisk) with prob(0.115)
if (sex==female & race==white & range(age, 25, 34)) then next(AtRisk) with prob(0.105)
if (sex==female & race==white & range(age, 35, 64)) then next(AtRisk) with prob(0.107)
if (sex==female & race==white & 65<=age) then next(AtRisk) with prob(0.075)
if (sex==male & race!=white & range(age, 0, 4)) then next(AtRisk) with prob(0.115)
if (sex==male & race!=white & range(age, 5, 14)) then next(AtRisk) with prob(0.201)
if (sex==male & race!=white & range(age, 15, 19)) then next(AtRisk) with prob(0.128)
if (sex==male & race!=white & range(age, 20, 24)) then next(AtRisk) with prob(0.143)
if (sex==male & race!=white & range(age, 25, 34)) then next(AtRisk) with prob(0.088)
if (sex==male & race!=white & range(age, 35, 64)) then next(AtRisk) with prob(0.063)
if (sex==male & race!=white & 65<=age) then next(AtRisk) with prob(0.078)
if (sex==female & race!=white & range(age, 0, 4)) then next(AtRisk) with prob(0.09)
if (sex==female & race!=white & range(age, 5, 14)) then next(AtRisk) with prob(0.177)
if (sex==female & race!=white & range(age, 15, 19)) then next(AtRisk) with prob(0.179)
if (sex==female & race!=white & range(age, 20, 24)) then next(AtRisk) with prob(0.132)
if (sex==female & race!=white & range(age, 25, 34)) then next(AtRisk) with prob(0.125)
if (sex==female & race!=white & range(age, 35, 64)) then next(AtRisk) with prob(0.127)
if (sex==female & race!=white & 65<=age) then next(AtRisk) with prob(0.079)
default(Negative)
}
state AtRisk {
ASTHMA.sus = 1.0
wait()
next()
}
state Negative {
ASTHMA.sus = 0.0
wait()
next()
}
}
Each rule contains a set of tests that matches the demographic factors
of each cell in the table and then assigns the same probability of being
at risk as the corresponding cell in the table. It is worth noting that
any individual in the population matches only one of the probability
rules, because the predicates are mutually exclusive. For example, a
5year old white male only matches the second rule, so his transition
probability from Start
to AtRisk
is 0.095. The effect of the
default rule is to set the transition probability from Start
to Negative
of this same individual to 1.0  0.095 = 0.905
. So, we expect that
about 9.5% of 5year old white males in the population will be in the
AtRisk state after the transition. Of course, the results will vary from
run to run, since each individual makes a probabilistic transition.
Concurrent Events
The FRED language’s approach to agentbased modeling is to provide a set of rules that apply to individual agents. Usually, the interesting results of the model arise from the combined effects of many agents interacting with each other and with their environment.
Although it is natural to think about all the agents in a simulation performing their rules in parallel, in practice, the FRED platform interprets the rules one agent at a time. As a result, there may be cases where the modeler has to understand how concurrent events, that is, events that are scheduled to occur on the same simulation step, are handled in practice.
The Order of Conditions
In FRED, conditions are updated in the order in which they are defined
in the FRED program. That is, for a given time step, agents that are
scheduled for a state transition in condition A
experience state
transition before agents that are scheduled for a state transition in
condition B
if condition A
is defined before condition B
in
the FRED program.
For example, suppose state A1
is the first state in condition A
and state B1
is the first state in condition B
, and we have the
following state definitions:
condition A {
start_state = A1
state A1 {
wait(24)
next(A2)
}
state A2 {
<action A2>
...
}
}
condition B {
start_state = B1
state B1 {
wait(24)
next(B2)
}
state B2 {
<action B2>
...
}
}
Then every agent is scheduled to enter both state A2
and B2
at
time step 24. Because condition A
is defined before condition B
,
all the agents will perform <action A2>
before any agent performs
<action B2>
. If the model assumes any other order of events, it will
likely produce unexpected results.
Note
It is considered a good modeling practice to avoid assumptions about the order in which state transition are processed across condition, if possible.
Concurrent State Transitions
FRED is a discretetime model and the time, with a step of one hour. For each hour of the simulation, FRED performs the following for each userdefined Condition:
Identify all agents that need to be updated according to the userdefined rules.
For each identified agent:
Select the agent’s next state according to the userdefined rules.
Perform any actions that are associated with the agent’s next state.
If the condition involves interactions among agents, simulate the agent interactions within the defined interaction groups. Interactions may result in some agents changing their states.
Let’s examine these steps in in more detail.
FRED maintains an event queue for each condition consisting of the list of agents that are scheduled to perform state transitions during the next simulation step. For each agent on the event queue, FRED performs the following substeps:
Evaluate the transition rules in the agent’s current state and select the agent’s new state (which may be the same as the agent’s old state).
Execute the action rules in the agent’s new state.
Evaluate the wait rules in the agent’s new state, and schedule the next event for the agent at the end of the duration of the wait step.
If multiple agents are scheduled for state transitions at the same simulation time step, the FRED language does not define the order in which agents are processed from the event queue. Different implementations may use different orderings, for example, firstinfirstout (FIFO) or perhaps random order.
For example, consider the program fragment below:
condition FOO {
start_state = A
state A {
wait(24)
next(B)
}
state B {
agent_id = id
wait(24)
next(C)
}
}
In the example above, all individual agents start in state A
where
they wait for 24 hours. At timestep 24, the agents are processed in some
order and proceed to state B
, where the value of agent_id
will
be the id of the last agent to enter state B
. In some
implementations this will be the last agent in the population, but it
may be different in other implementations, or even in the next run of
the model.
Warning
It is considered a modeling error to assume a given order of agents who perform concurrent state transitions within a given state.
In some cases, it may be desired to impose a random order on concurrent
events to avoid systematic biases toward certain agents. This can be
achieved by setting the condition property shuffle
, as follows:
condition <condition_name> {
shuffle = 1
...
}
With this setting, agents who are scheduled for a state transition at the same simulation step will be selected from the event queue in random order. For example:
condition FOO {
start_state = A
shuffle = 1
state A {
wait(24)
next(B)
}
state B {
agent_id = id
wait(24)
next(C)
}
state C {
agent_id = id
wait()
next()
}
}
In the example above, all individual agents start in state A
where
they wait for 24 hours. At timestep 24, the agents are processed in
random order and proceed to state B
, where the value of agent_id
will be the id of the last agent to enter state B
, that is, the id
of a random agent. After waiting 24 hours in state B
, the agents are
again processed in random order, so the value of agent_id
is set to
another random agent id in state C
at timestep 48.
Effects of set_state()
Concurrent event can also arise as the result of the set_state()
action, which immediately changes the state of an agent in a different
condition. The affected agent also immediately performs any actions
associated with its new state. Consider the following example:
condition COND1 {
...
state A {
set_state(COND2,B,C)
x = 1
wait()
next()
}
...
}
condition COND2 {
...
state B {
wait()
next()
}
state C {
x = 2
wait()
next()
}
...
}
If an agent enters state COND1.A
, the final value of x
is 1. The
order of event is:
Agent enters
COND1.A
Agent runs the
set_state()
action, which:Causes the agent to enter
COND2.C
Agent sets
x = 2
Agent waits in state
COND2.C
Agent continues to execute actions in state
COND1.A
and setsx = 1
That is, the set_state()
action is not queued. It runs immediately,
and the actions in the new state are performed before returning to the
calling state.
Note
It is considered a good modeling practice to avoid assumptions about the order of agents who perform concurrent state transitions.