Search Problems

A search problem is defined by five components:

1. State space $S$ — every configuration the world can be in. 2. Initial state $s_0 \in S$. 3. Actions $A(s)$ — what's available from each state. 4. Transition model $T(s, a) \to s'$ — deterministic version, or $P(s' | s, a)$ for stochastic. 5. Goal test — predicate over states (or a goal state). 6. Path cost — sum of step costs along a sequence of states.

A solution is a sequence of actions from $s_0$ to a goal state. An optimal solution minimizes path cost.

Examples

• 8-puzzle: state = tile arrangement, actions = slide one tile, goal = sorted arrangement, cost = 1 per move.
• Route planning: state = location, actions = take each road, goal = destination, cost = distance or time.
• Robot motion: state = configuration of all joints, actions = small continuous deltas, goal = target pose, cost = energy / path length.

State-space graph

A directed graph with states as nodes and actions as edges. Search algorithms explore this graph. Important properties:

• Branching factor $b$: average number of successors per state.
• Depth $d$: minimum number of steps from start to nearest goal.
• Search tree: the unrolled exploration of the state space. Can be larger than the state-space graph itself if states are revisited.

Repeated states are why bookkeeping (closed set, visited check) matters. Without it, a graph with cycles has an infinite search tree.

When NOT to formulate as search

• The state space is so huge that no exhaustive method works (Go: $10^{170}$ states). You need approximations: MCTS, learning, heuristics.
• The state isn't fully observable. Use planning under uncertainty (POMDPs).
• The dynamics aren't known. Use reinforcement learning.

Classical search is the right tool when the state space is enumerable in principle, the dynamics are known, and you can afford to look at many states.