A PROBLEM can be defined formally by FIVE COMPONENTS. This enumeration is the standard opening question of the section. 1. THE INITIAL STATE that the agent starts in. In(Kathmandu) 2. A description of the POSSIBLE ACTIONS available to the agent. Given a state s, ACTIONS(s) returns the set of actions that can be executed in s — the APPLICABLE actions. ACTIONS(In(Kathmandu)) = {Go(Bharatpur), Go(Banepa), …} 3. A TRANSITION MODEL, describing what each action does: RESULT(s, a) returns the state resulting from doing a in s RESULT(In(Kathmandu), Go(Banepa)) = In(Banepa) A state reachable from a given state by a single action is a SUCCESSOR. Together, the initial state, the actions and the transition model implicitly define the STATE SPACE — the set of all states reachable from the initial state. THE WORD "IMPLICITLY" IS IMPORTANT: the state space is never built and stored; it is generated as the search proceeds, which is why problems with astronomically large state spaces are still solvable. 4. THE GOAL TEST, determining whether a given state is a goal state. Sometimes an explicit set of states; sometimes an abstract property — in chess, "checkmate", which cannot be enumerated. 5. A PATH COST function assigning a numeric cost to each path. The STEP COST of taking action a in state s to reach s' is written c(s, a, s'). The path cost is the sum of the step costs. A SOLUTION is an action sequence leading from the initial state to a goal state. An OPTIMAL SOLUTION has the lowest path cost among all solutions. THE STATE SPACE FORMS A GRAPH: nodes are states, edges are actions. THE SEARCH TREE IS NOT THE SAME THING — the tree is built by the search algorithm and may contain the same state many times over, once per path that reaches it. Confusing the two is the commonest source of confusion about why graph search needs an "explored set". THE VOCABULARY OF SEARCH: NODE a bookkeeping structure in the search tree, with a STATE, a PARENT, the ACTION that produced it, and the PATH-COST g(n) FRONTIER the set of nodes generated but not yet expanded (also the "open list") EXPLORED SET the states already expanded (the "closed list") EXPANDING applying every applicable action to a node to generate its successors BRANCHING b, the maximum number of successors of any node FACTOR DEPTH d, the depth of the shallowest goal node MAXIMUM DEPTH m, the maximum length of any path in the space A NODE IS NOT A STATE. Two nodes can hold the same state reached by different paths, with different costs and parents.

THREE WORKED FORMULATIONS, showing how much the choice of state representation matters. THE 8-PUZZLE A 3×3 frame with eight numbered tiles and one blank. STATES the location of each of the eight tiles and the blank in the nine squares INITIAL STATE any configuration ACTIONS movements of the BLANK — Left, Right, Up, Down TRANSITION the blank swaps with the adjacent tile GOAL TEST the state matches the goal configuration PATH COST 1 per move, so the cost is the number of moves NOTE THE ACTION CHOICE: defining actions as movements of the BLANK rather than of the tiles gives at most 4 actions instead of up to 8, HALVING the branching factor for free. Same problem, smaller tree. STATE SPACE SIZE: 9! = 362,880 arrangements, but only HALF are reachable from any given state, because the puzzle's parity is invariant under legal moves — 9!/2 = 181,440 reachable states THE PARITY FACT IS PRACTICALLY IMPORTANT: half of all randomly generated 8-puzzles are unsolvable from the standard goal, so a solver must detect that rather than search forever. The 15-puzzle has 16!/2 = 10,461,394,944,000 states — ten trillion — which is why it needs heuristic search. THE WATER JUG PROBLEM Two jugs of capacity 4 and 3 litres, no markings, and a tap. Get exactly 2 litres into the 4-litre jug. STATES (x, y) with 0 ≤ x ≤ 4, 0 ≤ y ≤ 3 INITIAL (0, 0) GOAL TEST x = 2 ACTIONS fill either jug from the tap; empty either jug; pour from one into the other until the source is empty or the destination is full STATE SPACE 5 × 4 = 20 states — small enough to search exhaustively A SOLUTION: (0,0) → fill 3-jug → (0,3) → pour 3 into 4 → (3,0) → fill 3-jug → (3,3) → pour 3 into 4 → (4,2) [4-jug full, 2 left] → empty the 4-jug → (0,2) → pour 3 into 4 → (2,0) ✓ goal 6 actions. NOTE THAT "empty the 4-jug" LOOKS LIKE PROGRESS BEING THROWN AWAY, which is why greedy reasoning fails here and search is needed. THE TRAVELLING SALESMAN PROBLEM STATES the cities visited so far, and the current city ACTIONS travel to an unvisited city GOAL TEST all cities visited and back at the start PATH COST total distance STATE SPACE GROWTH — the reason this problem is famous: 5 cities → 12 tours 10 cities → 181,440 15 cities → 43,589,145,600 20 cities → 60,822,550,204,416,000 (distinct tours = (n−1)!/2, dividing by 2 because a tour and its reverse are the same) AT 20 CITIES, checking a million tours per second would take about 1,900 YEARS. This is why TSP is solved by heuristics and approximation rather than by exhaustive search, and it is the canonical illustration of combinatorial explosion.

