Nature acts twice

A convenient, alternative formulation can be given by allowing nature to act twice:

  1. First, a nature action, $ \theta \in \Theta$, is chosen but is unknown to the robot.
  2. Following this, a nature observation action is chosen to interfere with the robot's ability to sense $ \theta $.
Let $ \psi$ denote a nature observation action, which is chosen from a nature observation action space, $ \Psi(\theta)$. A sensor mapping, $ h$, can now be defined that yields $ y =
h(\theta,\psi)$ for each $ \theta \in \Theta$ and $ \psi \in
\Psi(\theta)$. Thus, for each of the two kinds of nature actions, $ \theta \in \Theta$ and $ \psi \in \Psi$, an observation, $ y =
h(\theta,\psi)$, is given. This yields an alternative way to express Formulation 9.5:

Formulation 9..6 (Nature Interferes with the Observation)  
  1. A nonempty, finite set $ U$ called the action space.
  2. A nonempty, finite set $ \Theta$ called the nature action space.
  3. A nonempty, finite set $ Y$ called the observation space.
  4. For each $ \theta \in \Theta$, a nonempty set $ \Psi(\theta)$ called the nature observation action space.
  5. A sensor mapping $ h:\Theta \times \Psi \rightarrow Y$.
  6. A function $ L: U \times \Theta \rightarrow {\mathbb{R}}\cup \{\infty\}$ called the cost function.

This nicely unifies the nondeterministic and probabilistic models with a single function $ h$. To express a nondeterministic model, it is assumed that any $ \psi \in
\Psi(\theta)$ is possible. Using $ h$,

$\displaystyle \Theta(y) = \{ \theta \in \Theta \;\vert\; \exists \psi \in \Psi(\theta)$    such that $\displaystyle y = h(\theta,\psi) \} .$ (9.27)

For a probabilistic model, a distribution $ P(\psi\vert\theta)$ is specified (often, this may reduce to $ P(\psi)$). Suppose that when the domain of $ h$ is restricted to some $ \theta \in \Theta$, then it forms an injective mapping from $ \Psi$ to $ Y$. In other words, every nature observation action leads to a unique observation, assuming $ \theta $ is fixed. Using $ P(\psi)$ and $ h$, $ P(y\vert\theta)$ is derived as

$\displaystyle P(y\vert\theta) = \left\{ \begin{array}{ll} P(\psi\vert\theta) & ...
...heta,\psi)$. }  0 & \mbox{ if no such $\psi$ exists. }  \end{array}\right.$ (9.28)

If the injective assumption is lifted, then $ P(\psi\vert\theta)$ is replaced by a sum over all $ \psi$ for which $ y =
h(\theta,\psi)$. In Formulation 9.6, the only difference between the nondeterministic and probabilistic models is the characterization of $ \psi$, which represents a kind of measurement interference. A strategy still takes the form $ \pi: \Theta \rightarrow U$. A hybrid model is even possible in which one nature action is modeled nondeterministically and the other probabilistically.

Steven M LaValle 2012-04-20