Flat State Space Generator

Flat State Space Generator

The flat state space generator¹ is used to generate the state space of the discrete-state stochastic process inherent in a model. The state space consists of the set of all states and the transitions between them. Once the state space has been generated, an appropriate analytical solver can be chosen to solve the model, as explained in Section 4.

¹ This was the only state space generator (SSG) available prior to version 1.6.0 and it was simply called the state space generator. From that version on, it is called the flat state space generator.

While simulation can be applied to models with any underlying stochastic process, numerical solution requires that the model satisfy one of the following properties:

1. All timed actions are exponentially distributed (Markov processes).
2. All timed actions are deterministic or exponentially distributed, with at most one deterministic action enabled at any time. Furthermore, the firing delay of the deterministic actions may not be state-dependent.

The only restrictions on the use of instantaneous (zero-timed) actions are that the model must begin in a stable state, and the model must be stabilizing and well-specified . It should also be noted that the reactivation predicates (see Section 4.2.1 of Building Models) must preserve the Markov property. In other words, the timed actions in the model must be reactivated so that the firing time distributions depend only on the current state, and not on any past state. That rule pertains only to timed actions with firing delays that are state-dependent.

The flat state space generator consists of a window with two tabs, SSG Info and SSG Output, which are discussed below.

Parameters

The SSG Info tab (<xr id="fig:ssg_info" />) is presented when you open the interface, and allows you to specify options and edit input to the state space generator.

<figure id="fig:ssg_info">

<xr id="fig:ssg_info" nolink />: Flat state space generator input.</figure>

• The Study Name text box specifies the name of the child study. This box will show the name of the study you selected to be the child when you created the new solver. You can change the child study by typing a new name in the box or clicking the Browse button and selecting the solver child from the list of available studies.

• The Experiment List box displays the list of active experiments in the study, and will be updated upon any changes made through the Experiment Activator button.

• The Experiment Activator button can be used to activate or deactivate experiments defined in the child study, and provides the same functionality as the study editor Experiment Activator described in Section 7.3 of Building Models.

• The Run Name text box specifies the name for a particular run of the state space generator. This field is used to name trace files and output files (see below), and defaults to “Results” when a new solver is created. If no run name is given, the solver name will be used.

• The Build Type pull-down menu is used to choose whether the generator should be run in Optimize or Normal mode. In normal mode, the model is compiled without compiler optimizations, and you can specify various levels of output by changing the trace level, as explained below. This mode is useful for testing or debugging a model, as a text file named $<$Run Name$>$_Exp$<$x$>$_trace.txt will be created for each experiment and contain a trace of the generation. In optimize mode, the model is compiled with maximum compiler optimizations, and all trace output is disabled for maximum performance. Running the generator will write over any data from a previous run of the same name, so change the Run Name field if you wish to save output/traces from an earlier run.

• The Trace Level pull-down menu is enabled only when Normal mode is selected as the Build Type. This feature is useful for debugging purposes, as it allows you to select the amount of detail the generator will produce in the trace. The five options for Trace Level are:

Level 0: None    No detail in the trace. This would produce the same output as if optimize mode were selected.

Level 1: Action Name    For each new state discovered, prints the names of the actions enabled in this state. These are the actions that are fired when all possible next states from the current state are being explored.

Level 2: Level 1 + State    The same as Level 1, with the addition that the current state is printed along with the actions that are enabled in the state.

Level 3    has not yet been implemented in Möbius.

Level 4: All    The same as Level 2, with the addition that the next states reachable from each state currently being explored are also printed.

While a higher trace level will produce more detail in the generator trace and aid in debugging a model, it comes at the cost of slower execution time and larger file size.

• The Hash Value text box is used by the hash table data structure, which stores the set of discovered states in the generation algorithm. This number specifies the point at which the hash table is resized. Specifically, it is the ratio of the number of states discovered to the size of the hash table when a resizing² occurs. The default value of $0.5$, which means that the hash table is resized when it becomes half full, should suffice for most purposes.

