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 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 denote the set of state-action histories that could arise from applied to the initial condition .
The cost of a plan from an initial condition is measured using worst-case analysis as
Under probabilistic uncertainty, the cost of a plan can be measured using expected-case analysis as
Steven M LaValle 2012-04-20