4. Search, Optimization, Planning and Game Playing

Introduction and Context

Artificial intelligence often addresses problems for which no direct formula produces the answer. An intelligent system must consider alternatives, evaluate partial possibilities, manage limited resources, and select actions that lead toward a desirable outcome. Search provides the general mechanism for exploring alternatives. Optimization provides methods for improving a solution according to an objective. Planning determines a sequence of actions that transforms an initial situation into a goal situation. Game playing extends search to environments in which another agent actively attempts to prevent success.

These ideas are closely related to practical problems. A delivery company searches for efficient routes, a hospital allocates operating rooms, a cloud platform schedules workloads, a robot plans movements, and a cybersecurity system chooses defensive responses. In each case, the system operates over a state space, applies actions or transformations, evaluates alternatives, and must often make decisions under computational or information constraints.

The central difficulty is combinatorial growth. If a problem has ten possible actions at each of ten levels, a naïve search may examine up to 10 billion action sequences. AI therefore relies on representations, pruning, heuristics, decomposition, approximation, and domain knowledge. This chapter develops these methods and explains how their theoretical properties influence professional decision-making.

Learning Objectives

After studying this chapter, students should be able to:

1. Model a problem using states, actions, transition models, goals, and path costs.

2. Explain and compare uninformed search algorithms, including breadth-first, depth-first, uniform-cost, and iterative-deepening search.

3. Use heuristic search, especially greedy best-first search and A*, and assess admissibility, consistency, completeness, and optimality.

4. Formulate constraint satisfaction, optimization, and scheduling problems.

5. Distinguish local search, evolutionary methods, and exact optimization approaches.

6. Explain planning representations and basic planning algorithms.

7. Apply minimax and alpha-beta pruning to adversarial decision problems.

8. Evaluate the practical, ethical, and organizational consequences of automated search and decision systems.

1. Problem Formulation: Searching Through a State Space

A search problem is normally specified by five elements:

• Initial state: the situation from which the system begins.
• Actions: legal operations available in a state.
• Transition model: a description of the state produced by an action.
• Goal test: a procedure for determining whether a state satisfies the objective.
• Path-cost function: a numerical measure of the cost of an action sequence.

A solution is a sequence of actions leading from the initial state to a goal. The quality of a solution depends on the path-cost function. For route planning, cost may be travel time, distance, fuel, tolls, or a weighted combination. In manufacturing, it may combine lateness, setup cost, energy use, and overtime.

The state space is the set of reachable states. A search tree records paths to states, whereas a search graph identifies states that may be reached through multiple paths. This distinction matters because repeated-state detection can prevent substantial redundant work. A search algorithm maintains a frontier, containing generated but unexpanded nodes, and often an explored set containing states already examined.

Important measures include branching factor, solution depth, maximum search depth, time complexity, space complexity, completeness, and optimality. An algorithm is complete if it finds a solution whenever one exists. It is optimal if it returns the least-cost solution under the stated cost model. These properties are not interchangeable: a method may be fast but non-optimal, or optimal but impractical because it consumes excessive memory.

2. Uninformed Search

Uninformed, or blind, search uses no problem-specific estimate of distance to the goal. It relies only on the formal problem definition.

Breadth-First Search

Breadth-first search (BFS) expands the shallowest unexpanded node first, usually by maintaining the frontier as a queue. It is complete when the branching factor is finite. If every action has identical cost, BFS is optimal because the first shallowest solution also has the fewest actions. However, its memory requirement is substantial because it stores an entire layer of the tree. In a large routing or scheduling space, this can make BFS unusable.

Depth-First Search

Depth-first search (DFS) expands the deepest available node first, using a stack or recursion. It has low memory requirements, but it is not generally complete in infinite-depth spaces or spaces containing cycles. It is also not optimal. A practical implementation must use cycle checking or a depth limit. DFS is useful when solutions are expected to be deep and memory is severely constrained, but it can spend considerable time pursuing an unproductive branch.

Uniform-Cost Search

