Search and planning

Plain English

Before giant neural nets, AI often meant search: list the moves you could make, imagine where each leads, and pick a path to the goal. Chess programs, GPS routing, and warehouse robots still use these ideas—sometimes with learning on top.

A search problem needs a starting situation, rules for changing it, and a target. The hard part is the combinatorial explosion: even simple puzzles can have more paths than atoms in the galaxy if you explore blindly.

Modern chat agents that break tasks into steps (/learn/planning-and-multi-step-reasoning) echo classical planning, but they often skip explicit guarantees. Knowing search helps you ask when a system actually explores alternatives versus guessing one plausible plan.

How it works

Uninformed search treats all moves equally until it finds the goal. Breadth-first search (BFS) explores layer by layer and finds the shortest path in steps—but memory can explode. Depth-first search (DFS) dives deep with less memory but may wander down dead ends.

Informed search adds a heuristic: a cheap estimate of distance to the goal. A* combines the cost so far with that estimate and, with an admissible heuristic, can find optimal paths efficiently. Constraint satisfaction problems (CSPs)—like Sudoku or scheduling—assign values to variables while respecting rules; backtracking search prunes illegal partial assignments early.

Berkeley CS188 treats these as core AI tools: graph search, adversarial games, Markov decision processes, and CSPs. The same vocabulary appears in robotics and logistics today.

• State: a snapshot of the world you care about.
• Action: a legal change from one state to another.
• Goal test: does this state win?
• Frontier: states waiting to be expanded.
• Heuristic h(n): estimated steps remaining (must not overestimate for optimal A*).

from collections import deque

# Each state maps to list of (action_label, next_state)
GRAPH = {
    "start": [("go", "hall"), ("stairs", "loft")],
    "hall": [("door", "goal"), ("back", "start")],
    "loft": [("ladder", "goal"), ("back", "start")],
    "goal": [],
}

def bfs_paths(start: str, goal: str):
    """Return one shortest action sequence, or None."""
    queue = deque([(start, [])])  # (state, actions_so_far)
    seen = {start}
    while queue:
        state, path = queue.popleft()
        if state == goal:
            return path
        for action, nxt in GRAPH.get(state, []):
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, path + [action]))
    return None

print(bfs_paths("start", "goal"))  # e.g. ['go', 'door']

Going deeper

Planning in partially observable or stochastic worlds adds belief states and probability—see /learn/uncertainty-and-bayesian-thinking. Hierarchical planning decomposes goals (make dinner → chop → sauté) like prompt chains in /learn/prompting-patterns.

Knowledge-based agents combine search with logic representations in /learn/knowledge-representation-and-logic. CS188's unified view: agents perceive, represent, reason, and act—whether the reasoner is Prolog-style rules or a transformer.

Common misconceptions

Classical search is obsolete because of deep learning.

Learning handles perception and fuzzy goals; explicit search still excels when rules are clear, safety matters, or you need optimality proofs.

A* always runs fast.

Bad heuristics or huge branching factors can still make search impractical without domain-specific pruning.

Key facts

• Search problems define states, actions, transitions, and goals.
• BFS finds shortest path in number of steps; DFS uses less memory but is incomplete on infinite graphs.
• A* uses g(n) + h(n) and is optimal with an admissible heuristic.
• CSPs assign values under constraints; backtracking prunes early.
• Modern agents reuse planning vocabulary without always implementing full graph search.