11.3.1 Basic Nondeterministic Examples

First, we consider a simple example that uses the sign sensor of Example 11.3.

Example 11..15 (Using the Sign Sensor)   This example is similar to Example 10.1, except that it involves sensing uncertainty instead of prediction uncertainty. Let $X = {\mathbb{Z}}$, $U = \{-1,1,u_T\}$, $Y = \{-1,0,1\}$, and $y = h(x) = {\rm sgn}x$. For the state transition equation, $x_{k+1} = f(x_k,u_k) = x_k+u_k$. No nature actions interfere with the state transition equation or the sensor mapping. Therefore, future history I-states are predictable. The information transition equation is ${\eta}_{k+1} = {f_{\cal I}}({\eta}_k,u_k)$. Suppose that initially, ${\eta_0}= X$, which means that any initial state is possible. The goal is to terminate at $0 \in X$.

The general expression for a history I-state at stage $k$ is

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

A possible I-state is ${\eta}_5 = (X,-1,1,1,-1,1,1,1,1,0)$. Using the nondeterministic I-space from Section 11.2.2, ${\cal I}_{ndet}= {\rm pow}(X)$, which is uncountably infinite. By looking carefully at the problem, however, it can be seen that most of the nondeterministic I-states are not reachable. If $y_k = 0$, it is known that $x_k = 0$; hence, $X_k({\eta}_k) = \{0\}$. If $y_k = 1$, it will always be the case that $X_k({\eta}_k) = \{1,2,\ldots\}$ unless 0 is observed. If $y_k = -1$, then $X_k({\eta}_k) = \{\ldots,-2,-1\}$. From this a plan, $\pi$, can be specified over the three nondeterministic I-states mentioned above. For the first one, $\pi (X_k({\eta}_k)) = u_T$. For the other two, $\pi (X_k({\eta}_k)) = -1$ and $\pi (X_k({\eta}_k)) = 1$, respectively. Based on the sign, the plan tries to move toward 0. If different initial conditions are allowed, then more nondeterministic I-states can be reached, but this was not required as the problem was defined. Note that optimal-length solutions are produced by the plan.

The solution can even be implemented with sensor feedback because the action depends only on the current sensor value. Let $\pi: Y \rightarrow U$ be defined as

$$\pi (y) = \left\{ \begin{array}{ll} -1 & \mbox{ if $y = 1$} \\ 1 & \mbox{ if $y = -1$} \\ u_T & \mbox{ if $y = 0$.} \\ \end{array}\right.$$ (11.43)

This provides dramatic memory savings over defining a plan on ${\cal I}_{hist}$. $\blacksquare$

The next example provides a simple illustration of solving a problem without ever knowing the current state. This leads to the goal recognizability problem [659] (see Section 12.5.1).

Example 11..16 (Goal Recognizability)   Let $X = {\mathbb{Z}}$, $U = \{-1,1,u_T\}$, and $Y = {\mathbb{Z}}$. For the state transition equation, $x_{k+1} = f(x_k,u_k) = x_k+u_k$. Now suppose that a variant of Example 11.7 is used to model sensing: $y = h(x,\psi) = x + \psi$ and $\Psi = \{-5,-4,\ldots,5\}$. Suppose that once again, ${\eta_0}= X$. In this case, it is impossible to guarantee that a goal, $X_G = \{0\}$, is reached because of the goal recognizability problem. The disturbance in the sensor mapping does not allow precise enough state measurements to deduce the precise achievement of the state. If the goal region, $X_G$, is enlarged to $\{-5,-4,\ldots,5\}$, then the problem can be solved. Due to the disturbance, the nondeterministic I-state is always a subset of a consecutive sequence of $11$ states. It is simple to derive a plan that moves this interval until the nondeterministic I-state becomes a subset of $X_G$. When this occurs, then the plan applies $u_T$. In solving this problem, the exact state never had to be known. $\blacksquare$

The problem shown in Figure 11.7 serves two purposes. First, it is an example of sensorless planning[321,394], which means that there are no observations (see Sections 11.5.4 and 12.5.2). This is an interesting class of problems because it appears that no information can be gained regarding the state. Contrary to intuition, it turns out for this example and many others that plans can be designed that estimate the state. The second purpose is to illustrate how the I-space can be dramatically collapsed using the I-map concepts of Section 11.2.1. The standard nondeterministic I-space for this example contains $2^{19}$ I-states, but it can be mapped to a much smaller derived I-space that contains only a few elements.

Figure 11.7: An example that involves $19$ states. There are no sensor observations; however, actions can be chosen that enable the state to be estimated. The example provides an illustration of reducing the I-space via I-maps.

Example 11..17 (Moving in an L-shaped Corridor)   The state space $X$ for the example shown in Figure 11.7 has $19$ states, each of which corresponds to a location on one of the white tiles. For convenience, let each state be denoted by $(i,j)$. There are $10$ bottom states, denoted by $(1,1)$, $(2,1)$, $\ldots$, $(10,1)$, and $10$ left states, denoted by $(1,1)$, $(1,2)$, $\ldots$, $(1,10)$. Since $(1,1)$ is both a bottom state and a left state, it is called the corner state.

There are no sensor observations for this problem. However, nature interferes with the state transitions, which leads to a form of nondeterministic uncertainty. If an action is applied that tries to take one step, nature may cause two or three steps to be taken. This can be modeled as follows. Let

$$U = \{(1,0),(-1,0),(0,1),(0,-1)\}$$ (11.44)

and let $\Theta = \{1,2,3\}$. The state transition equation is defined as $f(x,u,\theta) = x + \theta u$ whenever such motion is not blocked (by hitting a dead end). For example, if $x = (5,1)$, $u = (-1,0)$, and $\theta = 2$, then the resulting next state is $(5,1)+2(-1,0) = (3,1)$. If blocking is possible, the state changes as much as possible until it becomes blocked. Due to blocking, it is even possible that $f(x,u,\theta) = x$.

Since there are no sensor observations, the history I-state at stage $k$ is

$${\eta}_k = ({\eta_0},u_1,\ldots,u_{k-1}) .$$ (11.45)

Now use the nondeterministic I-space, ${\cal I}_{ndet}= {\rm pow}(X)$. The initial state, $x_1 = (10,1)$, is given, which means that the initial I-state, ${\eta}_0$, is $\{(10,1)\}$. The goal is to arrive at the I-state, $\{(1,10)\}$, which means that the task is to design a plan that moves from the lower right to the upper left.

With perfect information, this would be trivial; however, without sensors the uncertainty may grow very quickly. For example, after applying the action $u_1 = (-1,0)$ from the initial state, the nondeterministic I-state becomes $\{(7,1),(8,1),(9,1)\}$. After $u_2 = (-1,0)$ it becomes $\{(4,1),\ldots,(8,1)\}$. A nice feature of this problem, however, is that uncertainty can be reduced without sensing. Suppose that for $100$ stages, we repeatedly apply $u_k = (-1,0)$. What is the resulting I-state? As the corner state is approached, the uncertainty is reduced because the state cannot be further changed by nature. It is known that each action, $u_k = (-1,0)$, decreases the $X$ coordinate by at least one each time. Therefore, after nine or more stages, it is known that ${\eta}_k = \{(1,1)\}$. Once this is known, then the action $(0,1)$ can be applied. This will again increase uncertainty as the state moves through the set of left states. If $(0,1)$ is applied nine or more times, then it is known for certain that $x_k = (1,10)$, which is the required goal state.

A successful plan has now been obtained: 1) Apply $(-1,0)$ for nine stages, 2) then apply $(0,1)$ for nine stages. This plan could be defined over ${\cal I}_{ndet}$; however, it is simpler to use the I-map ${{\kappa}_{stage}}$ from Example 11.12 to define a plan as $\pi : {\mathbb{N}}\rightarrow U$. For $k$ such that $1 \leq k \leq 9$, $\pi (k) = (-1,0)$. For $k$ such that $10 \leq k \leq 18$, $\pi (k) = (0,1)$. For $k > 18$, $\pi (k) = u_T$. Note that the plan works even if the initial condition is any subset of $X$. From this point onward, assume that any subset may be given as the initial condition.