Uniform-cost search expands the node with the lowest accumulated path cost, commonly denoted g(n). It is equivalent to Dijkstra's algorithm when applied to a graph with non-negative edge costs. Uniform-cost search is complete and optimal when every action cost is positive or satisfies suitable non-negative assumptions. Unlike BFS, it handles unequal costs correctly. Its weakness is that it has no indication of geographical or semantic closeness to the goal and may explore many inexpensive but irrelevant paths.

Iterative Deepening

Iterative-deepening depth-first search repeatedly performs depth-limited DFS with limits 0, 1, 2, and so forth. It combines the low memory usage of DFS with the completeness and, for unit costs, optimality of BFS. Re-expansion creates overhead, but when the branching factor is high and the solution depth is unknown, iterative deepening is often a strong general-purpose choice.

3. Heuristic Search and A*

A heuristic function, h(n), estimates the remaining cost from node n to a goal. Good heuristics direct search toward promising regions and reduce unnecessary expansion. A heuristic need not be perfect; it must be computationally useful and sufficiently reliable for the desired guarantee.

Greedy best-first search selects the node with the smallest h(n). It can be fast when the heuristic is informative, but it may follow an attractive-looking route that is ultimately expensive and may fail to be optimal or complete in unrestricted spaces.

A* combines the cost already incurred with the estimated remaining cost:

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

where g(n) is the cost from the initial state to n. A expands the node with the lowest f-value. If h(n) is admissible, it never overestimates the true remaining cost, and edge costs are non-negative, tree-search A is optimal. For graph search, the stronger condition of consistency is especially useful. A heuristic is consistent when, for every edge from n to n', h(n) is no greater than the step cost plus h(n'). Consistency implies admissibility and ensures that once a node is removed from the frontier, its best path has been found under standard conditions.

A is complete under suitable finite-branching and positive-cost assumptions, but its memory requirement can be its principal limitation. Practical systems therefore use memory-bounded variants such as iterative-deepening A (IDA), simplified memory-bounded A, or weighted A. Weighted A uses f(n)=g(n)+w h(n), with w greater than 1, to obtain faster but potentially non-optimal solutions. This illustrates an important engineering principle: guarantees can be deliberately traded for speed when the operational cost of exactness is high.

Heuristic design is a form of knowledge engineering. A heuristic may be derived from a relaxed problem, in which some constraints are removed. The optimal cost of the relaxed problem cannot exceed the cost of the original problem and therefore provides an admissible estimate. For example, straight-line distance is a useful lower bound for road travel when roads cannot be shorter than the corresponding direct distance. Multiple admissible heuristics can sometimes be combined by taking their maximum, preserving admissibility while increasing informativeness.

4. Constraint Satisfaction and Structured Search

A constraint satisfaction problem (CSP) consists of variables, domains of possible values, and constraints restricting combinations of values. Map colouring, examination timetabling, employee rostering, Sudoku, and resource allocation can all be represented as CSPs.

A solution is a complete assignment satisfying every constraint. Backtracking search assigns values incrementally and returns to an earlier variable when a conflict occurs. Its performance improves greatly through problem-specific ordering and propagation strategies:

• Minimum remaining values (MRV): choose the variable with the smallest legal domain.
• Degree heuristic: when tied, select the variable constraining the largest number of unassigned variables.
• Least-constraining value: try the value that leaves the greatest flexibility for future assignments.
• Forward checking: after an assignment, remove inconsistent values from neighbouring domains.
• Arc consistency: repeatedly remove a value when no compatible value remains in a connected variable's domain.

CSP methods demonstrate that representation can be more important than raw computational power. A scheduling problem represented merely as a list of permutations may be difficult, whereas explicit variables, domains, precedence constraints, and resource constraints expose opportunities for propagation.

5. Optimization Beyond Complete Search

Optimization seeks the best feasible solution according to an objective function. Problems may be discrete or continuous, single-objective or multi-objective, deterministic or stochastic. A feasible solution satisfies all constraints; an optimal solution has the best objective value among feasible solutions.

Local Search