ABSTRACTION is the process of REMOVING DETAIL FROM A REPRESENTATION, and choosing the right level is the essence of formulation. THE ROUTE-FINDING EXAMPLE: a real journey involves travelling companions, the radio, the scenery, the state of the road, the weather. NONE OF IT IS IN THE STATE. The state is just In(City), because everything else is irrelevant to the choice of route. WHEN IS AN ABSTRACTION VALID? When any abstract solution can be EXPANDED INTO A SOLUTION in the more detailed world. The abstract action Go(Banepa) is valid because a driver can always find some way to actually drive there. WHEN IS AN ABSTRACTION USEFUL? When carrying out each of the abstract actions is EASIER THAN THE ORIGINAL PROBLEM. If "drive to Banepa" were itself as hard as the whole problem, the abstraction bought nothing. THE CHOICE OF ABSTRACTION IS THE ENGINEERING DECISION. Too detailed and the state space explodes; too abstract and the solutions are not realisable. PROPERTIES OF A GOOD FORMULATION — a checklist, with the effect of each: 1. THE STATE CAPTURES EVERYTHING RELEVANT AND NOTHING ELSE. Extra detail multiplies the state space; missing detail makes the problem unsolvable or the solution wrong. WORKED: in the 8-puzzle, including "which move was made last" in the state would multiply the space by 4 for no benefit — but for a problem where reversing the previous move is forbidden, it would be necessary. 2. THE BRANCHING FACTOR IS AS SMALL AS POSSIBLE. Search cost is roughly b^d, so b enters exponentially. WORKED: the 8-puzzle blank-versus-tile choice takes b from about 8 to at most 4. At depth 20 that is the difference between 8^20 ≈ 1.15×10^18 and 4^20 ≈ 1.10×10^12 — a factor of about a million, from one representational decision. 3. SYMMETRIES ARE ELIMINATED. If several states are equivalent, treat them as one. WORKED: in 8-queens, fixing one queen per column removed the column permutations; the further step of requiring one per row took the space from 8^8 = 16,777,216 to 8! = 40,320. 4. THE GOAL TEST IS CHEAP. It runs on every generated node, so an expensive test dominates the run time. 5. STEP COSTS ARE NON-NEGATIVE, and ideally bounded below by some ε > 0. Zero-cost cycles break the optimality guarantees of uniform-cost search and its relatives; negative costs break them entirely. 6. REPEATED STATES ARE DETECTABLE. A state must be comparable and hashable, or the explored set cannot work. THE COST OF NOT DOING THIS: in a rectangular grid, the number of DISTINCT states at depth d grows polynomially (about 2d² for a 4-connected grid) while the number of PATHS grows as 4^d. Tree search without an explored set therefore does exponentially redundant work on a polynomially small space — which is why graph search exists. THE UNIFYING POINT OF THIS TOPIC: FORMULATION IS WHERE THE LARGEST WINS ARE. An algorithmic improvement might buy a constant factor or reduce an exponent; a better representation can remove whole dimensions from the space. That is why the five components are written down before any algorithm is chosen.