Strategies
Properties to be model checked on MDPs (and their variants, such as POMDPs or IMDPs) usually quantify over strategies (or policies) of the model, i.e., over the different possible ways that nondeterminism can be resolved in the model. For example, this property:
Pmax=? [ F "goal" ]
determines the maximum probability, over all strategies, of reaching a state satisfying the label "goal".
When checking such properties, you can also ask PRISM to generate a corresponding (optimal) strategy,
which yields this maximum probability when followed. The strategy can then be viewed, exported or simulated.
Note: PRISM uses the term strategy for all model types (other common names are policy, scheduler and adversary). Strategy generation is implemented in the "explicit" model checking engine, which is used automatically if strategy generation is requested. The "sparse" engine has a more limited adversary generation feature (see below).
Generating strategies
Optimal strategies can be generated either from the command-line or the graphical user interface (GUI). For the former, use the -exportstrat switch. Simple examples are:
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat stdout
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat strat.pexp
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat strat.umb
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat strat.dot
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat strat.tra
The first of these exports actions, the others export induced models (see below).
From the GUI, you can trigger strategy generation by ticking the "Generate strategy" box either on the popup menu that appears when you right-click a property, or from the "Strategies" menu at the top. As long as it is supported, a strategy will then be generated once "Verify" is clicked.
From the same menu(s), you can then
- export the strategy to a file
- view the strategy by printing it in the log
- explore the strategy in the simulator
Export formats
Strategies can be viewed or exported in several different formats:
Action list
An action list gives the action taken in each state of the model, e.g.:
(0,0):east
(0,1):north
(0,2):north
(1,0):south
...
where states, by default, are shown as a tuple of variable values.
Induced model
An induced model is a representation of the model that is induced when the strategy is applied. There are two "modes" for this export. The first (and default) is reduce, which removes the nondeterminism resolved by the strategy (e.g., an MDP becomes a DTMC). This can be useful to re-import the model back into PRISM and analyse the induced model. The second is restrict, which shows the original model but with a restricted set of choices (e.g., an MDP with just one choice in each state).
In each case, the induced model can be exported in various formats,
as for regular model export,
including UMB or explicit format,
the latter either a combined (.pexp) file or just the transitions (.tra).
Dot file
A Dot file is, like an induced model, a view of the model induced by the strategy, but in Dot format, which allows it to be visualised.
Configuring strategy export
As hinted in the command-line examples above, the -exportstrat switch uses the file extension to determine the preferred format: if the strategy is exported to a file with extension .umb/.pexp/.tra or .dot, then it uses an induced model or Dot file, respectively. Otherwise, the default is an action list. You can specify the desired format:
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat file.txt:type=actions
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat file.txt:type=induced
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat file.txt:type=dot
Further options can be added, e.g., to specify whether an induced model is exported in "restrict" or "reduce" mode:
prism mdp.prism -pf 'Pmax=? [ F "goal" ]' -exportstrat file.txt:type=induced,mode=restrict
A list of available options is as follows:
type(actions,inducedordot): the type of strategy export to use (action list, induced model or Dot file)mode(restrictorreduce): when exporting as an induced model or Dot file, whether to "restrict" or "reduce" the model (see above); the default is "reduce"reach(trueorfalse): whether to restrict the strategy to states that are reachable when it is applied to the model (this is only used for exporting induced models and Dot files, and the default value is true, except for exporting just transitions in.traformat)states(trueorfalse): whether to show states, rather than state indices, for actions lists or Dot files; this is true by defaultmergeobs(trueorfalse): for partially observable models, whether to merge observationally equivalent states; this is true by default (and was previously calledobs).
Mirroring the -exportmodel switch (see here),
several other options are available for induced model export:
format(explicit,dotorumb): the format to export instates(trueorfalse): whether to include statesrewards(trueorfalse): whether to include rewardslabels(trueorfalse): whether to include labelsactions(trueorfalse): whether to include actions on choices/transitionsobs(trueorfalse): whether to include observationsprecision(<n>): use<n>significant figures for floating point values (in text)zip(true,false,gziporxz): whether to zip the output and in what formatheaders(trueorfalse): whether to include headers when exporting rewardstext(trueorfalse): whether to use textual form for UMB
Strategy types
PRISM generates several types of strategies. The simplest are memoryless deterministic strategies, which pick a single action in each state, as in the examples above. For some query types (e.g., step-bounded properties, or LTL-based properties), finite-memory strategies are generated, where an additional memory value is used. For these, induced models or Dot files are most useful since they will also show how the memory values are updated as the strategy is executed. Note that, in these cases, the state indices of the strategy will correspond to the product model constructed during model checking, not the original model. The product model can be exported using the -exportprodtrans and -exportprodstates switches.
Adversary generation
The "sparse" engine still includes PRISM's older "adversary generation" functionality,
which exports the induced model of an optimal strategy for MDPs, as a DTMC or an MDP
(switches -exportadv and -exportadvmdp,
or the "Adversary export" option in the GUI).
This is superseded by -exportstrat, described above, whose reduce and restrict modes give the same two models.