Local search begins with a candidate solution and repeatedly moves to a neighbouring candidate. It stores little or no search tree and is therefore suitable for large optimization spaces where a complete path is not required. In a routing problem, a neighbour might be produced by swapping two visits or reversing a segment.

Hill climbing selects an improving neighbour. It can become trapped at a local optimum, plateau, or ridge. Random-restart hill climbing reduces dependence on the initial state. Simulated annealing occasionally accepts a worse move, with a probability that decreases as a temperature parameter is reduced. This allows early exploration and later exploitation. Tabu search records recently visited moves or solutions in a tabu list, discouraging cycling while permitting carefully controlled exceptions.

Evolutionary Optimization

Evolutionary algorithms maintain a population of candidate solutions. Each candidate is evaluated by a fitness function. Selection favours stronger candidates, while crossover combines parts of candidates and mutation introduces variation. Repeated generations can discover high-quality solutions without requiring differentiability or a single smooth objective landscape.

Their effectiveness depends on representation, fitness design, population diversity, selection pressure, and termination conditions. Premature convergence occurs when the population becomes too similar. Poorly designed fitness functions can produce solutions that score well numerically but violate the real intention of the organization. Evolutionary methods are particularly useful for complex scheduling, layout, routing, and design problems, but they generally provide no simple certificate of global optimality.

Exact, Approximate, and Multi-objective Methods

Linear programming, integer programming, dynamic programming, branch-and-bound, and constraint programming can provide exact solutions or bounds for many structured problems. Branch-and-bound systematically divides the solution space and uses upper or lower bounds to eliminate branches that cannot improve the incumbent solution.

When objectives conflict, such as cost, speed, fairness, and emissions, there may be no single best solution. A solution is Pareto-optimal if no objective can be improved without worsening at least one other objective. Decision-makers may select a preferred point from the Pareto frontier after considering organizational priorities and stakeholder values.

6. Planning as Deliberate Action Selection

Search usually describes movement through a state space; planning emphasizes the construction of an action strategy. A classical planning problem represents the world using predicates, actions with preconditions, and effects. For example, an action Deliver(package, location) may require that the package is loaded and the vehicle is at the location, and may make the predicate Delivered(package) true.

A plan is a sequence or partially ordered set of actions that achieves the goal. Forward-state-space planning starts at the initial state and applies applicable actions. Backward planning starts from the goal and identifies actions capable of achieving it, then establishes their preconditions. Backward reasoning can reduce irrelevant exploration when the goal is specific.

The STRIPS representation uses positive and negative conditions and action effects. More expressive languages support conditional effects, numeric resources, time, uncertainty, and concurrent actions. Planning graphs organize possible actions and propositions by levels and use mutex relations to identify incompatible choices. Partial-order planning delays decisions that do not yet need to be made, preserving flexibility.

Real-world planning differs from idealized classical planning because actions may be uncertain, observations may be incomplete, and the environment may change. Replanning, online planning, probabilistic planning, and hierarchical task networks address these limitations. A hierarchical planner decomposes a high-level task such as “fulfil an order” into subtasks such as allocate inventory, schedule picking, select transport, and confirm delivery.

7. Adversarial Search and Game Playing

In a single-agent problem, the system evaluates states according to its own objective. In an adversarial environment, another agent chooses actions that may reduce that value. A game model includes states, legal moves, terminal tests, and utility values. Turn-taking, perfect information, deterministic transitions, and zero-sum utilities define the simplest setting.

Minimax

The minimax algorithm assumes that MAX chooses actions to maximize utility while MIN chooses actions to minimize it. At terminal states, the utility is known. Values are propagated upward: MAX nodes take the maximum child value, and MIN nodes take the minimum. The selected move is optimal against a perfectly rational opponent if the complete game tree can be searched.

Most practical games have trees too large for exhaustive analysis. A depth-limited minimax search stops at a cutoff and applies an evaluation function. Such a function estimates positional strength using features such as material, mobility, safety, or strategic control. It must be calibrated carefully because search can exploit systematic weaknesses in the evaluation function.

Alpha-Beta Pruning

