9 Planning with Uncertainty

9.2 One-Off Decisions

Dimensions: flat, features, finite horizon, partially observable, stochastic, utility, non-learning, single agent, offline, perfect rationality

Basic decision theory applied to intelligent agents relies on the following assumptions:

  • Agents know what actions they can carry out.

  • The effect of each action can be described as a probability distribution over outcomes.

  • An agent’s preferences are expressed by utilities of outcomes.

It is a consequence of Proposition 9.3 that, if agents only act for one step, a rational agent should choose an action with the highest expected utility.

Figure 9.6: A decision tree for the delivery robot. Square boxes represent decisions that the robot can make. Circles represent random variables that the robot cannot observe before making its decision.
Example 9.6.

Consider the problem of the delivery robot in which there is uncertainty in the outcome of its actions. In particular, consider the problem of going from position o109 in Figure 3.1 to the mail position, where there is a chance that the robot will slip off course and fall down the stairs. Suppose the robot can get pads that will not change the probability of an accident but will make an accident less severe. Unfortunately, the pads add extra weight. The robot could also go the long way around, which would reduce the probability of an accident but make the trip much slower.

Thus, the robot has to decide whether to wear the pads and which way to go (the long way or the short way). What is not under its direct control is whether there is an accident, although this probability can be reduced by going the long way around. For each combination of the agent’s choices and whether there is an accident, there is an outcome ranging from severe damage to arriving quickly without the extra weight of the pads.

In one-off decision making, a decision variable is used to model an agent’s choice. A decision variable is like a random variable, but it does not have an associated probability distribution. Instead, an agent gets to choose a value for a decision variable. A possible world specifies values for both random and decision variables. Each possible world has an associated utility. For each combination of values to decision variables, there is a probability distribution over the random variables. That is, for each assignment of a value to each decision variable, the measures of the worlds that satisfy that assignment sum to 1.

Figure 9.6 shows a decision tree that depicts the different choices available to the agent and the outcomes of those choices. To read the decision tree, start at the root (on the left in this figure). For the decision nodes, shown as squares, the agent gets to choose which branch to take. For each random node, shown as a circle, the agent does not get to choose which branch will be taken; rather there is a probability distribution over the branches from that node. Each leaf corresponds to a world, which is the outcome if the path to that leaf is followed.

Example 9.7.

In Example 9.6 there are two decision variables, one corresponding to the decision of whether the robot wears pads and one to the decision of which way to go. There is one random variable, whether there is an accident or not. Eight possible worlds correspond to the eight paths in the decision tree of Figure 9.6.

What the agent should do depends on how important it is to arrive quickly, how much the pads’ weight matters, how much it is worth to reduce the damage from severe to moderate, and the likelihood of an accident.

The proof of Proposition 9.3 specifies how to measure the desirability of the outcomes. Suppose we decide to have utilities in the range [0,100]. First, choose the best outcome, which would be w5, and give it a utility of 100. The worst outcome is w6, so assign it a utility of 0. For each of the other worlds, consider the lottery between w6 and w5. For example, w0 may have a utility of 35, meaning the agent is indifferent between w0 and [0.35:w5,0.65:w6], which is slightly better than w2, which may have a utility of 30. w1 may have a utility of 95, because it is only slightly worse than w5.

Example 9.8.

In medical diagnosis, decision variables correspond to various treatments and tests. The utility may depend on the costs of tests and treatment and whether the patient gets better, stays sick, or dies, and whether they have short-term or chronic pain. The outcomes for the patient depend on the treatment the patient receives, the patient’s physiology, and the details of the disease, which may not be known with certainty.

The same approach holds for diagnosis of artifacts such as airplanes; engineers test components and fix them. In airplanes, you may hope that the utility function is to minimize accidents (maximize safety), but the utility incorporated into such decision making is often to maximize profit for a company and accidents are simply costs taken into account.

In a one-off decision, the agent chooses a value for each decision variable simultaneously. This can be modeled by treating all the decision variables as a single composite decision variable, D. The domain of this decision variable is the cross product of the domains of the individual decision variables.

Each world ω specifies an assignment of a value to the decision variable D and an assignment of a value to each random variable. Each world has a utility, given by the variable u.

A single decision is an assignment of a value to the decision variable. The expected utility of single decision D=di is (uD=di), the expected value of the utility conditioned on the value of the decision. This is the average utility of the worlds where the worlds are weighted according to their probability:

(uD=di)=ω:D(ω)=diu(ω)*P(ω),

where D(ω) is the value of variable D in world ω, u(ω) is the value of utility in ω, and P(ω) is the probability of world ω.

An optimal single decision is the decision whose expected utility is maximal. That is, D=dmax is an optimal decision if

(uD=dmax)=maxdidomain(D)(uD=di),

where domain(D) is the domain of decision variable D. Thus,

dmax=argmaxdidomain(D)(uD=di).
Example 9.9.

The delivery robot problem of Example 9.6 is a single decision problem where the robot has to decide on the values for the variables Wear_pads and Which_way. The single decision is the complex decision variable Wear_pads,Which_way. Each assignment of a value to each decision variable has an expected value. For example, the expected utility of Wear_pads=trueWhich_way=short is given by

(uwear_padsWhich_way=short)
    =P(accidentwear_padsWhich_way=short)*u(w0)
    +(1-P(accidentwear_padsWhich_way=short))*u(w1),

where u(wi) is the value of the utility in worlds wi, the worlds w0 and w1 are as in Figure 9.6, and wear_pads means Wear_pads=true.