11.5.3 Examples with Nature Sensing Actions

This section illustrates the effect of nature sensing actions, but only for the nondeterministic case. General methods for computing probabilistic I-states are covered in Section 11.6.

Figure 11.23: (a) It is always possible to determine whether the state trajectory went above or below the designated region. (b) Now the ability to determine whether the trajectory went above or below the hole depends on the particular observations. In some cases, it may not be possible.

Figure 11.24: Nature interferes with the commanded direction, so that the true state could be anywhere within a circular section.

Example 11..22 (Above or Below Disc?)   This example involves continuous time. Suppose that the task is to gather information and determine whether the state trajectory travels above or below some designated region of the state space, as shown in Figure 11.23.

Let $X = {\mathbb{R}}^2$. Motions are generated by integrating the velocity $({\dot x},{\dot y})$, which is expressed as ${\dot x}= \cos(u(t) + \theta(t))$ and ${\dot y}= \sin(u(t) + \theta(t))$. For simplicity, assume $u(t) = 0$ is applied for all time, which is a command to move right. The nature action $\theta(t) \in \Theta = [-\pi/4,\pi/4]$ interferes with the outcome. The robot tries to make progress by moving in the positive $x_1$ direction; however, the interference of nature makes it difficult to predict the $x_2$ direction. Without nature, there should be no change in the $x_2$ coordinate; however, with nature, the error in the $x_2$ direction could be as much as $t$, after $t$ seconds have passed. Figure 11.24 illustrates the possible resulting motions.

Sensor observations will be made that alleviate the growing cone of uncertainty; use the sensing model from Figure 11.11, and suppose that the measurement error $r$ is $1$. Suppose there is a disc in ${\mathbb{R}}^2$ of radius larger than $1$, as shown in Figure 11.23a. Since the true state is never further than $1$ from the measured state, it is always possible to determine whether the state passed above or below the disc. Multiple possible observation histories are shown in Figure 11.23a. The observation history need not even be continuous, but it is drawn that way for convenience. For a disc with radius less than $1$, there may exist some observation histories for which it is impossible to determine whether the true state traveled above or below the disc; see Figure 11.23b. For other observation histories, it may still be possible to make the determination; for example, from the uppermost trajectory shown in Figure 11.23b it is known for certain that the true state traveled above the disc. $\blacksquare$

Example 11..23 (A Simple Mobile Robot Model)   In this example, suppose that a robot is modeled as a point that moves in $X = {\mathbb{R}}^2$. The sensing model is the same as in Example 11.22, except that discrete stages are used instead of continuous time. It can be imagined that each stage represents a constant interval of time (e.g., $1$ second).

Figure 11.25: A simple mobile robot motion model in which the sensing model is as given in Figure 11.11 and then nature interferes with commanded motions to yield an uncertainty region that is a circular ring.

To control the robot, a motion command is given in the form of an action $u_k \in U = {\mathbb{S}}^1$. Nature interferes with the motions in two ways: 1) The robot tries to travel some distance $d$, but there is some error $\epsilon_d > 0$, for which the true distance traveled, $d^\prime$, is known satisfy $\vert d^\prime - d\vert < \epsilon_d$; and 2) the robot tries to move in a direction $u$, but there is some error, $\epsilon_u > 0$, for which the true direction $u^\prime$ is known to satisfy $\vert u - u^\prime\vert < \epsilon_u$. These two independent errors can be modeled by defining a 2D nature action set, $\Theta(x)$. The transition equation is then defined so that the forward projection $F(x,u)$ is as shown in Figure 11.25.

Figure 11.26: (a) Combining information from $X_2({\eta }_1,u_1)$ and the observation $y_2$; (b) the intersection must be taken between $X_2({\eta }_1,u_1)$ and $H(y_2)$. (c) The action $u_2$ leads to a complicated nondeterministic I-state that is the union of $F(x_2,u_2)$ over all $x_2 \in X_2({\eta }_2)$.

Some nondeterministic I-states will now be constructed. Suppose that the initial state $x_1$ is known, and history I-states take the form

$${\eta}_k = (x_1,u_1,\ldots,u_{k-1},y_1,\ldots,y_k) .$$ (11.73)

The first sensor observation, $y_1$, is useless because the initial state is known. Equation (11.29) is applied to yield $H(y_1) \cap \{x_1\} = \{x_1\}$. Suppose that the action $u_1 = 0$ is applied, indicating that the robot should move horizontally to the right. Equation (11.30) is applied to yield $X_2({\eta }_1,u_1)$, which looks identical to the $F(x,u)$ shown in Figure 11.25. Suppose that an observation $y_2$ is received as shown in Figure 11.26a. Using this, $X_2({\eta}_2)$ is computed by taking the intersection of $H(y_2)$ and $X_2({\eta }_1,u_1)$, as shown in Figure 11.26b.

Figure 11.27: After the sensor observation, $y_3$, the intersection must be taken between $X_3({\eta }_2,u_2)$ and $H(y_3)$.

The next step is considerably more complicated. Suppose that $u_2 = 0$ and that (11.30) is applied to compute $X_3({\eta }_2,u_2)$ from $X_2({\eta}_2)$. The shape shown in Figure 11.26c is obtained by taking the union of $F(x_2,u_2)$ for all possible $x_2 \in X_2({\eta }_2)$. The resulting shape is composed of circular arcs and straight line segments (see Exercise 13). Once $y_3$ is obtained, an intersection is taken once again to yield $X_3({\eta}_3) = X_3({\eta}_2,u_2) \cap H(y_3)$, as shown in Figure 11.27. The process repeats in the same way for the desired number of stages. The complexity of the region in Figure 11.26c provides motivation for the approximation methods of Section 11.4.3. For example, the nondeterministic I-states could be nicely approximated by ellipsoidal regions. $\blacksquare$