Alpha-beta pruning produces the same minimax decision while ignoring branches that cannot influence the final result. Alpha records the best value MAX can guarantee so far; beta records the best value MIN can guarantee. At a MAX node, a branch can be pruned when its value is at least beta. At a MIN node, pruning occurs when its value is at most alpha.

The effectiveness of alpha-beta depends strongly on move ordering. With excellent ordering, the effective search depth can be approximately doubled relative to plain minimax for the same computational budget. Iterative deepening, transposition tables, killer-move heuristics, and opening or endgame databases further improve performance. In games with chance, expectiminimax incorporates probabilistic outcomes; in games with imperfect information, a system must reason about beliefs rather than a fully observable state.

8. Applied Case: Hospital Operating-Room Scheduling

Background

Consider an illustrative case involving a regional hospital with several operating rooms, surgical teams, equipment constraints, emergency cases, and recovery-bed limits. The hospital must schedule procedures while minimizing delay and overtime and ensuring that required staff and equipment are available.

Situation and Problem

A simple first-come, first-served schedule creates idle periods when equipment is unavailable, causes overtime when long operations are placed late in the day, and may delay urgent patients. The problem is combinatorial because each operation has alternative rooms, surgeons, preparation times, durations, cleaning requirements, and precedence constraints.

Analysis

The problem can be modelled as a CSP or mixed-integer optimization problem. Variables represent the assigned room, start time, and surgical team. Domains contain feasible rooms and time intervals. Constraints express surgeon availability, room capacity, equipment compatibility, non-overlap, cleaning time, patient readiness, and emergency priority. The objective may combine weighted waiting time, cancellation risk, overtime, and fairness across clinical categories.

A complete search over all schedules is impractical. Constraint propagation can remove impossible assignments before search. MRV may select the operation with the fewest feasible room-time combinations. A branch-and-bound method can use a lower bound on unavoidable waiting and overtime to discard schedules that cannot beat the current best solution. For daily rescheduling, local search can adjust swaps and start times as cancellations or emergencies occur.

Approach and Solution

The hospital first defines hard constraints, which cannot be violated, and soft objectives, which can be traded off. A feasible initial schedule is generated using constraint programming. Improvement then uses local search to reduce overtime and waiting while preserving feasibility. When an emergency case arrives, the system searches for affected changes rather than rebuilding the entire schedule. Human schedulers review proposed changes, particularly where fairness or clinical judgment is difficult to encode.

Outcome

The value of the approach is not merely a shorter computed schedule. It comes from making trade-offs explicit, detecting conflicts early, and presenting alternatives to decision-makers. A schedule that minimizes average waiting but repeatedly disadvantages a vulnerable patient group would not be acceptable, even if its numerical objective were strong.

Learning Points

The case illustrates four principles. First, representation determines what the system can reason about. Second, hard constraints and soft preferences must be distinguished. Third, approximate methods may be appropriate when the environment changes continuously. Fourth, professional oversight remains essential when objectives involve safety, fairness, and clinical responsibility.

9. Limitations, Risks, and Professional Responsibilities

Search quality depends on the correctness of the model. An optimal solution to an inaccurate model is still a poor decision. Common errors include omitting constraints, using an unsuitable cost function, treating a heuristic as a fact, ignoring uncertainty, and evaluating performance only on average cases.

Computational limits also matter. Large frontiers can exhaust memory; local methods can become trapped; evolutionary algorithms can converge prematurely; and game-playing systems can fail outside the distribution represented by their evaluation functions. Approximate solutions should therefore be accompanied by bounds, sensitivity analysis, or clear statements of uncertainty whenever possible.

Automated allocation creates governance concerns. If a scheduling objective silently gives priority to profitable customers, the system may reproduce organizational bias. If a routing system systematically sends pollution or traffic through disadvantaged communities, efficiency has been achieved at an unacceptable social cost. Systems should provide auditable objectives, preserve relevant logs, permit authorized human override, and be tested for disparate effects.

