Planning, Utility and Decision-Making

Introduction

Artificial intelligence systems rarely act successfully by reacting to isolated observations. They must represent possible situations, formulate objectives, select actions, anticipate consequences, and revise decisions when information is incomplete. Planning and decision-making provide the conceptual bridge between perception and intelligent action.

A planning system searches for a sequence of actions that transforms an initial state into a desired goal state. A decision-making system goes further: it compares alternatives according to preferences, costs, risks, and uncertainty. These ideas support route finding, logistics, robotics, game playing, recommendation, medical decision support, autonomous vehicles, and resource allocation.

This chapter develops state-space search, automated planning, scheduling, utility theory, decision trees, Markov decision processes (MDPs), and sequential decisions under uncertainty. It also examines practical limitations, ethical concerns, and the relationship between classical symbolic methods and contemporary AI.

Learning Objectives

By the end of this chapter, you should be able to:

1. Represent problems using states, actions, transition models, goals, and costs.

2. Explain forward and backward planning and compare common planning strategies.

3. Distinguish planning from scheduling and formulate scheduling constraints.

4. Apply utility theory and expected utility to uncertain choices.

5. Construct and evaluate decision trees.

6. Define MDPs and explain policies, value functions, and Bellman equations.

7. Analyze sequential decisions when outcomes are uncertain.

8. Identify limitations, ethical risks, and appropriate professional uses of planning systems.

1. State-Space Representation

A state is a description of the aspects of the world relevant to an agent’s decision. A state-space problem is commonly specified as

\[

P=(S,A,T,s_0,G,C),

\]

