Unconstrained Influence Diagrams
  We extend the language of influence diagrams to cope with decision scenarios
where the order of decisions and observations is not determined. As the
ordering of decisions is dependent on the evidence, a step-strategy of such a
scenario is a sequence of dependent choices of the next action. A strategy is a
step-strategy together with selection functions for decision actions. The
structure of a step-strategy can be represented as a DAG with nodes labeled
with action variables. We introduce the concept of GS-DAG: a DAG incorporating
an optimal step-strategy for any instantiation. We give a method for
constructing GS-DAGs, and we show how to use a GS-DAG for determining an
optimal strategy. Finally we discuss how analysis of relevant past can be used
to reduce the size of the GS-DAG.
