The history information space

The history I-space is simply the set of all possible history I-states. Although the history I-states appear to be quite complicated, it is helpful to think of them abstractly as points in a new space. To define the set of all possible history I-states, the sets of all initial conditions, actions, and observations must be precisely defined.

The set of all observation histories is denoted as $ {\tilde{Y}}_k$ and is obtained by a Cartesian product of $ k$ copies of the observation space:

$\displaystyle {\tilde{Y}}_k = \mathop{\underbrace{Y \times Y \ldots \times Y}}_k.$ (11.16)

Similarly, the set of all action histories is $ {\tilde{U}}_{k-1}$, the Cartesian product of $ k-1$ copies of the action space $ U$.

It is slightly more complicated to define the set of all possible initial conditions because three different types of initial conditions are possible. Let $ {{\cal I}_0}$ denote the initial condition space. Depending on which of the three types of initial conditions are used, one of the following three definitions of $ {{\cal I}_0}$ is used:

  1. Known State: If the initial state, $ x_1$, is given, then $ {{\cal I}_0}\subseteq X$. Typically, $ {{\cal I}_0}= X$; however, it might be known in some instances that certain initial states are impossible. Therefore, it is generally written that $ {{\cal I}_0}\subseteq X$.
  2. Nondeterministic: If $ X_1$ is given, then $ {{\cal I}_0}\subseteq
{\rm pow}(X)$ (the power set of $ X$). Again, a typical situation is $ {{\cal I}_0}
= {\rm pow}(x)$; however, it might be known that certain subsets of $ X$ are impossible as initial conditions.
  3. Probabilistic: Finally, if $ P(x)$ is given, then $ {{\cal I}_0}
\subseteq {\cal P}(X)$, in which $ {\cal P}(x)$ is the set of all probability distributions over $ X$.

The history I-space at stage $ k$ is expressed as

$\displaystyle {{\cal I}_k}= {{\cal I}_0}\times {\tilde{U}}_{k-1} \times {\tilde{Y}}_k .$ (11.17)

Each $ {\eta}_k \in {{\cal I}_k}$ yields an initial condition, an action history, and an observation history. It will be convenient to consider I-spaces that do not depend on $ k$. This will be defined by taking a union (be careful not to mistakenly think of this construction as a Cartesian product). If there are $ K$ stages, then the history I-space is

$\displaystyle {\cal I}_{hist}= {\cal I}_0 \cup {\cal I}_1 \cup {\cal I}_2 \cup \cdots \cup {\cal I}_K .$ (11.18)

Most often, the number of stages is not fixed. In this case, $ {\cal I}_{hist}$ is defined to be the union of $ {{\cal I}_k}$ over all $ k \in \{0\}
\cup {\mathbb{N}}$:

$\displaystyle {\cal I}_{hist}= {\cal I}_0 \cup {\cal I}_1 \cup {\cal I}_2 \cup \cdots .$ (11.19)

This construction is related to the state space obtained for time-varying motion planning in Section 7.1. The history I-space is stage-dependent because information accumulates over time. In the discrete model, the reference to time is only implicit through the use of stages. Therefore, stage-dependent I-spaces are defined. Taking the union of all of these is similar to the state space that was formed in Section 7.1 by making time be one axis of the state space. For the history I-space, $ {\cal I}_{hist}$, the stage index $ k$ can be imagined as an ``axis.''

One immediate concern regarding the history I-space $ {\cal I}_{hist}$ is that its I-states may be arbitrarily long because the history grows linearly with the number of stages. For now, it is helpful to imagine $ {\cal I}_{hist}$ abstractly as another kind of state space, without paying close attention to how complicated each $ {\eta}\in {\cal I}_{hist}$ may be to represent. In many contexts, there are ways to simplify the I-space. This is the topic of Section 11.2.

Steven M LaValle 2012-04-20