9 Planning Under Uncertainty

In the quote above, Tharp is referring to dance, but the same idea holds for any agent when there is uncertainty. An agent cannot just plan a sequence of steps; the result of planning needs to be more sophisticated. Planning must take into account the fact that the agent does not know what will actually happen when it acts. The agent should plan to react to its environment. What it does is determined by the plan and the actual environment encountered.

Consider what an agent should do when it does not know the exact effects of its actions. Determining what to do is difficult because what an agent should do at any time depends on what it will do in the future. However, what it will do in the future depends on what it does now and what it will observe in the future.

With uncertainty, an agent typically cannot guarantee to satisfy its goals, and even trying to maximize the probability of achieving a goal may not be sensible. For example, an agent whose goal is not to be injured in a car accident would not get in a car or travel down a sidewalk or even go to the ground floor of a building, which most people would agree is not very intelligent. An agent that does not guarantee to satisfy a goal can fail in many ways, some of which may be much worse than others.

This chapter is about how to take these issues into account simultaneously.

Any computer program or person who acts or gives advice is using some value system of what is important and what is not.

Lewis Carroll (1832-1898)
Alice's Adventures in Wonderland, 1865

We all, of course, want computers to work on our value system, but they cannot act according to everyone's value system! When you build programs to work in a laboratory, this is not usually a problem. The program acts according to the goals and values of the program's designer, who is also the program's user. When there are multiple users of a system, you must be aware of whose value system is incorporated into a program. If a company sells a medical diagnostic program to a doctor, does the advice the program gives reflect the values of society, the company, the doctor, or the patient (all of whom may have very different value systems)? Does it determine the doctor's or the patient's values?

If you want to build a system that gives advice to someone, you should find out what is true as well as what their values are. For example, in a medical diagnostic system, the appropriate procedure depends not only on patients' symptoms but also on their priorities. Are they prepared to put up with some pain in order to be more aware of their surroundings? Are they willing to put up with a lot of discomfort to live a bit longer? What risks are they prepared to take? Always be suspicious of a program or person that tells you what to do if it does not ask you what you want to do! As builders of programs that do things or give advice, you should be aware of whose value systems are incorporated into the actions or advice.

An agent's decision on what to do depends on three things:

• the agent's ability. The agent has to select from the options available to it.
• what the agent believes. You may be tempted to say "what is true in the world," but when an agent does not know what is true in the world, it can act based only on its beliefs. Sensing the world updates an agent's beliefs by conditioning on what is sensed.
• the agent's preferences. When an agent must reason under uncertainty, it has to consider not only what will most likely happen but also what may happen. Some possible outcomes may have much worse consequences than others. The notion of a "goal" here is richer than the goals considered in Chapter 8 because the designer of an agent must specify trade-offs between different outcomes. For example, if some action results in a good outcome most of the time, but sometimes results in a disastrous outcome, it must be compared with performing an alternative action that results in the good outcome less often and the disastrous outcome less often and some mediocre outcome most of the time. Decision theory specifies how to trade off the desirability of outcomes with the probabilities of these outcomes.

• 9.1 Preferences and Utility
  • 9.1.1 Factored Utility
• 9.2 One-Off Decisions
  • 9.2.1 Single-Stage Decision Networks
• 9.3 Sequential Decisions
  • 9.3.1 Decision Networks
  • 9.3.2 Policies
  • 9.3.3 Variable Elimination for Decision Networks
• 9.4 The Value of Information and Control
• 9.5 Decision Processes
  • 9.5.1 Value of a Policy
  • 9.5.2 Value of an Optimal Policy
  • 9.5.3 Value Iteration
  • 9.5.4 Policy Iteration
  • 9.5.5 Dynamic Decision Networks
  • 9.5.6 Partially Observable Decision Processes
• 9.6 Review
• 9.7 References and Further Reading
• 9.8 Exercises