• The Flag Absorbing States checkbox, when selected, will print an alert when an absorbing state is encountered. An absorbing state is one for which there are no next (successor) states.

• The Place Comments in Output checkbox, when selected, will put the user-entered comments in the generator output/trace. If the box is not checked, no comments will appear, regardless of whether any have been entered.

• The Edit Comments button allows you to enter your own comments for a run of the generator. Clicking this button brings up the window shown in <xr id="fig:ssg_commentbox" />. Type any helpful comments in the box and hit OK to save or Cancel to discard the comments. The Clear button will clear all the text from the comment box.

<figure id="fig:ssg_commentbox">

<xr id="fig:ssg_commentbox" nolink />: Edit Comments window.</figure>

• The Place Comments in Output checkbox, when selected, will put the user-entered comments in the generator output/trace. If the box is not checked, no comments will appear, regardless of whether any have been entered.

• The Experiment List box displays the list of active experiments in the study, and will be updated upon any changes made through the Experiment Activator button.

² A resizing rehashes and roughly doubles the size of the hash table.

Generation

Clicking the Start State Space Generation button switches the view to the SSG Output tab and begins the process of generating the state space. The output window appears in <xr id="fig:ssg_output" />.

<figure id="fig:ssg_output">

<xr id="fig:ssg_output" nolink />: Flat state space generator output.</figure>

First the models³ are compiled and the generator is built. For each active experiment, the values of the global variables are printed; if normal mode is being used, information about the trace level and hash table is also displayed. Then the state space is generated for the experiment. While it is being generated, the States Generated box and progress bar at the bottom of the dialog indicate the number of states that have been discovered. This number is updated once for every 1,000 states generated and when generation is complete. At any time, you may use the Stop button to terminate the run. A text file named
$<$Run Name$>$_output.txt will be created. It will mirror the data output in the GUI.

³ Here models refers to the atomic/composed models, performance variable, and study.

A final remark is in order about the notion of state during generation of the state space of the stochastic process. In Möbius, a state is defined as the values of the state variables along with the impulse reward (see Section 6.1.1 of Building Models) associated with the action whose firing led to that state. Therefore, for a model on which impulse rewards have been defined, if two different actions may fire in a given state and lead to the same next state, they give rise to two unique states in the state space. The reason is that when impulse rewards are defined, the state space generator must store information about the last action fired. The result is a larger state space for models on which impulse rewards have been defined. It is important to realize this when analyzing the size of the generated state space.

Command line options

The flat state space generator is usually run from the GUI. However, since the models are compiled and linked with the generator libraries to form an executable, the generator can also be run from the command line (e.g., from a system shell/terminal window). The executable is found in the directory

$<$Möbius Project Root$>$/$<$Project Name$>$/Solver/$<$Solver Name$>$/

and is named $<$Solver Name$>$Gen_$<$Arch$>$[_debug], where Arch is the system architecture (Windows, Linux, or Solaris) and _debug is appended if you build the flat state space generator in normal mode. The command line options and their arguments are as follows:

-P   experimentfilepath

Place the created experiment files in the directory specified by experimentfilepath. This argument can be a relative path. By default, the experiment files will be placed in the current directory.

-N   experimentname

Use experimentname to name the experiment files created. These files will have extensions .arm or .var, and will be placed in the directory specified by the “-P” option.

-B   experimentnumber

Generate the state space for the experiment numbered experimentnumber, with the first experiment having number 0. For example, use “-B1” to run the second experiment (e.g., Experiment_2). Defaults to 0.

-h   hash_value

Use hash_value as the hash value described above. Defaults to 0.5.

-a   

Flag absorbing states.

-F   filetype[1-6]

Use filetype as the format for the experiment file. The only filetype currently supported in the flat state space generator is “-F1,” or row ASCII format, which is also the default option. Other file formats may be available in future versions.

-e, -s   db_entity, db_macserver

These are internal options for interaction with the database. You can safely ignore them.

-l   trace_level[0-4]

Use trace_level as the trace level described above. Only applies when you are running the debug executable.

-t   tracefilename