In adversarial applications such as security or automated negotiation, the other party may exploit predictable heuristics. Robustness requires stress testing, adversarial evaluation, and monitoring after deployment. Privacy is relevant when states include personal, medical, location, or behavioural information. Professional responsibility includes documenting assumptions, validating data, protecting access to plans, and ensuring that the system's authority is proportionate to the consequences of error.

10. Current Directions and Best Practice

Modern AI systems increasingly combine classical search with learned components. Neural models may propose actions, estimate value, generate heuristics, or guide branching, while symbolic search enforces constraints and verifies feasibility. Monte Carlo tree search combines selective simulation with tree statistics and has been influential in complex games and sequential decision systems.

A strong implementation generally follows these practices:

1. Define the state, actions, objectives, constraints, and failure conditions before selecting an algorithm.

2. Separate feasibility from preference: hard constraints should not be hidden inside an arbitrary penalty.

3. Establish baselines using simple methods before adopting sophisticated optimization.

4. Use admissible or otherwise validated heuristics when guarantees matter.

5. Report solution quality, computation time, robustness, and sensitivity rather than a single score.

6. Test unusual, adversarial, and changing conditions.

7. Keep human review and escalation mechanisms for high-impact decisions.

8. Monitor the deployed system because data, costs, opponents, and operational priorities change.

Chapter Summary

Search represents problem solving as exploration of states and actions. Uninformed methods differ in their expansion order and guarantees: BFS favours shallow solutions, DFS conserves memory, uniform-cost search handles unequal costs, and iterative deepening combines useful properties of BFS and DFS. Heuristic search adds estimates of remaining cost; A* combines accumulated and estimated costs and is optimal under appropriate heuristic conditions.

Constraint satisfaction exploits variables, domains, propagation, and intelligent ordering. Optimization methods range from exact techniques such as branch-and-bound and integer programming to local search and evolutionary algorithms that handle large or irregular spaces. Planning constructs action sequences or partial orders using preconditions and effects. Adversarial search models competing agents through minimax, while alpha-beta pruning reduces computation without changing the decision. Across scheduling, routing, resource allocation, and strategic decisions, successful AI depends not only on algorithms but also on accurate representation, explicit objectives, uncertainty management, fairness, auditability, and responsible human oversight.

Key Terms

State space: The set of states reachable through available actions.

Frontier: The collection of generated search nodes awaiting expansion.

Completeness: The property of finding a solution whenever one exists under stated assumptions.

Optimality: The property of returning a least-cost or highest-value solution.

Heuristic: A problem-specific estimate used to guide search.

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

Consistent heuristic: A heuristic satisfying a triangle-inequality-like condition across every action.

A*: A search algorithm that prioritizes nodes using g(n)+h(n).

Constraint satisfaction problem: A problem defined by variables, domains, and constraints.

Constraint propagation: Removing values that cannot participate in any valid complete assignment.

Local search: Optimization by repeatedly moving among neighbouring candidate solutions.

Simulated annealing: A local-search method that sometimes accepts worse moves to escape local optima.

Evolutionary algorithm: A population-based optimization method using selection, variation, and fitness evaluation.

Pareto-optimal solution: A feasible solution that cannot improve one objective without worsening another.

Planning: Constructing actions that achieve specified goals from an initial state.

Predicate: A symbolic statement that may be true or false in a planning state.

Minimax: Adversarial search assuming one player maximizes utility and the opponent minimizes it.

Alpha-beta pruning: Elimination of game-tree branches that cannot affect the minimax result.

Evaluation function: An estimate of the value of a non-terminal state.

Branch-and-bound: An exact search method that prunes regions using bounds on their best possible value.

Review Questions

Short Answer Questions

1. What five elements are normally used to formulate a search problem?

2. Why is uniform-cost search preferable to breadth-first search when action costs differ?

3. What is the difference between an admissible and a consistent heuristic?

4. How does forward checking improve backtracking in a constraint satisfaction problem?

5. What information do alpha and beta represent in alpha-beta pruning?

Long Answer Questions

1. Compare breadth-first, depth-first, uniform-cost, and iterative-deepening search in terms of expansion strategy, memory, completeness, and optimality.

