Next: , Previous: , Up: Example Programs   [Contents][Index]


7.3 optpath

This program performs the search of a path in the state transition network represented in Figure 5.2. The final state of the path is 9. The example program tries to find a path that satisfies two optimization goals: the path should be short, and the path should have maximum geometric mean probability of state transition. To find an optimal path, the example program traverses the state transition network from the initial state to the final state a number of times defined by the macro NVISIT (that has value 400).

The example program creates a single-node model that uses two spur types and has a restriction that the action emission matrix must define deterministic choice of an instruction class emitted in every node state. The restriction eliminates the need to specify stt instructions in an assembler program that represents the state transition network. To code the state transition network in the assembler program, an approach is used analogous to one described in Specifying State Transition Networks.

The example program turns off the use of the automatic spur by the environment state identification engine. Instead of the automatic spur (of type 0), the environment state identification engine uses the spur equal to the sum of logarithms of probabilities of state transitions performed. Spur of type 1 countervails spur of type 0 and is incremented by 1 each time the final state is reached. Continuous time tracked by the model is incremented by 1 after every state transition.

At the end of its run, the example program prints the sum of logarithms of probabilities of state transitions performed, the total number of state transitions performed, and the geometric mean probability of state transition. Arguments of incspr instructions in the assembler program specify probabilities of state transitions less than 1. To register instruction classes ‘incspr prob’, the memory representation of the assembler program is scanned, names and parameters of instructions are fetched by the function qsmm_instr_str.

A random seed can be specified by a program argument. If the random seed is non-negative, then the program will operate normally. If the random seed is negative, then state transitions will be selected completely randomly. You could compare the program output for these two modes of program execution.

Here is given sample program output.

$ ./optpath -1
logprob = -1551.45
path_len = 2755
step_prob = 0.569417
$ ./optpath 1
logprob = -829.073
path_len = 1903
step_prob = 0.646834

Results of invocation of the example program in the normal mode of operation using random seeds in the range 1 to 20, and in the completely random mode of operation using seeds in the range -20 to -1 are represented in the table below.

  SEED  logprob path_len step_prob    SEED  logprob path_len step_prob
------ -------- -------- ---------  ------ -------- -------- ---------
    -1 -1551.45     2755  0.569417       1 -829.073     1903  0.646834
    -2 -1580.21     2692  0.555991       2 -894.364     1867  0.619379
    -3 -1590.75     2800  0.566587       3 -871.942     1861  0.625919
    -4 -1628.23     2857  0.565577       4 -827.89      1876  0.643196
    -5 -1661.79     2923  0.566361       5 -828.801     1882  0.64379
    -6 -1582.71     2770  0.564748       6 -839.799     1873  0.638668
    -7 -1552.68     2731  0.566352       7 -824.554     1855  0.641143
    -8 -1619.09     2860  0.567726       8 -823.913     1867  0.643198
    -9 -1606.98     2836  0.567431       9 -835.016     1885  0.642121
   -10 -1540.68     2719  0.567431      10 -848.998     1888  0.637832
   -11 -1605.54     2833  0.567379      11 -869.818     1873  0.628513
   -12 -1596.22     2788  0.564095      12 -792.632     1912  0.660633
   -13 -1524.97     2734  0.572479      13 -820.228     1852  0.642179
   -14 -1577.36     2752  0.563737      14 -845.155     1858  0.634528
   -15 -1623.44     2770  0.556506      15 -751.143     1831  0.663493
   -16 -1579.98     2758  0.563904      16 -805.133     1819  0.642349
   -17 -1570.52     2839  0.575109      17 -784.603     1873  0.657769
   -18 -1577.83     2779  0.566789      18 -807.793     1822  0.641879
   -19 -1555.77     2719  0.564291      19 -815.895     1870  0.646419
   -20 -1497.82     2749  0.579922      20 -877.093     1918  0.632993
------ -------- -------- ---------  ------ -------- -------- ---------
   AVG -1581.2    2783.2 [0.566588]    AVG -829.7     1869.3 [0.641554]
STDDEV    38.2      58.6  0.00534   STDDEV   33.7       26.3  0.010816

The intersections of the ‘AVG’ row and ‘logprob’ and ‘path_len’ columns contain arithmetic means of column values located above. The intersections of the ‘AVG’ row and ‘step_prob’ columns contain geometric mean probabilities of state transitions for 20 invocations of the example program. The ‘STDDEV’ row contains the standard deviation of column values located above.

As it can be seen from the table above, the geometric mean probability of state transition for 20 invocations of the example program for the normal mode of operation is by 0.074966 greater than that probability for the completely random mode of operation.


Next: , Previous: , Up: Example Programs   [Contents][Index]