where \(S\) is the set of states, \(A\) the available actions, \(T(s,a)\) the transition model, \(s_0\) the initial state, \(G\subseteq S\) the goal states, and \(C\) a cost function. In a deterministic problem, an action maps a state to one successor state. In a stochastic problem, the transition model is a probability distribution \(P(s'\mid s,a)\).

A solution is a path or policy, depending on the problem. A path is a finite sequence of actions leading from \(s_0\) to a goal. Its path cost is often

\[

C(\pi)=\sum_{t=0}^{n-1}c(s_t,a_t,s_{t+1}),

\]

where \(\pi\) is the action sequence and costs are assumed additive. The objective may be to reach any goal, minimize cost, minimize time, maximize reliability, or optimize a weighted combination.

Example: delivery robot

A robot in a warehouse can be represented by its location, load status, and whether each required package has been collected. An action such as “move from aisle A to aisle B” changes location and incurs a distance cost. “Pick up package P” changes the load status and may require the robot to be at P’s location. The goal is a state in which all packages have been delivered.

The quality of a representation matters. If it omits battery level, a plan may appear feasible while the robot actually runs out of power. If it includes irrelevant details, the state space becomes unnecessarily large.

2. Search and Automated Planning

Automated planning is the computational construction of action sequences or policies that achieve specified objectives. Classical planning usually assumes:

• a fully known initial state;
• deterministic actions;
• discrete states and actions;
• predictable action effects; and
• goals expressed as conditions on states.

These assumptions are useful but restrictive.

2.1 Forward and backward planning

Forward (progression) planning starts at the initial state and applies applicable actions until a goal is reached. It is intuitive and can discover many possible plans, but it may explore actions unrelated to the goal.

Backward (regression) planning starts with the goal conditions and asks which actions could achieve them. It then replaces achieved conditions with the actions’ preconditions. Regression can focus search on goal-relevant actions, although it may be difficult when goals interact or actions have complex effects.

2.2 Search strategies

Breadth-first search expands the shallowest nodes first and is complete for finite branching spaces. It is optimal when every action has the same positive cost. Uniform-cost search expands the lowest accumulated-cost node and is optimal when action costs are nonnegative.

Depth-first search uses little memory but is not generally optimal and may follow an unproductive branch. Greedy best-first search uses a heuristic estimate \(h(n)\) of remaining cost. A* evaluates

\[

f(n)=g(n)+h(n),

\]

where \(g(n)\) is cost from the start and \(h(n)\) estimates cost to a goal. A heuristic is admissible if it never overestimates the true remaining cost. For tree search with nonnegative costs, admissibility is sufficient for A* optimality. For graph search, the usual closed-list implementation additionally requires a consistent (monotone) heuristic, or it must reopen a previously expanded node when a cheaper path is found. Consistency means

\[

h(n)\leq c(n,n')+h(n')

\]

for every applicable edge and, typically, \(h(goal)=0\).

A heuristic can be derived from a relaxed problem. For example, a route-planning heuristic may use straight-line distance when roads impose additional constraints; straight-line distance cannot exceed the shortest road distance under ordinary metric assumptions, so it is admissible.

2.3 STRIPS-style action representation

A symbolic action can be described by:

• preconditions: facts that must hold;
• add effects: facts made true; and
• delete effects: facts made false.

For example, `Move(robot, A, B)` may require `At(robot,A)` and `Connected(A,B)`, add `At(robot,B)`, and delete `At(robot,A)`. This representation supports logical planning but requires careful handling of time, resources, concurrency, and incomplete knowledge.

2.4 Planning graphs and hierarchical planning

Planning graphs alternate proposition and action levels. They record which actions are reachable and identify mutual exclusions (mutexes), such as actions that require contradictory conditions. They can provide useful admissible estimates for search.

Hierarchical task-network planning decomposes a high-level task into subtasks. “Organize a conference” might decompose into booking a venue, inviting speakers, and arranging catering. Hierarchical methods can exploit domain expertise and produce understandable plans, but they depend on accurate decomposition knowledge.

3. Planning, Scheduling, and Execution

Planning answers “what should be done?” Scheduling answers “when should it be done, with which resources, and in what order?” A plan may specify that a machine must process a component and then inspect it; a schedule assigns start times while respecting machine capacity and deadlines.

A scheduling problem typically contains:

• activities with durations;
• precedence constraints;
• renewable resources such as staff or machines;
• nonrenewable resources such as budget or material;
• release times and deadlines; and
• an objective such as minimizing completion time or lateness.

If activity A must finish before B starts, then

\[

start(B)\geq finish(A)=start(A)+duration(A).

\]

For a single machine, two activities A and B cannot overlap:

\[

finish(A)\leq start(B)\quad\text{or}\quad finish(B)\leq start(A).

\]

The critical path is the longest-duration path through precedence constraints. In a project with activities A (3 days), B (4 days after A), and C (2 days after A), followed by D (2 days after both B and C), the paths have lengths A-B-D = 3+4+2=9 days and A-C-D = 3+2+2=7 days. The minimum project duration under unlimited resources is therefore 9 days, and B lies on the critical path. Resource limits may increase this duration.

Planning and scheduling are often interleaved. A schedule may reveal that a plan requires two actions simultaneously on one machine, forcing replanning. In real systems, execution monitoring detects deviations and triggers replanning rather than assuming that an original plan remains valid.

4. Utility Theory and Rational Choice

Goals alone do not determine a decision when alternatives have different benefits and risks. Utility theory represents an agent’s preferences numerically. A utility function \(U(x)\) assigns a value to outcome \(x\), with higher values preferred. Utility is not necessarily money; it may combine safety, comfort, fairness, time, and quality.

If outcomes are uncertain, the expected utility of action \(a\) is

\[

EU(a)=\sum_i P(o_i\mid a)U(o_i),

\]

for mutually exclusive and exhaustive outcomes \(o_i\). The principle of maximum expected utility selects an action with greatest expected utility, assuming the probabilities and utilities adequately represent the decision maker’s beliefs and preferences.

Worked example

Suppose a maintenance manager chooses between two policies:

• Preventive maintenance costs 20 utility units for certain.
• Delayed maintenance costs 0 if equipment remains reliable, with probability 0.75, but costs 80 if failure occurs, with probability 0.25.

Taking cost as negative utility,

\[

EU(Preventive)=-20,

\]

and

\[

EU(Delayed)=0.75(0)+0.25(-80)=-20.

\]

The manager is indifferent under these simplified assumptions. A preference for reliability, indirect downtime, or safety would alter the utilities and could make preventive maintenance preferable. This example illustrates why probability alone is insufficient: consequences must also be valued.

Risk attitudes

A risk-neutral decision maker evaluates expected monetary value directly. A risk-averse decision maker prefers a certain outcome to a fair gamble and is represented by a concave utility function over wealth. A risk-seeking decision maker may have a convex utility function in a relevant range. The expected value of money and expected utility are therefore different concepts.

Utility models should be elicited transparently. Hidden weights can encode organizational bias, and a system that maximizes a proxy may sacrifice the underlying objective. Multi-criteria decisions often use a weighted score such as

\[

U(x)=\sum_{k=1}^{m}w_k u_k(x),

\]

where normalized component utilities \(u_k\) and weights \(w_k\) reflect criteria and priorities. This additive form is appropriate only when trade-offs and preference independence assumptions are defensible.

5. Decision Trees and Value of Information

A decision tree represents choices and uncertain events. Decision nodes are usually squares, chance nodes circles, and terminal nodes outcomes. Evaluation proceeds from the leaves backward:

1. At a chance node, calculate the probability-weighted value of its branches.

2. At a decision node, select the branch with the greatest value.

Example

A company may launch a product. Launching yields a profit of 100 (utility units) if demand is high, probability 0.6, and a loss of 40 if demand is low, probability 0.4. Not launching yields 0. The expected utility of launching is

\[

0.6(100)+0.4(-40)=60-16=44.

\]

Since 44 exceeds 0, launch is preferred under the stated model. This conclusion changes if probabilities, utilities, or additional costs change.

Information can have economic value. The expected value of perfect information (EVPI) is

\[

EVPI=EU(\text{best action after knowing state})-EU(\text{best action before knowing state}).

\]

The value of imperfect information is no greater than EVPI. In practice, a market survey, diagnostic test, or sensor may be worthwhile only if its expected benefit exceeds its acquisition and delay costs.

Decision trees become unwieldy with many sequential decisions. They also rely on calibrated probabilities and well-defined utilities. Correlated events, changing information, and strategic behavior may require richer models.

6. Markov Decision Processes

An MDP models sequential decision-making under stochastic outcomes. A finite MDP is commonly defined as

\[

(S,A,P,R,\gamma),

\]

where \(S\) is the state set, \(A\) the action set, \(P(s'\mid s,a)\) the transition probability, \(R(s,a,s')\) the reward, and \(\gamma\in[0,1)\) a discount factor for continuing tasks. The Markov property states that, given the current state and action, the future is conditionally independent of the earlier history:

\[

P(s_{t+1}\mid s_t,a_t,s_{t-1},a_{t-1},\ldots)=P(s_{t+1}\mid s_t,a_t).

\]

A policy \(\pi(a\mid s)\) specifies action probabilities; a deterministic policy chooses one action for each state. The value of a policy is

\[

V^\pi(s)=\mathbb{E}_\pi\left[\sum_{t=0}^{\infty}\gamma^t R_{t}\mid s_0=s\right].

\]

Discounting ensures convergence for bounded rewards when \(\gamma<1\), and it represents preference for earlier rewards. In episodic tasks, an undiscounted formulation can be used when termination is guaranteed and expected returns are finite.

The Bellman expectation equation is

\[

V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a)[R(s,a,s')+\gamma V^\pi(s')].

\]

The optimal value satisfies the Bellman optimality equation:

\[

V^(s)=\max_a\sum_{s'}P(s'\mid s,a)[R(s,a,s')+\gamma V^(s')].

\]

An optimal policy selects an action attaining the maximum. Value iteration repeatedly applies the optimality backup until values stabilize within a chosen tolerance. Policy iteration alternates policy evaluation and policy improvement. For large or continuous state spaces, approximate dynamic programming, reinforcement learning, simulation, and function approximation are used.

Small MDP illustration

A cleaning robot has states `Clean` and `Dirty`. In `Dirty`, `Clean` gives reward 5 and leads to `Clean` with probability 1; `Wait` gives reward 0 and remains `Dirty`. If the robot is already `Clean`, waiting gives reward 1 and remains `Clean`, while cleaning gives reward 0. With discount \(\gamma=0.9\), the value of always waiting in `Clean` is

\[

1+0.9+0.9^2+\cdots=\frac{1}{1-0.9}=10.

\]

If cleaning in `Dirty` is certain and then the robot waits forever, the value of cleaning now is \(5+0.9(10)=14\). Thus cleaning is attractive in the dirty state under this reward model. The model does not claim that cleaning is always optimal in reality; it depends on transition probabilities, costs, and reward design.

7. Sequential Decisions Under Uncertainty

A sequential decision problem differs from a one-step choice because current actions affect future states, information, and opportunities. An agent must balance immediate reward against long-term consequences. A greedy policy that chooses the largest immediate reward can be inferior to an action with lower immediate reward but better future prospects.

Uncertainty has several sources:

• aleatory uncertainty: inherent randomness in outcomes;
• epistemic uncertainty: incomplete knowledge of the environment;
• model uncertainty: uncertainty about whether the transition or reward model is correct; and
• observation uncertainty: noisy or partial sensing.

An MDP assumes the state is fully observed. A partially observable MDP (POMDP) introduces observations and a belief state, which is a probability distribution over possible physical states. The belief state can serve as the information state for decision-making, but its continuous, high-dimensional nature makes exact solution difficult.

When the model is unknown, reinforcement learning estimates values or policies through interaction. Model-free methods learn action values directly; model-based methods learn or use a transition model and plan with it. Exploration creates a trade-off: the agent may select an action to gain information even when its immediate reward is lower. Poorly controlled exploration can cause safety or financial harm, so real deployments often use simulators, constraints, human approval, and conservative uncertainty handling.

8. Case Study: Hospital Equipment Allocation

Background

The following is an illustrative case. A hospital must allocate a limited number of portable monitoring devices among wards. Demand changes over time, equipment can fail, and emergency cases may arrive unexpectedly.

Problem

A simple rule assigning devices to the ward with the largest current queue may produce unfair or unsafe outcomes. It ignores expected emergency demand, travel time, device reliability, and the consequences of leaving a critical-care patient unserved.

Analysis

The state can include available devices, ward queues, battery levels, and equipment condition. Actions include assigning, relocating, charging, or repairing devices. A transition model represents arrivals, discharges, failures, and repair times. Rewards can combine treated patients, response time, safety, and fairness penalties. Because the hospital observes only estimates of future arrivals, uncertainty is material.

A planning layer can create feasible assignments and maintenance schedules. A scheduling layer ensures that one device is not assigned simultaneously to two wards and that charging precedes deployment. An MDP can represent sequential relocation and repair decisions. A utility or constrained optimization layer can give safety a minimum threshold rather than treating it as merely another easily traded score.

Approach and safeguards

The hospital could begin with a transparent baseline: reserve a fixed emergency capacity, prioritize clinically urgent cases, and use optimization for the remaining devices. Historical data can estimate arrivals and failures, but estimates should be calibrated and regularly audited. A human supervisor should approve unusual reallocations. The system should log its state, recommendations, assumptions, and reasons for auditability.

Outcome and learning points

In an evaluation, performance should be measured not only by average utilization but also by worst-case response time, missed urgent demand, ward-level fairness, robustness to demand shifts, and frequency of human overrides. The central lesson is that a mathematically optimal policy under an incomplete reward model may be operationally unacceptable. Safety constraints, governance, and stakeholder participation are part of the decision system, not optional additions.

9. Limitations, Ethics, and Best Practices

Planning systems suffer from state-space explosion: the number of possible states can grow exponentially with variables. Approximate heuristics, abstraction, decomposition, hierarchical methods, and sampling reduce computation but may sacrifice optimality or completeness.

Models can be wrong. Transition probabilities estimated from historical data may fail under unusual conditions. Reward functions can encode discrimination or encourage harmful shortcuts. A system may optimize average performance while systematically disadvantaging a minority group. In safety-critical applications, constraints should be explicit, and unsafe actions should be excluded rather than merely assigned a large negative reward.

Important governance practices include:

• document states, actions, assumptions, data sources, and objectives;
• test calibration and sensitivity to probabilities and utilities;
• evaluate subgroup and worst-case performance;
• maintain human oversight proportional to risk;
• log decisions and enable post-deployment audit;
• protect personal and operational data;
• monitor distribution shift and model degradation; and
• provide appeal, correction, and incident-response mechanisms.

Contemporary systems increasingly combine symbolic planning with learned models. A language model may propose actions, while a planner verifies preconditions and a controller enforces safety constraints. This division is valuable because fluent generation does not guarantee feasible, optimal, or safe behavior. Digital twins, simulation-based planning, probabilistic programming, offline reinforcement learning, and constrained reinforcement learning are active areas of development.

Chapter Summary

State-space representation formalizes intelligent action through states, actions, transitions, goals, and costs. Search algorithms construct paths, while automated planning uses structured action representations to achieve goals. A* combines path cost and heuristic estimates; admissibility guarantees optimality in tree search, while graph search requires consistency or node reopening under standard implementations.

Planning determines actions, whereas scheduling assigns times and resources under precedence and capacity constraints. Utility theory allows alternatives to be compared when outcomes have different benefits, costs, and risks. Expected utility, decision trees, and value-of-information analysis support one-step and sequential choices.

MDPs model repeated decisions using states, actions, transition probabilities, rewards, and discounting. Policies and Bellman equations express long-term value. Partial observability, model uncertainty, and exploration make real-world decisions more difficult. Effective systems therefore combine algorithms with valid representations, calibrated models, explicit safety constraints, human governance, and continuous evaluation.

Key Terms

State: A representation of relevant conditions in the environment.

Action: An operation available to an agent.

Transition model: A model describing how actions change states.

Goal state: A state satisfying the desired objective conditions.

Path cost: The accumulated cost of actions along a path.

Heuristic: An estimate of the remaining cost to a goal.

Admissible heuristic: A heuristic that never overestimates true remaining cost.

Consistent heuristic: A heuristic satisfying the triangle-like monotonicity condition.

Automated planning: Computational construction of actions to achieve goals.

Scheduling: Assigning activities to times and resources under constraints.

Critical path: The longest precedence-constrained path determining minimum project duration.

Utility: Numerical representation of preference for an outcome.

Expected utility: Probability-weighted utility of possible outcomes.

Decision tree: A branching representation of decisions and uncertain events.

Value of information: The improvement in expected decision value from obtaining information.

Markov decision process: A sequential stochastic decision model satisfying the Markov property.

Policy: A rule mapping states or beliefs to actions.

Value function: Expected cumulative future reward from a state under a policy.

Partial observability: A condition in which the true state cannot be directly observed.

Reward shaping: Modification of rewards to influence learning or behavior, with possible unintended effects.

Review Questions

Short Answer Questions

1. What are the principal components of a state-space planning problem?

2. Distinguish forward planning from backward planning.

3. Why does scheduling require more information than a basic plan?

4. Define expected utility and explain its purpose.

5. State the Markov property in an MDP.

Long Answer Questions

1. Compare breadth-first, uniform-cost, greedy best-first, and A* search in terms of completeness, optimality, and information requirements.

2. Explain why admissibility alone is sufficient for A* tree search but not generally sufficient for standard graph search without consistency or node reopening.

3. Derive and interpret the Bellman optimality equation for a discounted MDP.

4. Discuss how utility functions, probabilities, and risk attitudes influence decisions under uncertainty.

5. Explain the relationship between planning, scheduling, execution monitoring, and replanning in a real AI system.

Analytical / Application Questions

1. A project contains activities A=4 hours, B=3 hours after A, C=5 hours after A, and D=2 hours after both B and C. Identify the critical path and minimum duration assuming unlimited resources.

2. An investment returns 70 utility units with probability 0.4 and −20 utility units with probability 0.6, while rejecting it returns 0. Which action maximizes expected utility? Show the calculation.

3. Design an MDP for an autonomous delivery robot. Specify states, actions, transition uncertainty, rewards, and one safety constraint. Explain one limitation of your model.

Multiple Choice Questions with Answers

Question 1

Which condition defines an admissible heuristic?

A. It always overestimates the remaining cost.

B. It never overestimates the true remaining cost.

C. It assigns the same value to every state.

D. It ignores the accumulated path cost.

Correct Answer: B. It never overestimates the true remaining cost.

Question 2

For standard A* tree search with nonnegative costs, which property is sufficient for optimality?

A. Admissibility of the heuristic

B. A heuristic that always overestimates

C. Random tie-breaking only

D. Depth-first expansion

Correct Answer: A. Admissibility of the heuristic

Question 3

What is the critical-path duration for activities A=3 days, B=4 days after A, C=2 days after A, and D=2 days after both B and C?

A. 7 days

B. 8 days

C. 9 days

D. 11 days

Correct Answer: C. 9 days

Question 4

A policy costs 20 utility units for certain. Another costs 0 with probability 0.75 and 80 with probability 0.25. Using negative cost as utility, what is the second policy’s expected utility?

A. −80

B. −35

C. −20

D. 20

Correct Answer: C. −20

Question 5

Which expression is the expected utility of an action with outcomes oi?

A. The largest outcome only

B. The sum of probabilities without utilities

C. The probability-weighted sum of outcome utilities

D. The utility of the most probable outcome

Correct Answer: C. The probability-weighted sum of outcome utilities

Question 6

In an MDP, what does the transition probability P(s'|s,a) represent?

A. The reward of action a

B. The probability of reaching s' after taking a in s

C. The probability of choosing state s

D. The discount factor

Correct Answer: B. The probability of reaching s' after taking a in s

Question 7

For a discounted MDP with gamma=0.9 and a reward of 1 at every time step forever, what is the return from the initial state?

A. 0.9

B. 1

C. 9

D. 10

Correct Answer: D. 10

Question 8

What is evaluated at a chance node in a decision tree?

A. The maximum branch value regardless of probabilities

B. The probability-weighted value of its branches

C. The minimum branch value

D. Only the first branch

Correct Answer: B. The probability-weighted value of its branches

Question 9

Which statement best describes scheduling?

A. It assigns times and resources subject to constraints.

B. It eliminates all uncertainty from an environment.

C. It is identical to defining a goal.

D. It only applies to games.

Correct Answer: A. It assigns times and resources subject to constraints.

Question 10

What is the defining assumption of the Markov property?

A. Rewards must always be positive.

B. The future depends on the entire history equally.

C. Given the current state and action, history adds no information about the next state.

D. Every action has a deterministic outcome.

Correct Answer: C. Given the current state and action, history adds no information about the next state.