Search & Planning

Key ideas

A search problem has states, actions (successors), step costs, a start and a goal test. Let $b$ = branching factor, $d$ = depth of the shallowest goal, $m$ = maximum depth.

IDS repeats the shallow levels, but most nodes sit at the deepest level, so the overhead is small: for $b=10$, $d=5$ it generates 123,456 nodes against 111,111 for a single pass (about 11% more), while memory stays that of one DFS. UCS is Dijkstra's algorithm, i.e. A* with $h=0$¹. BFS may goal-test when a node is generated; UCS and A* must test when it is popped, otherwise a cheaper path found later is missed.

Heuristics. $h$ is admissible if it never overestimates the true cost $h^*$; consistent (monotone) if $h(m)\le c(m,n)+h(n)$ on every edge¹ and $h(\text{goal})=0$. Summing that inequality along a path to the goal shows consistent ⇒ admissible, and since $f(n)=g(m)+c(m,n)+h(n)\ge g(m)+h(m)=f(m)$, $f$ never decreases along a path. So with a consistent $h$, A* expands nodes in non-decreasing $f$, pops each node with its optimal $g$ and never needs to process it twice¹. With an admissible but inconsistent $h$, A* is optimal only if a node reached again by a cheaper path is put back on the open list¹; a strict expanded list can return a suboptimal path. On an infinite graph A* still finds a solution, if one exists, when $b$ is finite and every edge costs at least some $\varepsilon>0$¹. Good admissible heuristics come from relaxed problems (e.g. Manhattan distance for the 8-puzzle), and the maximum of several admissible heuristics is admissible and at least as informed. Weighted A* ($f=g+w\,h$, $w>1$) usually expands fewer nodes and returns a path costing at most $w\,C^*$¹. A* keeps every generated node, its main drawback; memory-bounded variants such as IDA* (iterative deepening on $f$) need memory linear in depth but re-expand nodes¹.

Constraint satisfaction (CSP). Variables, domains, constraints; solved by backtracking². Forward checking removes, after each assignment, the values of unassigned neighbours that conflict with it and backtracks when a domain empties; arc consistency (AC-3, MAC) also checks pairs of unassigned variables, so it prunes more³. Put the most critical variables first²: the one with the fewest remaining values (MRV)³, and on ties the one in the most constraints with unassigned variables (degree heuristic), whose value prunes the most other domains. Try first the value that removes the fewest values from other domains³.

Local search keeps one complete state. Hill climbing (greedy descent) moves to the best neighbour and stops at a local optimum⁴. Simulated annealing accepts a worse neighbour with probability $e^{-\Delta E/T}$: close to a random walk at high $T$, greedy descent as $T\to 0$⁴. Tabu search keeps taking the best allowed move, even a worse one, but forbids undoing recent changes for a few steps (the tabu tenure), so it does not cycle back⁴. TSP 2-opt removes two edges and reconnects by reversing a segment. Beam search keeps the $k$ most probable prefixes; $k=1$ is greedy search, cost grows as $O(k\,|\mathcal{Y}|\,T')$ versus $O(|\mathcal{Y}|^{T'})$ for exhaustive search⁵. A finite beam is guaranteed optimal only if it can hold every prefix.

Games. Minimax backs up max at MAX nodes and min at MIN nodes. Alpha–beta prunes branches that cannot change the decision, so it returns the same value and move⁶. With perfect move ordering the leaf count follows $b\times1\times b\times1\cdots$, about $b^{d/2}$ instead of $b^d$, and iterative deepening supplies good ordering⁶. As an AND/OR tree, MAX needs one good move (OR node) that works against every MIN reply (AND node).

Planning (STRIPS). Each action has $pre(a)$, $add(a)$, $del(a)$. Forward (progression) planning picks the first action first; backward (regression) planning picks the last action first; a partial-order planner commits to an order only when forced⁷. It starts from a dummy start action (achieves the initial state) and finish action (preconditions = goal), keeps causal links $a_2\xrightarrow{P}a_3$, and resolves a threat (an action that may undo $P$ between them) by ordering it before $a_2$ or after $a_3$⁷. The Sussman anomaly (C on A; goal A on B and B on C) defeats planners that finish one subgoal before starting the other: whichever subgoal is achieved first must be undone to achieve the second⁸.

Formulas

Regression of goal $g$ through a relevant action ($add(a)\cap g\ne\emptyset$, $del(a)\cap g=\emptyset$)⁷:

Worked example

Edges S→A (2), S→B (5), A→B (1), B→G (3); $h(S)=0$, $h(A)=4$, $h(B)=0$, $h(G)=0$. True costs to G are 6, 4, 3, 0, so $h$ is admissible, but $h(A)=4>c(A,B)+h(B)=1$: not consistent. A* with a strict expanded list: pop S; push A ($f=2+4=6$) and B ($f=5$). Pop B, push G ($f=g=8$). Pop A, push S–A–B ($g=3$, $f=3$); when it is popped, B is already expanded, so it is dropped. Pop G and return cost 8, while S–A–B–G costs 6. Re-opening B (non-strict list) gives the optimum.

Common pitfalls

• BFS is not cost-optimal when step costs differ — it minimises the number of edges.
• Admissible + strict expanded list can fail; it needs a consistent heuristic¹.
• UCS cannot goal-test on generation, unlike BFS.
• Alpha–beta never changes the answer — only how many leaves are evaluated; bad ordering just prunes less⁶.
• Forward checking ≠ arc consistency: forward checking only looks at neighbours of the variable just assigned³.
• A wider beam costs more and usually finds an equally or more probable output⁵, but it is not guaranteed to: the extra prefixes can crowd out the one that led to the narrower beam's answer.
• Regression adds preconditions and removes achieved goals — and the action must not delete any other goal⁷.