2. Explain A* search in detail and discuss how heuristic quality affects both computational performance and solution guarantees.

3. Describe local search and evolutionary optimization, including their strengths, failure modes, and appropriate applications.

4. Explain how classical planning represents actions, preconditions, effects, and goals. Contrast forward, backward, and partial-order planning.

5. Develop a minimax-based game-playing system and explain how depth limits, evaluation functions, move ordering, and alpha-beta pruning would improve it.

Analytical / Application Questions

1. Design a CSP formulation for university examination timetabling. Identify variables, domains, hard constraints, soft preferences, and two useful variable-ordering heuristics.

2. A logistics firm must minimize delivery cost while respecting deadlines, vehicle capacity, driver hours, and carbon limits. Recommend a combination of search and optimization methods and justify the trade-offs.

3. Critically evaluate the hospital scheduling case. Which objectives should be hard constraints, which should be optimized, and what governance controls are necessary before deployment?

22. Multiple Choice Questions with Answers

Question 1

A delivery route has unequal travel costs on its edges. Which algorithm guarantees a least-cost route without using a heuristic, assuming non-negative edge costs?

A. Depth-first search

B. Uniform-cost search

C. Greedy best-first search

D. Breadth-first search

Correct Answer: B. Uniform-cost search

Question 2

For A* graph search, which property is especially useful because it prevents a node from needing reconsideration after expansion under standard conditions?

A. The heuristic is consistent

B. The heuristic is always zero

C. The branching factor is infinite

D. The goal has multiple labels

Correct Answer: A. The heuristic is consistent

Question 3

In a constraint satisfaction problem, the minimum-remaining-values heuristic selects the variable that:

A. Has the largest domain

B. Was assigned most recently

C. Has the fewest currently legal values

D. Constrains no other variable

Correct Answer: C. Has the fewest currently legal values

Question 4

A local-search algorithm occasionally accepts a worse neighbouring solution, especially early in its execution, to escape local optima. Which method is this?

A. Uniform-cost search

B. Simulated annealing

C. Breadth-first search

D. Minimax

Correct Answer: B. Simulated annealing

Question 5

Which statement best describes a Pareto-optimal solution in a multi-objective problem?

A. It always minimizes every objective independently

B. It is the first solution found by local search

C. No objective can improve without worsening at least one other objective

D. It violates all soft constraints but satisfies one hard constraint

Correct Answer: C. No objective can improve without worsening at least one other objective

Question 6

In classical planning, an action's preconditions specify:

A. The conditions that must hold before the action can occur

B. The cost of every alternative plan

C. The opponent's evaluation function

D. The complete search frontier

Correct Answer: A. The conditions that must hold before the action can occur

Question 7

In minimax search, a MIN node selects the child with:

A. The highest utility for MAX

B. The lowest utility for MAX

C. The smallest branching factor

D. The greatest path depth

Correct Answer: B. The lowest utility for MAX

Question 8

Alpha-beta pruning is correct because it:

A. Changes the utility values of terminal states

B. Removes branches that cannot affect the final minimax decision

C. Guarantees that every game tree is searched completely

D. Replaces the evaluation function with a heuristic route cost

Correct Answer: B. Removes branches that cannot affect the final minimax decision

Question 9

A hospital scheduling model produces an excellent numerical objective but repeatedly delays one vulnerable patient category. What is the most appropriate first response?

A. Deploy it because the objective is mathematically optimal

B. Remove all constraints to increase flexibility

C. Review the objective, fairness criteria, and governance controls

D. Use depth-first search instead of optimization

Correct Answer: C. Review the objective, fairness criteria, and governance controls

Question 10

Why can a relaxed problem provide a useful admissible heuristic for A*?

A. Its optimal cost cannot exceed the cost of the more constrained original problem

B. It always has a larger branching factor

C. It guarantees that every search node is a goal

D. It deliberately overestimates the remaining cost

Correct Answer: A. Its optimal cost cannot exceed the cost of the more constrained original problem