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

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

(11.42) |

A possible I-state is . Using the nondeterministic I-space from Section 11.2.2, , 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 , it is known that ; hence, . If , it will always be the case that unless 0 is observed. If , then . From this a plan, , can be specified over the three nondeterministic I-states mentioned above. For the first one, . For the other two, and , 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 be defined as

(11.43) |

This provides dramatic memory savings over defining a plan on .

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).

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 I-states, but it can be mapped to a
much smaller derived I-space that contains only a few elements.

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

(11.44) |

and let . The state transition equation is defined as whenever such motion is not blocked (by hitting a dead end). For example, if , , and , then the resulting next state is . If blocking is possible, the state changes as much as possible until it becomes blocked. Due to blocking, it is even possible that .

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

(11.45) |

Now use the nondeterministic I-space, . The initial state, , is given, which means that the initial I-state, , is . The goal is to arrive at the I-state, , 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 from the initial state, the nondeterministic I-state becomes . After it becomes . A nice feature of this problem, however, is that uncertainty can be reduced without sensing. Suppose that for stages, we repeatedly apply . 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, , decreases the coordinate by at least one each time. Therefore, after nine or more stages, it is known that . Once this is known, then the action can be applied. This will again increase uncertainty as the state moves through the set of left states. If is applied nine or more times, then it is known for certain that , which is the required goal state.

A successful plan has now been obtained: 1) Apply for nine stages, 2) then apply for nine stages. This plan could be defined over ; however, it is simpler to use the I-map from Example 11.12 to define a plan as . For such that , . For such that , . For , . Note that the plan works even if the initial condition is any subset of . 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 . Let be an I-map from to a set of three derived I-states. Let , in which denotes ``goal,'' denotes ``left,'' and denotes ``any.'' The I-map, , is

(11.46) |

Based on the successful plan described so far, a solution on is defined as , , and . This plan is simpler to represent than the one on ; however, there is one drawback. The I-map 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 is applied from , how can the robot determine whether or 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,
, which is sufficient. There are derived
I-states, which include as defined previously, for
, and for
. The I-map is defined as
if
. Otherwise,
for the smallest value of such that
is a subset of
. If there is no
such value for , then
, for the smallest
value of such that is a subset of
. Now the plan is defined
as
,
, and
. 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
is applied
at , then is obtained. If
is applied at
, then is obtained. From there, is applied to
yield . These actions can be repeated until eventually and
are reached. The resulting plan, however, is not an improvement
over the original open-loop one.

Steven M LaValle 2012-04-20