12.3.1 Grid Problems

To gain a clear understanding of the issues, it will once again be helpful to consider discrete problems. The discussion here is a continuation of Section 12.2.1. In that section, the state represented a position, $p$, and a direction, $d$. Now suppose that the state is represented as $(p,d,e)$, in which $e$ represents the particular environment that contains the robot. This will require defining a space of environments, which is rarely represented explicitly. It is often expressed as a constraint on the types of environments that can exist. For example, the set of environments could be defined as all connected 2D grid-planning problems. The set of simply connected grid-planning problems is even further constrained.

One question immediately arises: When are two maps of an environment equivalent? Recall the maps shown in Figures 12.2a and 12.3b. The map in Figure 12.3b appears the same for every 90-degree rotation; however, the map in Figure 12.2a appears to be different. Even if it appears different, it should still be the same environment, right? Imagine mapping a remote island without having a compass that indicates the direction to the north pole. An orientation (which way is up?) for the map can be chosen arbitrarily without any harm. If a map of the environment is made by ``drawing'' on ${\mathbb{R}}^2$, it should seem that two maps are equivalent if a transformation in $SE(2)$ (i.e., translation and rotation) can be applied to overlay one perfectly on top of the other.

When defining an environment space, it is important to clearly define what it means for two environments to be equivalent. For example, if we are required to build a map by exploration, is it required to also provide the exact translation and orientation? This may or may not be required, but it is important to specify this in the problem description. Thus, we will allow any possibility: If the maps only differ by a transformation in $SE(2)$, they may or may not be defined as equivalent, depending on the application.

To consider some examples, it will be convenient to define some finite or infinite sets of environments. Suppose that planning on a 2D grid is once again considered. In this section, assume that each grid point $p$ has integer coordinates $(i,j) \in {\mathbb{Z}}\times {\mathbb{Z}}$, as defined in Section 2.1. Let $E$ denote a set of environments. Once again, there are four possible directions for the robot to face; let $D$ denote this set. The state space is

$$X = {\mathbb{Z}}\times {\mathbb{Z}}\times D \times E .$$ (12.23)

Assume in general that an environment, $e \in E$, is specified by indicating a subset of ${\mathbb{Z}}\times {\mathbb{Z}}$ that corresponds to the positions of all of the white tiles on which the robot can be placed. All other tiles are black, which means that they are obstacles. If any subset of ${\mathbb{Z}}\times {\mathbb{Z}}$ is allowed, then $E = {\rm pow}({\mathbb{Z}}\times {\mathbb{Z}})$. This includes many useless maps, such as a checkerboard that spans the entire plane; this motivates some restrictions on $E$. For example, $E$ can be restricted to be the subset of ${\rm pow}({\mathbb{Z}}\times {\mathbb{Z}})$ that corresponds to all maps that include a white tile at the origin, $(0,0)$, and for which all other white tiles are reachable from it and lie within a bounded region.

Examples will be given shortly, but first think about the kinds of problems that can be formulated:

1. Map building: The task is to visit every reachable tile and construct a map. Depending on how $E$ is defined, this may identify a particular environment in $E$ or a set of environments that are consistent with the exploration. This may also be referred to as simultaneous localization and mapping, or SLAM, because constructing a complete map usually implies that the robot position and orientation are eventually known [483,970]. Thus, the complete state, $x \in X$, as given in (12.23) is determined by the map-building process. For the grid problem considered here, this point is trivial, but the problem becomes more difficult for the case of probabilistic uncertainty in a continuous environment. See Section 12.3.5 for this case.
2. Determining the environment: Imagine that a robot is placed into a building at random and then is switched on. The robot is told that it is in one of a fixed (i.e., 10) number of buildings. It must move to determine which one. As the number of possible environments is increased, the problem appears to be more like map building. In fact, map building can be considered as a special case in which little or no constraints are initially imposed on the set of possible environments.
3. Navigation: In this case, a goal position is to be reached, even though the robot has no map. The location of the goal relative to the robot can be specified through a sensor. The robot is allowed to solve this problem without fully exploring the environment. Thus, the final nondeterministic I-state after solving the task could contain numerous possible environments. Only a part of the environment is needed to solve the problem.
4. Searching: In this case, a goal state can only be identified when it is reached (or detected by a short-range sensor). There are no additional sensors to help in the search. The environment must be systematically explored, but the search may terminate early if the goal is found. A map does not necessarily have to be constructed. Searching can be extended to pursuit-evasion, which is covered in Section 12.4.

Simple examples of determining the environment and navigation will now be given.

Figure 12.12: A set of possible 2D grid environments. In each case, the ``up'' direction represents north and the white circle represents the origin, $p = (0,0)$.

