CSE443 Reasoning Under Uncertainty

Exercise Sheet 4: Decision Making


  1. Expected utility
  2. Russell and Norvig, Exercise 16.2

    1. R&N 16.2 Tickets to the state lottery cost $1. There are two possible prizes: a $10 payoff with probability 1/50 and a $1,000,000 payoff with probability 1/2,000,000. What is the expected monetry value of a lottery ticket? When (if ever) is it rational to buy a ticket? Be precise - show an equation involving utilities. You may assume that U($10) = 10 x U($1), but you may not make any assumptions about U($1,000,000). Sociological studies show that people with lower income buy a disproportionate number of lottery tickets. Do you think this is because they are worse decision makers or because they have a different utility function?

  3. Decision networks: Delivery Robot
  4. (This example is adapted from an example in Computational Intelligence: A Logical Approach, D. Poole, A. Mackworth, R. Goebel, Oxford University Press, 1998.)

    Consider a robot that delivers parcels in an office environment. Suppose it has to go from the mail room to Office 203 and that there are two routes it can take:

    1. There is a shorter route that takes it past a stairwell, in which case there is a chance the robot will slip off course and fall down the stairs. It is possible to get pads for the robot that won't reduce the the probability of an accident but will reduce the damage. Unfortunately these pads add extra weight.
    2. There is a longer, safe route.

    (a) What are the robot's choices and what are the different utilities that have to be assessed?

    (b) Draw a decision network for this delivery robot decision problem. Your network should (at least) have two decision nodes, a chance node for accident and a utility node.

    (c) Write down CPTs and a utility function that seems reasonable for this problem.

  5. Decision networks: Oil Wildcatter robot
  6. Originally described by Raiffa (1968), with variation given by Shenoy (1992), and presented in Cowell et al. (1999).

    An oil wildcatter must decide either to drill or not drill. He is uncertain whether the hole is dry, wet or soaking. AT a cost of 10,000, the wildcatter could take seismic soundings which help determine the geological structure at the site. The soundings disclose whether the terrain below has no structure (that's bad), or open structure (that's so-so), or closed structure (that's really hopeful). Construct a decision network for this problem. (Hint: the network should have 2 utility nodes, 2 decision nodes and 2 random variable nodes.)

  7. Dynamic Decision networks: Temperature robot
  8. (This example is taken from Artificial Intelligence: A New Synthesis, N.J. Nilsson, Morgan Kaufmann, 1998. Ex 20.5)

    A robot lives in a 5x5 grid as shown. The numbers in the grid represent relative temperture values. Supose the robot begins in one of the cells with temperature = 2. It doesn't know which of the possible temperature = 2 cells it begins in, but it does have a map of the grid showing the temperature cells.

    Robot temperature grid

    Assume that the robot can accurately sense the temperature value of the cell it occupies. It is capable of four moving actions: north, eastsouth and west. It must choose among them in order to maximize its expected temperature.

    Ordinarily, each of the actions would move the robot one cell in the indicated direction, but if there is a strong southwesterly wind blowing the actions have the following effects whenever the robot is in a cell with temperature = 2.

    south: has no effect
    west: has no effect
    north: moves one cell north with probability 0.5
    north: moves two cells north with probability 0.25
    north: moves one cell east with probability 0.25
    east: moves one cell east with probability 0.5
    east: moves one cell east with probability 0.5

    (a) Construct a dynamic decision network corresponding to one action step. This should include both the network structure and the CPTs. The network will include an action node, ordinary chance variable nodes (e.g. location, temperature SWWind), and a value node (temperature). It will have to represent the nodes at two time-slices, T0 and T1.

    (b) Calculate the expected temperature, E(Temp1|A0) for each of the four actions.

    (c) Now suppose that the robot is not sure of its temperature at time t=t0. Instead it sense a signal S0=2, while informs it about its temperature. The sensor model for S0 includes

    P(S0=2 | Temp0=2) = 0.9
    P(S0=2 | Temp0=3) = 0.3
    P(S0=2 | Temp0=i) = 0 for all values of i different from 2 or 2.

    Extend your decision network to incorporate this sensor model.

    (d) Assuming that the actions have the same effects when taken in a cell with temperature = 3 as they do when taken in a cell with temperature = 2, what is the expected temperature resulting from each of the four actions in this case (i.e. when starting in a location with temperature = 3)?

    (e) (CPT Representation) Consider the CPT you used for the location node at T1. What would a classification tree representation of this CPT look like? Is it a more compact representation?