Task based information reduction and the shadow sequence information space

Once the task is fixed, however, it may become possible to reduce $\mathcal I_{hist}$ dramatically. For example, for our specific task of tracking hidden targets in shadows, all we need to know is the initial distribution of targets, the component events, and the FOV events. Since targets move unpredictably, other information contained in $\eta_t$ does not help: the robots' exact location, the shape of the workspace shadows, and what the targets in the FOV are doing are not relevant. Thus, Observation 2 allows us to construct a derived I-space $\mathcal I_{ss}$ , called the shadow sequence I-space that discards the irrelevant information. Consider the information contained in $\eta_t = (\eta_0, \tilde{q}_t, \tilde{y}_t)$ . In $\mathcal I_{ss}$ , the following reductions are made to $\eta_0, \tilde{q}_t, \tilde{y}_t$ :

1. The initial distribution of targets is extracted from $\eta_0$ .
2. The shadow sequence is extracted via processing $\tilde{q}_t$ and $\tilde{y}_t$ . Sometimes $\tilde{y}_t$ is not needed, such as a point robot equipped with omni-directional, infinite range sensor moving in a known 2D or 3D environment. For such setups, component events happen when the point robot's trajectory crosses critical lower dimensional surfaces in the workspace. In the other extreme, the particular configurations do not even need to be measured, provided that there is some alternative way to determine the shadow components (for example, they can be inferred from depth discontinuities in a planar, simply connected free space [40]).
3. The observation history $\tilde{y}_t$ is compressed so that only changes and time between changes need to be recorded. Every such change corresponds to the observation of a FOV event. The process yields a sequence of distinct observations.

The result from this reduction is the shadow sequence I-state $\eta '_t$ (Fig. 7 gives an example) that lives in $\mathcal I_{ss}$ . Although we cannot say that $\mathcal I_{ss}$ is the smallest I-space that is sufficient for solving the task of tracking targets in shadows, it immediately reveals much more structure that is intrinsic to the task than $\mathcal I_{hist}$ does. From this we observe a general pattern that we exploit: Given $\mathcal I_{hist}$ and a task, we try to find one or more sufficient derived I-spaces, and work exclusively in these derived I-spaces. As we will see shortly, further reduction of information may again be possible depending on the tasks, yielding more compact I-states and I-spaces.

Figure 8: Although it is possible to obtain $\eta '_{t+1}$ from $\eta _{t+1}$ , it is also possible to derive it from $\eta '_t$ and $q_{t, t+1}, y_{t, t+1}$ .

In practice, this suggests that if the task is known before the observation history is obtained, the derived I-state can be obtained ``online''. Most of $\eta_t$ can be discarded once we have $\eta '_t$ , and $\eta '_{t+1}$ can then be obtained from $\eta '_t$ and $q_{t, t+1}, y_{t, t+1}$ , which are the information accumulated during the time interval $(t, t+1]$ . This is illustrated for $\mathcal I_{hist}$ and $\mathcal I_{ss}$ in Fig. 8. Computationally, the shadow sequence can be obtained by storing and processing only immediate history. At a given time $t$ , since our analysis establishes a 1-1 correspondence between workspace-time shadows and workspace shadows at $t$ , we only need to look at observation history between $t-t_{\epsilon}$ ( $t_{\epsilon} > 0$ is a small real number) and $t$ to detect component events. That is, workspace-time shadows, which determines the shadow sequence, can be recovered from workspace shadows. Similar techniques apply to the detection of FOV events.