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 \((1-p)\).

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 built-in 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 state-transition 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 state-transition 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:

1. Compute the transition probabilities for this agent in the row of current state.

2. 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:

1. Find all qualifying rules for the given agent from state i to state j. These are the rules that specify the current state C.i and the next state j and for which the agent meets all the predicates in the rule.

2. 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.

3. Use the maximum probability computed for any qualifying rule as the tentative probability p(i,j) for the agent to transition from state i to state j.

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 5-year 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 5-year 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 agent-based 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 discrete-time model and the time, with a step of one hour. For each hour of the simulation, FRED performs the following for each user-defined Condition:

• Identify all agents that need to be updated according to the user-defined rules.

• For each identified agent:

  • Select the agent’s next state according to the user-defined 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 sub-steps:

1. 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).

2. Execute the action rules in the agent’s new state.

3. 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, first-in-first-out (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 sets x = 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.