Some alternative plans will now be considered by making other derived I-spaces from ${\cal I}_{ndet}$. Let ${\kappa}_3$ be an I-map from ${\cal I}_{ndet}$ to a set ${\cal I}_3$ of three derived I-states. Let ${\cal I}_3 = \{g,l,a\}$, in which $g$ denotes ``goal,'' $l$ denotes ``left,'' and $a$ denotes ``any.'' The I-map, ${\kappa}_3$, is

$$X({\eta}) = \left\{ \begin{array}{ll} g & \mbox{ if $X({\eta}) = ... ...bset of the set of left states} a & \mbox{ otherwise.} \end{array}\right.$$ (11.46)

Based on the successful plan described so far, a solution on ${\cal I}_3$ is defined as $\pi (g) = u_T$, $\pi (l) = (0,1)$, and $\pi (a) = (-1,0)$. This plan is simpler to represent than the one on ${\mathbb{N}}$; however, there is one drawback. The I-map ${\kappa}_3$ is not sufficient. This implies that more of the nondeterministic I-state needs to be maintained during execution. Otherwise, there is no way to know when certain transitions occur. For example, if $(-1,0)$ is applied from $a$, how can the robot determine whether $l$ or $a$ is reached in the next stage? This can be easily determined from the nondeterministic I-state.

To address this problem, consider a new I-map, ${\kappa}_{19}: {\cal I}_{ndet} \rightarrow {\cal I}_{19}$, which is sufficient. There are $19$ derived I-states, which include $g$ as defined previously, $l_i$ for $1 \leq j \leq 9$, and $a_i$ for $2 \leq i \leq 10$. The I-map is defined as ${\kappa}_{19}(X({\eta})) = g$ if $X({\eta}) = \{(1,10)\}$. Otherwise, ${\kappa}_{19}(X({\eta})) = l_i$ for the smallest value of $i$ such that $X({\eta})$ is a subset of $\{(1,i),\ldots,(1,10)\}$. If there is no such value for $i$, then ${\kappa}_{19}(X({\eta})) = a_i$, for the smallest value of $i$ such that $X({\eta})$ is a subset of $\{(1,1),\ldots,(1,10),(2,1),\ldots,(i,1)\}$. Now the plan is defined as $\pi (g) = u_T$, $\pi (l_i) = (0,1)$, and $\pi (a_i) = (-1,0)$. Although the plan is larger, the robot does not need to represent the full nondeterministic I-state during execution. The correct transitions occur. For example, if $u_k = (-1,0)$ is applied at $a_5$, then $a_4$ is obtained. If $u = (-1,0)$ is applied at $a_2$, then $l_1$ is obtained. From there, $u = (0,1)$ is applied to yield $l_2$. These actions can be repeated until eventually $l_9$ and $g$ are reached. The resulting plan, however, is not an improvement over the original open-loop one. $\blacksquare$