The cost of a plan

The next task is to extend the definition of the cost-to-go under a fixed plan, which was given in Section 10.1.3, to the case of imperfect state information. Consider evaluating the quality of a plan, so that the ``best'' one might be selected. Suppose that the nondeterministic uncertainty is used to model nature and that a nondeterministic initial condition is given. If a plan $\pi$ is fixed, some state and action trajectories are possible, and others are not. It is impossible to know in general what histories will occur; however, the plan constrains the choices substantially. Let ${\cal H}(\pi,{\eta_0})$ denote the set of state-action histories that could arise from $\pi$ applied to the initial condition ${\eta_0}$.

The cost of a plan $\pi$ from an initial condition ${\eta_0}$ is measured using worst-case analysis as

$${G_\pi }({\eta_0}) = \max_{({\tilde{x}},{\tilde{u}}) \in {\cal H}(\pi,{\eta_0})} \Big\{ L({\tilde{x}},{\tilde{u}}) \Big\}.$$ (11.22)

Note that ${\tilde{x}}$ includes $x_1$, which is usually not known. It may be known only to lie in $X_1$, as specified by ${\eta_0}$. Let ${\Pi}$ denote the set of all possible plans. An optimal plan using worst-case analysis is any plan for which (11.22) is minimized over all $\pi \in {\Pi}$ and ${\eta_0}\in {{\cal I}_0}$. In the case of feasible planning, there are usually numerous equivalent alternatives.

Under probabilistic uncertainty, the cost of a plan can be measured using expected-case analysis as

$$G_\pi ({\eta_0}) = E_{{\cal H}(\pi,{\eta_0})} \Big[ L({\tilde{x}},{\tilde{u}}) \Big],$$ (11.23)

in which $E$ denotes the mathematical expectation of the cost, with the probability distribution taken over ${\cal H}(\pi,{\eta_0})$. The task is to find a plan $\pi \in {\Pi}$ that minimizes (11.23).