This section defines the I-map from Figure 11.3, which converts each history I-state into a subset of that corresponds to all possible current states. Nature is modeled nondeterministically, which means that there is no information about what actions nature will choose, other than that they will be chosen from and . Assume that the state-action sensor mapping from Section 11.1.1 is used. Consider what inferences may be drawn from a history I-state, . Since the model does not involve probabilities, let represent a set . Let be the minimal subset of in which is known to lie given . This subset is referred to as a nondeterministic I-state. To remind you that is a subset of , it will now be denoted as . It is important that be as small as possible while consistent with .
Recall from (11.6) that for every observation , a set of possible values for can be inferred. This could serve as a crude estimate of the nondeterministic I-state. It is certainly known that ; otherwise, , would not be consistent with the current sensor observation. If we carefully progress from the initial conditions while applying constraints due to the state transition equation, the appropriate subset of will be obtained.
From the state transition function , define a set-valued function that yields a subset of for every and as
An inductive process will now be described that results in computing the nondeterministic I-state, , for any stage . The base case, , of the induction proceeds as
Now assume inductively that has been computed and the task is to compute . From (11.15), . Thus, the only new pieces of information are that was applied and was observed. These will be considered one at a time.
Consider computing . If was known, then after applying , the state could lie anywhere within , using (11.28). Although is actually not known, it is at least known that . Therefore,
The next step is to take into account the observation . This information alone indicates that lies in . Therefore, an intersection is performed to obtain the nondeterministic I-state,
Since the nondeterministic I-state is always a subset of , the nondeterministic I-space, , is obtained (shown in Figure 11.3). If is finite, then is also finite, which was not the case with because the histories continued to grow with the number of stages. Thus, if the number of stages is unbounded or large in comparison to the size of , then nondeterministic I-states seem preferable. It is also convenient that is a sufficient I-map, as defined in Section 11.2.1. This implies that a planning problem can be completely expressed in terms of without maintaining the histories. The goal region, , can be expressed directly as a nondeterministic I-state. In this way, the planning task is to terminate in a nondeterministic I-state, , for which .
The sufficiency of is obtained because (11.30) and (11.31) show that can be computed from , , and . This implies that a derived information transition equation can be formed. The nondeterministic I-space can also be treated as ``just another state space.'' Although many history I-states may map to the same nondeterministic I-state, it has been assumed for decision-making purposes that particular history is irrelevant, once is given.
The following example is not very interesting in itself, but it is simple enough to illustrate the concepts.
The history I-space appears very cumbersome for this example, which only involves three states. The nondeterministic I-space for this example is
Now consider the execution over a number of stages. Suppose that the first observation is . Based on the sensor mapping, , which is not very helpful because . Applying (11.29) yields . Now suppose that the decision maker applies the action and nature applies . Using , this yields . The decision maker does not know and must therefore take into account any nature action that could have been applied. It uses (11.30) to infer that
Steven M LaValle 2012-04-20