As the name suggests, sensors are designed to sense the state.
Throughout all of this section it is assumed that the state space,
, is finite or countably infinite, as in Formulations 2.1
and 2.3. A sensor is defined in terms of two
components: 1) an observation space, which is the set of
possible readings for the sensor, and 2) a sensor mapping, which
characterizes the readings that can be expected if the current state
or other information is given. Be aware that in the planning model,
the state is not really given; it is only assumed to be given when
modeling a sensor. The sensing model given here generalizes the one
given in Section 9.2.3. In that case, the sensor provided
information regarding instead of because state spaces
were not needed in Chapter 9.
Let denote an observation space, which is a finite or
countably infinite set. Let denote the sensor mapping.
Three different kinds of sensor mappings will be considered, each of
which is more complicated and general than the previous one:
in which is the observation obtained in stage . Note that
the mapping is denoted as because the domain is different for
each . In general, any of the sensor mappings may be
stage-dependent, if desired.
- State sensor mapping: In this case,
means that given the state, the observation is completely determined.
- State-nature sensor mapping: In this case, a finite set,
, of nature sensing actions is defined for each . Each nature sensing action,
, interferes with the sensor observation.
Therefore, the state-nature mapping, , produces an observation,
, for every and
particular chosen by nature is assumed to be unknown during
planning and execution. However, it is specified as part of the
- History-based sensor mapping: In this case, the
observation could be based on the current state or any previous
states. Furthermore, a nature sensing action could be applied.
Suppose that the current stage is . The set of nature sensing
actions is denoted by , and the particular nature sensing
. This yields a very general sensor
Many examples of sensors will now be given. These are provided to
illustrate the definitions and to provide building blocks that will be
used in later examples of I-spaces. Examples 11.1 to
11.6 all involve state sensor mappings.
, the set of integers, and let
. The sensor
The limitation of this sensor is that it only tells whether
is odd or even. When combined with other information, this might be
enough to infer the state, but in general it provides incomplete
can be easily generalized to yield the
is divided by
for some fixed integer
, and let
. The sensor mapping is
, and let
. The sensor mapping is
This sensor provides very limited information because it only
indicates on which side of the boundary
the state may lie. It
can, however, precisely determine whether
, and let
denote a state in which
. Suppose that only the first component of
observed. This yields the sensor mapping
An obvious generalization can be made for any state space that is
formed from Cartesian products. The sensor may reveal the values of
one or more components, and the rest remain hidden.
be any state space, and let
. Let the sensor mapping
be any bijective function
. This sensor provides
information that is equivalent to knowing the state. Since
bijective, it can be inverted to obtain
, the state can be determined as
A special case of the bijective sensor is the identity
sensor, for which is the identity function. This was essentially
assumed to exist for all planning problems covered before this chapter
because it immediately yields the state. However, any bijective
sensor could serve the same purpose.
be any state space, and let
. The null
is obtained by defining the sensor mapping as
sensor reading remains fixed and hence provides no information
regarding the state.
From the examples so far, it is tempting to think about partitioning
based on sensor observations. Suppose that in general a state
mapping, , is not bijective, and let denote the following
subset of :
which is the preimage of .
The set of preimages, one for each , forms a partition of .
In some sense, this indicates the ``resolution'' of the sensor. A
bijective sensor partitions into singleton sets because it
contains perfect information. At the other extreme, the null sensor
partitions into a single set, itself. The sign sensor appears
slightly more useful because it partitions into three sets:
The preimages of the selective sensor are particularly interesting.
. The partitions induced by the
preimages may remind those with an algebra background of the
construction of quotient groups via homomorphisms .
Next consider some examples that involve a state-action sensor
mapping. There are two different possibilities regarding the model
for the nature sensing action:
These two possibilities also appeared in Section 10.1.1,
for nature actions that interfere with the state transition equation.
- Nondeterministic: In this case, there is no additional
information regarding which
will be chosen.
- Probabilistic: A probability distribution is known. In
this case, the probability, , that will be chosen
is known for each
It is sometimes useful to consider the state-action sensor model as a
probability distribution over for a given state. Recall the
(9.28). By replacing by , the same idea can
be applied here. Assume that if the domain of is restricted to
some , it forms an injective (one-to-one) mapping from
to . In this case,
If the injective assumption is lifted, then is replaced by a
sum over all for which
. The idea is to
construct a sensor that would be the identity sensor if it were not
for the interference of nature. The sensor mapping is
It is always known that
. Therefore, if
received as a sensor reading, one of the following must be true:
(Disturbed Sign Sensor)
. Let the
sensor mapping be
In this case, if
, it is no longer known for certain whether
. It is possible that
, then it is
possible for the sensor to read
(Disturbed Odd/Even Sensor)
It is not hard to construct examples for which some mild interference
from nature destroys all of the information. Let
. Let the sensor mapping be
Under the nondeterministic model for the nature sensing action
the sensor provides no useful information regarding the state.
Regardless of the observation, it is never known whether
or odd. Under a probabilistic model, however, this sensor may provide
some useful information.
It is once again informative to consider preimages. For a
state-action sensor mapping, the preimage is
In comparison to state sensor mappings, the preimage sets are larger
for state-action sensor mappings. Also, they do not generally form a
partition of . For example, the preimages of Example
. This is not a
partition because every preimage contains 0. If desired, can
be directly defined for each , instead of explicitly defining
nature sensing actions.
Finally, one example of a history-based sensor mapping is given.
. A delayed-observation sensor
can be defined
for some fixed positive integer
. It indicates
what the state was
stages ago. In this case, it gives a perfect
measurement of the old state value. Many other variants are possible.
For example, it might only give the sign of the state from
Steven M LaValle