Search, Planning & Problem Solving
How AI agents navigate state spaces to achieve goals — from blind search to heuristic-guided algorithms, constraint satisfaction, and the planning formalisms that power modern agentic systems.
Formalising Intelligence as Goal-Directed Search
One of AI's most powerful insights is that a huge class of intelligent behaviour can be modelled as search through a state space. A state encodes everything we need to know about the world at a point in time. An action transitions between states. The goal is to find a path from the initial state to a goal state.
This framework applies to chess (states = board positions), logistics (states = locations of packages), language generation (states = partial sequences), and robotic planning (states = robot configurations). The differences between these problems are differences in the size and structure of the state space — not fundamental differences in the computational approach.
A search problem is defined by: (1) Initial state — where we start. (2) Actions — what transitions are available. (3) Transition model — what state results from each action. (4) Goal test — whether a state is a solution. (5) Path cost — the cost of reaching a state. This 5-tuple formalises a huge range of AI tasks.
Uninformed Search Algorithms
Breadth-First Search (BFS) explores all nodes at depth d before depth d+1. Guaranteed to find the shortest path (fewest steps). Memory cost is O(b^d) where b is branching factor — catastrophic for large problems. Depth-First Search (DFS) follows one path to its end before backtracking. Memory efficient (O(bd)) but not guaranteed to find optimal solutions, and can loop infinitely without visited-state checking. Iterative Deepening (IDDFS) combines the memory efficiency of DFS with the completeness of BFS by incrementally increasing depth limits — generally preferred for large uninformed search.
Informed Search: Heuristics
A heuristic function h(n) estimates the cost from node n to the goal. A good heuristic prunes the search space dramatically. The key properties: Admissibility — h(n) never overestimates the true cost (essential for optimal solutions). Consistency — h(n) ≤ cost(n,a,n') + h(n') for every action a (stronger than admissibility for graph search).
A* search uses f(n) = g(n) + h(n), where g(n) is the cost to reach n and h(n) is the heuristic. With an admissible heuristic, A* is both complete and optimal — it finds the lowest-cost solution and explores the minimum number of nodes necessary. It is the workhorse of practical search-based AI.