Formulating the problem

Let $Y$ denote the observation space, which is the set of all possible observations, $y \in Y$. For convenience, suppose that $Y$, $U$, and $\Theta$ are all discrete. It will be assumed as part of the model that some constraints on $\theta$ are known once $y$ is given. Under the nondeterministic model a set $Y(\theta) \subseteq Y$ is specified for every $\theta \in \Theta$. The set $Y(\theta)$ indicates the possible observations, given that the nature action is $\theta$. Under the probabilistic model a conditional probability distribution, $P(y\vert\theta)$, is specified. Examples of sensing models will be given in Section 9.2.4. Many others appear in Sections 11.1.1 and 11.5.1, although they are expressed with respect to a state space $X$ that reduces to $\Theta$ in this section. As before, the probabilistic case also requires a prior distribution, $P(\Theta)$, to be given. This results in the following formulation.

Formulation 9..5 (A Game Against Nature with an Observation)  

1. A finite, nonempty set $U$ called the action space. Each $u \in U$ is referred to as an action.
2. A finite, nonempty set $\Theta$ called the nature action space.
3. A finite, nonempty set $Y$ called the observation space.
4. A set $Y(\theta) \subseteq Y$ or probability distribution $P(y\vert\theta)$ specified for every $\theta \in \Theta$. This indicates which observations are possible or probable, respectively, if $\theta$ is the nature action. In the probabilistic case a prior, $P(\theta)$, must also be specified.
5. A function $L: U \times \Theta \rightarrow {\mathbb{R}}\cup \{\infty\}$, called the cost function.

Consider solving Formulation 9.5. A strategy is now more complicated than simply specifying an action because we want to completely characterize the behavior of the robot before the observation has been received. This is accomplished by defining a strategy as a function, $\pi: Y \rightarrow U$. For each possible observation, $y \in Y$, the strategy provides an action. We now want to search the space of possible strategies to find the one that makes the best decisions over all possible observations. In this section, $Y$ is actually a special case of an information space, which is the main topic of Chapters 11 and 12. Eventually, a strategy (or plan) will be conditioned on an information state, which generalizes an observation.