Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

9.3.1 Decision Networks

A decision network (also called an influence diagram) is a graphical representation of a finite sequential decision problem. Decision networks extend belief networks to include decision variables and utility. A decision network extends the single-stage decision network to allow for sequential decisions.

In particular, a decision network is a directed acyclic graph (DAG) with chance nodes, decision nodes, and a utility node. This extends single-stage decision networks by allowing both chance nodes and decision nodes to be parents of decision nodes. Arcs coming into decision nodes represent the information that will be available when the decision is made. Arcs coming into chance nodes represents probabilistic dependence. Arcs coming into the utility node represent what the utility depends on.

A no-forgetting agent is an agent whose decisions are totally ordered, and the agent remembers its previous decisions and any information that was available to a previous decision. A no-forgetting decision network is a decision network in which the decision nodes are totally ordered and, if decision node Di is before Dj in the total ordering, then Di is a parent of Dj, and any parent of Di is also a parent of Dj. Thus, any information available to Di is available to Dj, and the action chosen for decision Di is part of the information available at decision Dj. The no-forgetting condition is sufficient to make sure that the following definitions make sense and that the following algorithms work.

figures/ch09/umbrella.png
Figure 9.7: Decision network for decision of whether to take an umbrella
Example 9.11: Figure 9.7 shows a simple decision network for a decision of whether the agent should take an umbrella when it goes out. The agent's utility depends on the weather and whether it takes an umbrella. However, it does not get to observe the weather. It only gets to observe the forecast. The forecast probabilistically depends on the weather.

As part of this network, the designer must specify the domain for each random variable and the domain for each decision variable. Suppose the random variable Weather has domain {norain,rain}, the random variable Forecast has domain {sunny,rainy,cloudy}, and the decision variable Umbrella has domain {takeIt,leaveIt}. There is no domain associated with the utility node. The designer also must specify the probability of the random variables given their parents. Suppose P(Weather) is defined by

P(Weather=rain)=0.3.

P(Forecast|Weather) is given by

Weather Forecast Probability
norain sunny 0.7
norain cloudy 0.2
norain rainy 0.1
rain sunny 0.15
rain cloudy 0.25
rain rainy 0.6

Suppose the utility function, Utility(Weather,Umbrella), is

Weather Umbrella Utility
norain takeIt 20
norain leaveIt 100
rain takeIt 70
rain leaveIt 0

There is no table specified for the Umbrella decision variable. It is the task of the planner to determine which value of Umbrella to select, depending on the forecast.

figures/ch09/diagnosisDN.png
Figure 9.8: Decision network for diagnosis
Example 9.12: Figure 9.8 shows a decision network that represents the scenario of Example 9.10. The symptoms depend on the disease. What test to perform is decided based on the symptoms. The test result depends on the disease and the test performed. The treatment decision is based on the symptoms, the test performed, and the test result. The outcome depends on the disease and the treatment. The utility depends on the costs and the side effects of the test and on the outcome.

Note that the diagnostic assistant that is deciding on the tests and the treatments never actually finds out what disease the patient has, unless the test result is definitive, which it typically is not.

figures/ch09/fireidnew.png
Figure 9.9: Decision network for the alarm problem
Example 9.13: Figure 9.9 gives a decision network that is an extension of the belief network of Figure 6.1. The agent can receive a report of people leaving a building and has to decide whether or not to call the fire department. Before calling, the agent can check for smoke, but this has some cost associated with it. The utility depends on whether it calls, whether there is a fire, and the cost associated with checking for smoke.

In this sequential decision problem, there are two decisions to be made. First, the agent must decide whether to check for smoke. The information that will be available when it makes this decision is whether there is a report of people leaving the building. Second, the agent must decide whether or not to call the fire department. When making this decision, the agent will know whether there was a report, whether it checked for smoke, and whether it can see smoke. Assume that all of the variables are binary.

The information necessary for the decision network includes the conditional probabilities of the belief network and

  • P(SeeSmoke|Smoke,CheckSmoke); how seeing smoke depends on whether the agent looks for smoke and whether there is smoke. Assume that the agent has a perfect sensor for smoke. It will see smoke if and only if it looks for smoke and there is smoke. [See Exercise 9.6.]
  • Utility(CheckSmoke,Fire,Call); how the utility depends on whether the agent checks for smoke, whether there is a fire, and whether the fire department is called. Figure 9.10 provides this utility information.
    CheckSmoke Fire Call Utility
    yes yes call -220
    yes yes do not call -5020
    yes no call -220
    yes no do not call -20
    no yes call -200
    no yes do not call -5000
    no no call -200
    no no do not call 0
    Figure 9.10: Utility for alarm decision network

    This utility function expresses the cost structure that calling has a cost of 200, checking has a cost of 20, but not calling when there is a fire has a cost of 5,000. The utility is the negative of the cost.