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

$\displaystyle {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

$\displaystyle 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).

Steven M LaValle 2012-04-20