Unit 2: Problem Solving & Search in AI; AI problem design

I. Orientation: The Search Paradigm

Most classical AI casts problem solving as searching a space of states for a path from a start to a goal. A rational agent formulates the problem, chooses a search strategy, and executes the returned plan (Newell & Simon, mid-1950s onward).

• Search agent: perceives an initial state, applies actions, and reaches a goal — decisions are offline (planned before acting) in deterministic, fully observable worlds.
• State: a snapshot of the world sufficient to decide the next action; the set of all reachable states is the state space.
• Deterministic assumption: each action from a state yields exactly one successor, so a plan is a fixed action sequence.
• Separation of concerns: formulation (what counts as a state, action, goal) is distinct from strategy (how the space is explored); Sections II–IV keep referring to this split.

II. Problem Formulation and State Space Search

A problem is well-formulated when its states, actions, and goal test are precisely specified so that search becomes mechanical.

A. The five formulation components

• Initial state: where the agent begins, e.g. Arad in the Romania route problem.
• Actions/operators: the choices legal in a state, given by ACTIONS(s).
• Transition model: RESULT(s, a) = s', defining each successor deterministically.
• Goal test: a predicate GOAL(s), either explicit (a set) or implicit (e.g. checkmate).
• Path cost: g(n) = sum of step costs c(s, a, s') along the path; an optimal solution minimises it.

B. State space search

• Search tree vs graph: nodes are partial paths, not states; the same state can recur, so a graph search keeps an explored set to avoid re-expansion.
• Frontier (fringe): the set of generated-but-unexpanded nodes; the strategy is defined entirely by how the frontier is ordered.
• Expansion: applying every legal action to a node to generate its children.
• Worked example (8-puzzle): state = tile permutation of 9 cells; actions = move blank Up/Down/Left/Right; branching factor ≈ 3; state space size = 9!/2 = 181,440 reachable states.

III. Introduction to Uninformed Search

Uninformed (blind) strategies use only the problem definition — no estimate of distance to the goal — and differ only in frontier ordering.

A. Blind strategies and their trade-offs

• Breadth-first search (BFS): FIFO frontier; complete and optimal for uniform step costs; time and space O(b^d), where b = branching factor, d = shallowest-goal depth.
• Uniform-cost search: expands the lowest-g(n) node (a priority queue); optimal for any non-negative step costs; complexity O(b^{1+⌊C*/ε⌋}) where C* = optimal cost, ε = smallest step.
• Depth-first search (DFS): LIFO frontier; space O(bm) for depth m, but not complete or optimal.
• Iterative deepening (IDS): repeated depth-limited DFS; combines BFS optimality with DFS memory O(bd); preferred blind method when depth is unknown.

IV. Core Search Algorithms

These strategies exploit knowledge about the goal to order the frontier and prune effort.

A. Best-first search

Best-first search expands the node judged closest to a goal by an evaluation function f(n).

• Evaluation function: the frontier is a priority queue ordered by f(n); the strategy's identity comes entirely from the choice of f.
• Greedy best-first: sets f(n) = h(n), the heuristic estimate of remaining cost; fast but neither complete (can loop) nor optimal.
• Anchor: on the Romania map, greedy search from Arad follows straight-line h and can miss the cheaper route through Rimnicu Vilcea.

B. A* search

A* is best-first search with f(n) = g(n) + h(n), balancing cost-so-far against estimated cost-to-go.

f(n) = g(n) + h(n)
g(n) = path cost from start to n
h(n) = estimated cheapest cost from n to a goal

• Admissibility: if h(n) ≤ h*(n) (never overestimates the true cost h*), tree-search A* is optimal.
• Consistency (monotonicity): if h(n) ≤ c(n, a, n') + h(n'), graph-search A* is optimal and never re-expands a node.
• Optimal efficiency: no other optimal algorithm using the same h expands fewer nodes; but memory grows like the number of nodes with f ≤ C*.

C. Heuristic search

A heuristic is any function that estimates goal distance to steer search; its quality determines A*'s cost.

• Dominance: if h₂(n) ≥ h₁(n) for all n and both are admissible, h₂ dominates and expands no more nodes.
• Relaxed problems: admissible heuristics arise by dropping constraints — the 8-puzzle's misplaced-tiles count and Manhattan distance both come from relaxed move rules; Manhattan dominates.
• Effective branching factor: b* measures heuristic quality — the branching factor a uniform tree of N nodes and depth d would need; b* near 1 is excellent.

V. Constraint Satisfaction

A constraint satisfaction problem (CSP) replaces path-finding with assigning values to variables so that all constraints hold — the goal is the assignment, not the route.

A. Structure and solving

• Definition: a triple ⟨X, D, C⟩ — variables X, domains D, constraints C; a solution is a complete, consistent assignment.
• Anchor (map colouring): colour Australia's regions with {red, green, blue} such that adjacent regions differ — constraints like WA ≠ NT.
• Backtracking search: depth-first assignment of one variable at a time, undoing on failure.
• Constraint propagation: forward checking removes conflicting values from neighbours; arc consistency (AC-3) enforces that every value has a consistent partner, pruning before search.
• Heuristics: minimum-remaining-values (choose the most constrained variable) and least-constraining-value speed solution.

VI. Basics of Optimization

Optimization seeks a state minimising or maximising an objective, rather than a path — the route is irrelevant, only the final state's quality matters.

A. Gradient-based methods

These follow the slope of a differentiable objective toward an optimum.

x_{t+1} = x_t − η ∇f(x_t)

• Symbols: ∇f = gradient (vector of partial derivatives), η = learning rate/step size.
• Gradient descent: steps downhill; converges to a local minimum for convex f, to a stationary point otherwise.
• Limitations: requires differentiability; can stall at local minima, saddle points, or plateaus; sensitive to η (too large diverges, too small crawls).

B. Metaheuristics

Metaheuristics are derivative-free, stochastic strategies for rugged or discrete landscapes.

1. Trajectory-based: hill climbing moves to a better neighbour and stops at any local optimum; simulated annealing accepts worse moves with probability exp(−ΔE / T), cooling T to escape local optima.
2. Population-based: genetic algorithms evolve a population by selection, crossover, and mutation, trading guaranteed optimality for broad exploration.

VII. Complexity, Data Requirements, and Solution Metrics

Every method is judged by cost, information needed, and output quality.

A. Complexity

• Four criteria: completeness (finds a solution if one exists), optimality (finds the best), time complexity, space complexity.
• Anchor: BFS time and space are both O(b^d), so memory — not time — is usually the binding constraint; IDS trims space to O(bd).
• NP-hardness: many CSPs and combinatorial optimizations are NP-hard, motivating heuristics and metaheuristics over exhaustive search.

B. Data requirements

• Model-based search: needs an explicit transition model and cost function, but no training data.
• Heuristic design: requires domain knowledge or precomputed pattern databases storing exact solution costs of subproblems.
• Learning-based methods: trade a hand-built model for sampled experience (Section VIII), shifting the burden from modelling to data collection.

C. Solution metrics

• Path cost g: total step cost of the returned solution.
• Search cost: nodes generated/expanded and wall-clock time — the price of finding the solution.
• Total cost: search cost plus path cost; a fast suboptimal plan can beat a slow optimal one.
• Optimality gap: for approximate methods, the ratio or difference between the returned and the best possible objective value.

VIII. Introduction to Reinforcement Learning for Sequential Decision Problems

Reinforcement learning (RL) handles sequential decisions where the model is unknown and feedback comes as delayed reward, unlike the fully specified problems above.

A. Framework and learning

• Markov Decision Process (MDP): ⟨S, A, P, R, γ⟩ — states, actions, transition probabilities P(s'|s,a), reward R, discount γ ∈ [0,1).
• Policy and return: a policy π(a|s) maps states to actions; the goal maximises expected discounted return G_t = Σ γ^k R_{t+k+1}.
• Value function: Q(s,a) estimates expected return of taking a in s then following π.
• Q-learning update:
  
  TEXT

  Q(s,a) ← Q(s,a) + α [ r + γ max_{a'} Q(s',a') − Q(s,a) ]

  • Symbols: α = learning rate, r = observed reward, γ = discount factor.
• Exploration vs exploitation: an ε-greedy policy explores random actions with probability ε and exploits the best-known action otherwise — the RL analogue of choosing which frontier node to trust.