## 11.5.2 Simple Projection Examples

This section gives examples of I-spaces for which the sensor mapping is and is a projection that reveals some of the state variables, while concealing others. The examples all involve continuous time, and the focus is mainly on the nondeterministic I-space . It is assumed that there are no actions, which means that . Nature actions, , however, will be allowed. Since there are no robot actions and no nature sensing actions, all of the uncertainty arises from the fact that is a projection and the nature actions that affect the state transition equation are not known. This is a very important and interesting class of problems in itself. The examples can be further complicated by allowing some control from the action set, ; however, the purpose here is to illustrate I-space concepts. Therefore, it will not be necessary. Example 11..20 (Moving on a Sine Curve)   Suppose that the state space is the set of points that lie on the sine curve in the plane: (11.72)

Let , which results in no action history. The observation space is and the sensor mapping yields , the height of the point on the sine curve, as shown in Figure 11.17.

The nature action space is , in which means to move at unit speed in the direction along the sine curve, and means to move at unit speed in the direction along the curve. Thus, for some nature action history , a state trajectory that moves the point along the curve can be determined by integration. A history I-state takes the form , which includes the initial condition and the observation history up to time . The nondeterministic I-states are very interesting for this problem. For each observation , the preimage is a countably infinite set of points that corresponds to the intersection of with a horizontal line at height , as shown in Figure 11.18.

The uncertainty for this problem is always characterized by the number of intersection points that might contain the true state. Suppose that . In this case, there is no state trajectory that can reduce the amount of uncertainty. As the point moves along , the height is always known because of the sensor, but the coordinate can only be narrowed down to being any of the intersection points. Suppose instead that , in which is some particular point along . If remains within over some any period of time starting at , then is known because the exact segment of the sine curve that contains the state is known. However, if the point reaches an extremum, which results in or , then it is not known which way the point will travel. From this point, the sensor cannot disambiguate moving in the direction from the direction. Therefore, the uncertainty grows, as shown in Figure 11.19. After the observation is obtained, there are two possibilities for the current state, depending on which action was taken by nature when ; hence, the nondeterministic I-state contains two states. If the motion continues until , then there will be four states in the nondeterministic I-state. Unfortunately, the uncertainty can only grow in this example. There is no way to use the sensor to reduce the size of the nondeterministic I-states.  The previous example can be generalized to observing a single coordinate of a point that moves around in a planar topological graph, as shown in Figure 11.20a. Most of the model remains the same as for Example 11.20, except that the state space is now a graph. The set of nature actions, , needs to be extended so that if is a vertex of the graph, then there is one input for each incident edge. These are the possible directions along which the point could move. Example 11..21 (Observing a Point on a Graph)   Consider the graph shown in Figure 11.20b, in which there are four edges.11.8 When the point moves on the interior of the rightmost edge of the graph, then the state can be inferred from the sensor. The set contains a single point on the rightmost edge. If the point moves in the interior of one of the other edges, then contains three points, one for each edge above . This leads to seven possible cases for the nondeterministic I-state, as shown in Figure 11.21. Any subset of these edges may be possible for the nondeterministic I-state, except for the empty set.

The eight pieces of depicted in Figure 11.21 are connected together in an interesting way. Suppose that the point is on the rightmost edge and moves left. After crossing the vertex, the I-state must be the case shown in the upper right of Figure 11.21, which indicates that the point could be on one of two edges. If the point travels right from one of the I-states of the left edges, then the I-state shown in the bottom right of Figure 11.20 is always reached; however, it is not necessarily possible to return to the same I-state on the left. Thus, in general, there are directional constraints on . Also, note that from the I-state on the lower left of Figure 11.20, it is impossible to reach the I-state on the lower right by moving straight right. This is because it is known from the structure of the graph that this is impossible.  The graph example can be generalized substantially to reflect a wide variety of problems that occur in robotics and other areas. For example, Figure 11.22 shows a polygon in which a point can move. Only one coordinate is observed, and the resulting nondeterministic I-space has layers similar to those obtained for Example 11.21. These ideas can be generalized to any dimension. Interesting models can be constructed using the simple projection sensors, such as a position sensor or compass, from Section 11.5.1. In Section 12.4, such layers will appear in a pursuit-evasion game that uses visibility sensors to find moving targets.

Steven M LaValle 2012-04-20