Figure 12.13: Add these environments to the set depicted in Figure 12.12. Each is essentially equivalent to an environment already given and generally does not affect the planning problem.

Example 12..4 (Determining the Environment)   Suppose that the robot is told that it was placed into one of the environments shown in Figure 12.12. Let the initial position of the robot be $(0,0)$, which is shown as a white circle. Let the initial direction be east and the environment be $e_3$. These facts are unknown to the robot. Use the same actions and state transition model as in Section 12.2.1. The current state space includes the environment, but the environment never changes. Only information regarding which environment the robot is in will change. The sensing model again only indicates whether the robot has changed its position from the application of the last action.

The initial condition is $X$, because any position, orientation, and environment are possible. Some nondeterministic I-states will now be determined. Let $(u_1,u_2,u_3) = ({\rm F},{\rm R},{\rm R})$. From this sequence of actions, the sensor observations $(y_2,y_3,y_4)$ report that the robot has not yet changed its position. The orientation was changed to west, but this is not known to the robot (it does, however, know that it is now pointing in the opposite direction with respect to its initial orientation). What can now be inferred? The robot has discovered that it is on a tile that is bounded on three sides by obstacles. This means that $e_1$ and $e_6$ are ruled out as possible environments. In the remaining four environments, the robot deduces that it must be on one of the end tiles: 1) the upper left of $e_2$, 2) the upper right of $e_2$, 3) the bottom of $e_3$, 4) the rightmost of $e_3$, 5) the top of $e_4$, 6) the lower left of $e_5$, or 7) the upper left of $e_5$. It can also make strong inferences regarding its orientation. It even knows that the action $u_4 = {\rm R}$ would cause it to move because all four directions cannot be blocked.

Apply $(u_4,u_5) = ({\rm R},{\rm F})$. The robot should move two times, to arrive in the upper left of $e_3$ facing north. In this case, any of $e_2$, $e_3$, $e_4$, or $e_5$ are still possible; however, it now knows that its position at stage $4$ could not have been in the upper left of $e_5$. If the robot is in $e_3$, it knows that it must be in the upper left, but it still does not know its orientation (it could be north or west). The robot could also be in the lower left or lower right of $e_2$.

Now let $(u_6,u_7) = ({\rm R},{\rm F})$, which moves the robot twice. At this point, $e_4$ and $e_5$ are ruled out, and the set of possible environments is $\{e_2,e_3\}$ (one orientation from $e_2$ is also ruled out). If $u_8 = {\rm R}$ is applied, then the sensor observation $y_9$ reports that the robot does not move. This rules out $e_2$. Finally, the robot can deduce that it is in the upper right of $e_3$ facing south. It can also deduce that in its initial state it was in the lower left of $e_3$ facing east. Thus, all of the uncertainty has been eliminated through the construction of the nondeterministic I-states.

Now consider adding the environments shown in Figure 12.13 to the set and starting the problem over again. Environment $e_7$ is identical to $e_1$, except that the origin is moved, and $e_8$ is identical to $e_2$, except that it is rotated by $180$ degrees. In these two cases, there exist no inputs that enable the robot to distinguish between $e_1$ and $e_7$ or between $e_2$ and $e_8$. It is reasonable to declare these environments to be pairwise equivalent. The only distinction between them is the way that the map is drawn.

If the robot executes the same action sequence as given previously, then it will also not be able to distinguish $e_3$ from $e_9$. It is impossible for the robot to deduce whether there is a white tile somewhere that is not reachable. A general environment space may include such variations, and this will prevent the robot from knowing the precise environment. However, this usually presents no additional difficulty in solving a planning problem. Therefore, it might make sense to declare $e_3$ and $e_9$ to be equivalent. The fact that tasks can be achieved without knowing the precise environment is very important. In a sense, the environment is observed at some ``resolution'' that is sufficient for solving a problem; further details beyond that are unimportant. Since the robot can ignore unnecessary details, cheaper and more reliable systems can often be built. $\blacksquare$

Example 12..5 (Reaching a Goal State)   Suppose once again that the set of environments shown in Figure 12.12 is given. This time, also assume that the position $p = (0,0)$ and orientation east are known. The environment is $e_4$, but it is unknown to the robot. The task is to reach the position $(2,0)$, which means that the robot must move two tiles to the east. The plan $(u_1,u_2) = ({\rm F},{\rm F})$ achieves the goal without providing much information about the environment. After $u_1 = {\rm F}$ is applied, it is known that the environment is not $e_3$; however, after this, no additional information is gathered regarding the environment because it is not relevant to solving the problem. If the goal had been to reach $(2,2)$, then more information would be obtained regarding the environment. For example, if the plan is $({\rm F},{\rm L},{\rm R},{\rm L})$, then it is known that the environment is $e_6$. $\blacksquare$