9.5.3 Concerns Regarding the Nondeterministic Model

Given all of the problems with probabilistic modeling, it is tempting to abandon the whole framework and work strictly with the nondeterministic model. This only requires specifying , without indicating anything about the relative likelihoods of various actions. Therefore, most of the complicated issues presented in Sections 9.5.1 and 9.5.2 vanish. Unfortunately, this advantage comes at a substantial price. Making decisions with worst-case analysis under the nondeterministic model has its own shortcomings. After considering the trade-offs, you can decide which is most appropriate for a particular application of interest.

The first difficulty is to ensure that is sufficiently large
to cover all possibilities. Consider Formulation 9.6,
in which nature acts twice. Through a nature observation action
space,
, interference is caused in the measurement
process. Suppose that
and
. In this case,
can be interpreted as the
measurement error. What is the maximum amount of error that can
occur? Perhaps a sonar is measuring the distance from the robot to a
wall. Based on the sensor specifications, it may be possible to
construct a nice bound on the error. Occasionally, however, the error
may be larger than this bound. Sonars sometimes fail to hear the
required echo to compute the distance. In this case the reported
distance is . Due to reflections, extremely large errors can
sometimes occur. Although such errors may be infrequent, if we want
*guaranteed* performance, then large or even infinite errors
should be included in
. The problem is that worst-case
reasoning could always conclude that the sensor is useless by
reporting . Any statistically valid information that could be
gained from the sensor would be ignored. Under the probabilistic
model, it is easy to make
quite large and then assign
very small probabilities to larger errors. The problem with
nondeterministic uncertainty is that
needs to be
smaller to make appropriate decisions; however, theoretically
``guaranteed'' performance may not truly be guaranteed in practice.

Once a nondeterministic model is formulated, the optimal decision rule may produce results that seem absurd for the intended application. The problem is that the DM cannot tolerate any risk. An action is applied only if the result can be guaranteed. The hope of doing better than the worst case is not taken into account. Consider the following example:

The following cost matrix reflects the outcomes (ignoring utility theory):

Using probabilistic analysis, we might conclude that it is best to take the check. Perhaps the friend is even known to be very wealthy and responsible with banking accounts. This information, however, cannot be taken into account in the decision-making process. Using worst-case analysis, the optimal action is to take the 1 Euro in cash. You may not feel too good about it, though. Imagine the regret if you later learn that the account had sufficient funds to cash the check for 1000 Euros.

Thus, it is important to remember the price that one must pay for wanting results that are absolutely guaranteed. The probabilistic model offers the flexibility of incorporating statistical information. Sometimes the probabilistic model can be viewed as a generalization of the nondeterministic model. If it is assumed that nature acts after the robot, then the nature action can take this into account, as incorporated into Formulation 9.4. In the nondeterministic case, is specified, and in the probabilistic case, is specified. The distribution can be designed so that nature selects with very high probability the that maximizes . In Example 9.28, this would mean that the probability that the check would bounce (resulting in no earnings) would by very high, such as . In this case, even the optimal action under the probabilistic model is to select the 1 Euro in cash. For virtually any decision problem that is modeled using worst-case analysis, it is possible to work backward and derive possible priors for which the same decision would be made using probabilistic analysis. In Example 9.4, it seemed as if the decision was based on assuming that with very high probability, the check would bounce, even though there were no probabilistic models.

This means that worst-case analysis under the nondeterministic model can be considered as a special case of a probabilistic model in which the prior distribution assigns high probabilities to the worst-case outcomes. The justification for this could be criticized in the same way that other prior assignments are criticized in Bayesian analysis. What is the basis of this particular assignment?

Steven M LaValle 2012-04-20