Beyond Classical Search: Overview

Chapter 4 — Search in Complex Environments Book: Artificial Intelligence: A Modern Approach (Russell & Norvig, 4th ed) Pages: 110–145

The Limits of Classical Search

Classical search (Ch.3) assumes: - Observable: agent knows full state at all times - Deterministic: actions have exactly one outcome - Static: environment does not change during search - Known: the agent has a complete model of actions

Chapter 4 relaxes these assumptions in three directions:

Extension	Classical →	New Setting
Local search	Path matters	Only final state matters
Nondeterministic	One outcome/action	Multiple possible outcomes
Partial observability	Full state	Percept-based belief states
Online/unknown	Map known before search	Map discovered during execution

Landscape Metaphor

For optimization / local search: think of the state space as a landscape where elevation = objective function value.

Global maximum: best state (goal)
Local maximum: better than neighbors but not globally best
Plateau / ridge / shoulder: flat region (gradient ≈ 0)
Valley / basin: for minimization problems

Goal: reach the highest peak. Challenge: most algorithms can get stuck at local maxima.

Chapter Roadmap

Local Search: Hill climbing, simulated annealing, beam search, evolutionary algorithms
Continuous Spaces: Gradient methods, Newton–Raphson
Nondeterministic Actions: AND-OR search trees, cyclic plans
Partial Observability: Belief-state search, sensorless and contingency problems
Online Agents: LRTA*, competitive ratio, safe exploration

Key Distinction: Path vs. State

In classical search, the path is part of the solution (we need the sequence of actions).

In local search, only the goal state matters — not the path taken. This allows: - Constant O(1) memory (no frontier, no explored set) - Applicability to optimization problems with no explicit goal test (maximize/minimize an objective)

Example applications: 8-queens, VLSI layout, airline scheduling, protein structure prediction, neural architecture search.