Conservative approximations

Figure 11.9: The nondeterministic I-states may be complicated regions that are difficult or impossible to compute.

Figure 11.10: The nondeterministic I-states can be approximated by bounding spheres.

Suppose that nondeterministic uncertainty is used and an approximation is made to the nondeterministic I-states. An I-map, ${{\kappa}_{app}}: {\cal I}_{ndet}\rightarrow {\cal I}_{app}$, will be defined in which ${\cal I}_{app}$ is a particular family of subsets of $X$. For example, ${\cal I}_{app}$ could represent the set of all ball subsets of $X$. If $X = {\mathbb{R}}^2$, then the balls become discs, and only three parameters $(x,y,r)$ are needed to parameterize ${\cal I}_{app}$ ($x,y$ for the center and $r$ for the radius). This implies that ${\cal I}_{app}\subset {\mathbb{R}}^3$; this appears to be much simpler than ${\cal I}_{ndet}$, which could be a complicated collection of regions in ${\mathbb{R}}^2$. To make ${\cal I}_{app}$ even smaller, it could be required that $x$, $y$, and $r$ are integers (or are sampled with some specified dispersion, as defined in Section 5.2.3). If ${\cal I}_{app}$ is bounded, then the number of derived I-states would become finite. Of course, this comes an at expense because ${\cal I}_{ndet}$ may be poorly approximated.

For a fixed sequence of actions ($u_1$, $u_2$, $\ldots$) consider the sequence of nondeterministic I-states:

$$X_1({\eta}_1) \stackrel{u_1,y_2}{\longrightarrow} X_2({\eta}_2) \... ..._3}{\longrightarrow} X_3({\eta}_3) \stackrel{u_3,y_4}{\longrightarrow} \cdots ,$$ (11.59)

which is also depicted in Figure 11.9. The I-map ${\cal I}_{app}$ must select a bounding region for every nondeterministic I-state. Starting with a history I-state, ${\eta}$, the nondeterministic I-state $X_k({\eta}_k)$ can first be computed, followed by applying ${\cal I}_{app}$ to yield a bounding region. If there is a way to efficiently compute $X_k({\eta}_k)$ for any ${\eta}_k$, then a plan on ${\cal I}_{app}$ could be much simpler than those on ${\cal I}_{ndet}$ or ${\cal I}_{hist}$.

If it is difficult to compute $X_k({\eta}_k)$, one possibility is to try to define a derived information transition equation, as discussed in Section 11.2.1. The trouble, however, is that ${\cal I}_{app}$ is usually not a sufficient I-map. Imagine wanting to compute ${{\kappa}_{app}}(X_{k+1}({\eta}_{k+1}))$, which is a bounding approximation to $X_{k+1}({\eta}_{k+1})$. This can be accomplished by starting with $X_k({\eta}_k)$, applying the update rules (11.30) and (11.31), and then applying ${{\kappa}_{app}}$ to $X_{k+1}({\eta}_{k+1})$. In general, this does not produce the same result as starting with the bounding volume ${\cal I}_{app}(X_k({\eta}_k))$, applying (11.30) and (11.31), and then applying ${{\kappa}_{app}}$.

Thus, it is not possible to express the transitions entirely in ${\cal I}_{app}$ without some further loss of information. However, if this loss of information is tolerable, then an information-destroying approximation may nevertheless be useful. The general idea is to make a bounding region for the nondeterministic I-state in each iteration. Let ${\hat{X}}_k$ denote this bounding region at stage $k$. Be careful in using such approximations. As depicted in Figures 11.9 and 11.10, the sequences of derived I-states diverge. The sequence in Figure 11.10 is not obtained by simply bounding each calculated I-state by an element of ${\cal I}_{app}$; the entire sequence is different.

Initially, ${\hat{X}}_1$ is chosen so that $X_1({\eta}_1) \subseteq {\hat{X}}_1$. In each inductive step, ${\hat{X}}_k$ is treated as if it were the true nondeterministic I-state (not an approximation). Using (11.30) and (11.31), the update for considering $u_k$ and $y_{k+1}$ is

$${\hat{X}}'_{k+1} = \Bigg( \bigcup_{x_k \in {\hat{X}}_k} F(x_k,u_k) \Bigg) \cap H(y_{k+1}).$$ (11.60)

In general, ${\hat{X}}'_{k+1}({\eta}_{k+1})$ might not lie in ${\cal I}_{app}$. Therefore, a bounding region, ${\hat{X}}_{k+1} \in {\cal I}_{app}$, must be selected to approximate ${\hat{X}}'$ under the constraint that ${\hat{X}}'_{k+1} \subseteq {\hat{X}}_{k+1}$. This completes the inductive step, which together with the base case yields a sequence

$${\hat{X}}_1 \stackrel{u_1,y_2}{\longrightarrow} {\hat{X}}_2 \stac... ...,y_3}{\longrightarrow} {\hat{X}}_3 \stackrel{u_3,y_4}{\longrightarrow} \cdots ,$$ (11.61)

which is depicted in Figure 11.10.

Both a plan, $\pi : {\cal I}_{app}\rightarrow U$, and information transitions can now be defined over ${\cal I}_{app}$. To ensure that a plan is sound, the approximation must be conservative. If in some iteration, ${\hat{X}}_{k+1}({\eta}_{k+1}) \subset {\hat{X}}^\prime_{k+1}({\eta}_{k+1})$, then the true state may not necessarily be included in the approximate derived I-state. This could, for example, mean that a robot is in a collision state, even though the derived I-state indicates that this is impossible. This bad behavior is generally avoided by keeping conservative approximations. At one extreme, the approximations can be made very conservative by always assigning ${\hat{X}}_{k+1}({\eta}_{k+1}) = X$. This, however, is useless because the only possible plans must apply a single, fixed action for every stage. Even if the approximations are better, it might still be impossible to cause transitions in the approximated I-state. To ensure that solutions exist to the planning problem, it is therefore important to make the bounding volumes as close as possible to the derived I-states.

This trade-off between the simplicity of bounding volumes and the computational expense of working with them was also observed in Section 5.3.2 for collision detection. Dramatic improvement in performance can be obtained by working with simpler shapes; however, in the present context this could come at the expense of failing to solve the problem. Using balls as described so far might not seem to provide very tight bounds. Imagine instead using solid ellipsoids. This would provide tighter approximations, but the dimension of ${\cal I}_{app}$ grows quadratically with the dimension of $X$. A sphere equation generally requires $n+1$ parameters, whereas the ellipsoid equation requires ${(^{n}_{2})} + 2n$ parameters. Thus, if the dimension of $X$ is high, it may be difficult or even impossible to use ellipsoid approximations. Nonconvex bounding shapes could provide even better approximations, but the required number of parameters could easily become unmanageable, even if $X = {\mathbb{R}}^2$. For very particular problems, however, it may be possible to design a family of shapes that is both manageable and tightly approximates the nondeterministic I-states. This leads to many interesting research issues.