Create a trace file named tracefilename as output. If this option is not specified, output is directed to the standard output stream.

Example:    ssgGen_Windows_debug -P. -B0 -l4 -ttrace.txt

• $<$Solver Name$>$ is ssg

• $<$Arch$>$ is Windows

This command will generate the state space for the first experiment (Experiment_1) with trace level 4, place the experiment files in the current directory, and create a trace file named trace.txt.

Understanding the Generated State Space Output

This section is not important to the reader if they intend to only use the built-in tools that Möbius provides. This section provides an explanation of the generated Q matrix that results from running the flat state space generator. Again, read this only if you are interested in the inner workings of the state space generator.

The Q matrix can be found in the .arm file. Here is the format:

Line 1: Initial state (first state is 1) Line 2: Total number of states. Line 3: Blank

From here on out, you get a state number (i), a state that can be transitioned from from state i (j), and a rate. If another state can be transitioned to from state i, then that other state j and its rate will appear until all nonzero i, j pairs are listed. When you run into a "0", this acts as a delimiter.

A short example should make this clear. Here is a .arm file from a 5 state birth-death process (I've added comments after "#"). Births happen at a constant rate of 2.0 and deaths happen at a constant rate of 5.0:

1                                   # Initial state
5                                   # Total number of states
                                    # Ignore
1                                   # Source state ( i )
2                                   # Target state ( j )
2.0000000000e+00                    # Rate for 1 -> 2
0                                   # Delimiter
2                                   # Source state ( i )
1                                   # Target state ( j )
5.0000000000e+00                    # Rate for 2 -> 1
3                                   # Target state ( j )
2.0000000000e+00                    # Rate for 2 -> 3
0                                   # Delimiter
3                                   # Source state ( i )
2                                   # Target state ( j )
5.0000000000e+00                    # Rate for 3 -> 2 
4                                   # Target state ( j )
2.0000000000e+00                    # Rate for 3 -> 4
0
4
3
5.0000000000e+00
5
2.0000000000e+00
0
5
4
5.0000000000e+00
0

References

Flat State Space Generator

The flat state space generator¹ is used to generate the state space of the discrete-state stochastic process inherent in a model. The state space consists of the set of all states and the transitions between them. Once the state space has been generated, an appropriate analytical solver can be chosen to solve the model, as explained in Section 4.

¹ This was the only state space generator (SSG) available prior to version 1.6.0 and it was simply called the state space generator. From that version on, it is called the flat state space generator.

While simulation can be applied to models with any underlying stochastic process, numerical solution requires that the model satisfy one of the following properties:

1. All timed actions are exponentially distributed (Markov processes).
2. All timed actions are deterministic or exponentially distributed, with at most one deterministic action enabled at any time. Furthermore, the firing delay of the deterministic actions may not be state-dependent.

The only restrictions on the use of instantaneous (zero-timed) actions are that the model must begin in a stable state, and the model must be stabilizing and well-specified . It should also be noted that the reactivation predicates (see Section 4.2.1 of Building Models) must preserve the Markov property. In other words, the timed actions in the model must be reactivated so that the firing time distributions depend only on the current state, and not on any past state. That rule pertains only to timed actions with firing delays that are state-dependent.

The flat state space generator consists of a window with two tabs, SSG Info and SSG Output, which are discussed below.

Parameters

The SSG Info tab (<xr id="fig:ssg_info" />) is presented when you open the interface, and allows you to specify options and edit input to the state space generator.

<figure id="fig:ssg_info">

<xr id="fig:ssg_info" nolink />: Flat state space generator input.</figure>

• The Study Name text box specifies the name of the child study. This box will show the name of the study you selected to be the child when you created the new solver. You can change the child study by typing a new name in the box or clicking the Browse button and selecting the solver child from the list of available studies.

• The Experiment List box displays the list of active experiments in the study, and will be updated upon any changes made through the Experiment Activator button.

• The Experiment Activator button can be used to activate or deactivate experiments defined in the child study, and provides the same functionality as the study editor Experiment Activator described in Section 7.3 of Building Models.

• The Run Name text box specifies the name for a particular run of the state space generator. This field is used to name trace files and output files (see below), and defaults to “Results” when a new solver is created. If no run name is given, the solver name will be used.

• The Build Type pull-down menu is used to choose whether the generator should be run in Optimize or Normal mode. In normal mode, the model is compiled without compiler optimizations, and you can specify various levels of output by changing the trace level, as explained below. This mode is useful for testing or debugging a model, as a text file named $<$Run Name$>$_Exp$<$x$>$_trace.txt will be created for each experiment and contain a trace of the generation. In optimize mode, the model is compiled with maximum compiler optimizations, and all trace output is disabled for maximum performance. Running the generator will write over any data from a previous run of the same name, so change the Run Name field if you wish to save output/traces from an earlier run.

• The Trace Level pull-down menu is enabled only when Normal mode is selected as the Build Type. This feature is useful for debugging purposes, as it allows you to select the amount of detail the generator will produce in the trace. The five options for Trace Level are:

Level 0: None    No detail in the trace. This would produce the same output as if optimize mode were selected.

Level 1: Action Name    For each new state discovered, prints the names of the actions enabled in this state. These are the actions that are fired when all possible next states from the current state are being explored.

Level 2: Level 1 + State    The same as Level 1, with the addition that the current state is printed along with the actions that are enabled in the state.

Level 3    has not yet been implemented in Möbius.

Level 4: All    The same as Level 2, with the addition that the next states reachable from each state currently being explored are also printed.

While a higher trace level will produce more detail in the generator trace and aid in debugging a model, it comes at the cost of slower execution time and larger file size.

• The Hash Value text box is used by the hash table data structure, which stores the set of discovered states in the generation algorithm. This number specifies the point at which the hash table is resized. Specifically, it is the ratio of the number of states discovered to the size of the hash table when a resizing² occurs. The default value of $0.5$, which means that the hash table is resized when it becomes half full, should suffice for most purposes.

• The Flag Absorbing States checkbox, when selected, will print an alert when an absorbing state is encountered. An absorbing state is one for which there are no next (successor) states.

• The Place Comments in Output checkbox, when selected, will put the user-entered comments in the generator output/trace. If the box is not checked, no comments will appear, regardless of whether any have been entered.

• The Edit Comments button allows you to enter your own comments for a run of the generator. Clicking this button brings up the window shown in <xr id="fig:ssg_commentbox" />. Type any helpful comments in the box and hit OK to save or Cancel to discard the comments. The Clear button will clear all the text from the comment box.

<figure id="fig:ssg_commentbox">

<xr id="fig:ssg_commentbox" nolink />: Edit Comments window.</figure>

• The Place Comments in Output checkbox, when selected, will put the user-entered comments in the generator output/trace. If the box is not checked, no comments will appear, regardless of whether any have been entered.

• The Experiment List box displays the list of active experiments in the study, and will be updated upon any changes made through the Experiment Activator button.

² A resizing rehashes and roughly doubles the size of the hash table.

Generation

Clicking the Start State Space Generation button switches the view to the SSG Output tab and begins the process of generating the state space. The output window appears in <xr id="fig:ssg_output" />.

<figure id="fig:ssg_output">

<xr id="fig:ssg_output" nolink />: Flat state space generator output.</figure>

First the models³ are compiled and the generator is built. For each active experiment, the values of the global variables are printed; if normal mode is being used, information about the trace level and hash table is also displayed. Then the state space is generated for the experiment. While it is being generated, the States Generated box and progress bar at the bottom of the dialog indicate the number of states that have been discovered. This number is updated once for every 1,000 states generated and when generation is complete. At any time, you may use the Stop button to terminate the run. A text file named
$<$Run Name$>$_output.txt will be created. It will mirror the data output in the GUI.

³ Here models refers to the atomic/composed models, performance variable, and study.

A final remark is in order about the notion of state during generation of the state space of the stochastic process. In Möbius, a state is defined as the values of the state variables along with the impulse reward (see Section 6.1.1 of Building Models) associated with the action whose firing led to that state. Therefore, for a model on which impulse rewards have been defined, if two different actions may fire in a given state and lead to the same next state, they give rise to two unique states in the state space. The reason is that when impulse rewards are defined, the state space generator must store information about the last action fired. The result is a larger state space for models on which impulse rewards have been defined. It is important to realize this when analyzing the size of the generated state space.

Command line options

The flat state space generator is usually run from the GUI. However, since the models are compiled and linked with the generator libraries to form an executable, the generator can also be run from the command line (e.g., from a system shell/terminal window). The executable is found in the directory

$<$Möbius Project Root$>$/$<$Project Name$>$/Solver/$<$Solver Name$>$/

and is named $<$Solver Name$>$Gen_$<$Arch$>$[_debug], where Arch is the system architecture (Windows, Linux, or Solaris) and _debug is appended if you build the flat state space generator in normal mode. The command line options and their arguments are as follows:

-P   experimentfilepath

Place the created experiment files in the directory specified by experimentfilepath. This argument can be a relative path. By default, the experiment files will be placed in the current directory.

-N   experimentname

Use experimentname to name the experiment files created. These files will have extensions .arm or .var, and will be placed in the directory specified by the “-P” option.

-B   experimentnumber

Generate the state space for the experiment numbered experimentnumber, with the first experiment having number 0. For example, use “-B1” to run the second experiment (e.g., Experiment_2). Defaults to 0.

-h   hash_value

Use hash_value as the hash value described above. Defaults to 0.5.

-a   

Flag absorbing states.

-F   filetype[1-6]

Use filetype as the format for the experiment file. The only filetype currently supported in the flat state space generator is “-F1,” or row ASCII format, which is also the default option. Other file formats may be available in future versions.

-e, -s   db_entity, db_macserver

These are internal options for interaction with the database. You can safely ignore them.

-l   trace_level[0-4]

Use trace_level as the trace level described above. Only applies when you are running the debug executable.

-t   tracefilename

Create a trace file named tracefilename as output. If this option is not specified, output is directed to the standard output stream.

Example:    ssgGen_Windows_debug -P. -B0 -l4 -ttrace.txt

• $<$Solver Name$>$ is ssg

• $<$Arch$>$ is Windows

This command will generate the state space for the first experiment (Experiment_1) with trace level 4, place the experiment files in the current directory, and create a trace file named trace.txt.

Understanding the Generated State Space Output

This section is not important to the reader if they intend to only use the built-in tools that Möbius provides. This section provides an explanation of the generated Q matrix that results from running the flat state space generator. Again, read this only if you are interested in the inner workings of the state space generator.

The Q matrix can be found in the .arm file. Here is the format:

Line 1: Initial state (first state is 1) Line 2: Total number of states. Line 3: Blank

From here on out, you get a state number (i), a state that can be transitioned from from state i (j), and a rate. If another state can be transitioned to from state i, then that other state j and its rate will appear until all nonzero i, j pairs are listed. When you run into a "0", this acts as a delimiter.

A short example should make this clear. Here is a .arm file from a 5 state birth-death process (I've added comments after "#"). Births happen at a constant rate of 2.0 and deaths happen at a constant rate of 5.0:

1                                   # Initial state
5                                   # Total number of states
                                    # Ignore
1                                   # Source state ( i )
2                                   # Target state ( j )
2.0000000000e+00                    # Rate for 1 -> 2
0                                   # Delimiter
2                                   # Source state ( i )
1                                   # Target state ( j )
5.0000000000e+00                    # Rate for 2 -> 1
3                                   # Target state ( j )
2.0000000000e+00                    # Rate for 2 -> 3
0                                   # Delimiter
3                                   # Source state ( i )
2                                   # Target state ( j )
5.0000000000e+00                    # Rate for 3 -> 2 
4                                   # Target state ( j )
2.0000000000e+00                    # Rate for 3 -> 4
0
4
3
5.0000000000e+00
5
2.0000000000e+00
0
5
4
5.0000000000e+00
0

References