2. Example Problems

Source: AIMA 4th Ed., Chapter 3 (Section 3.2) Status: Complete

Overview

Problems fall into two categories: - Standardized/toy problems: simple, precisely defined, used to benchmark algorithms. State spaces are small enough to enumerate. - Real-world problems: large, messy, often require heuristics and approximations.

Standardized Problems

Grid World / Vacuum Cleaner World

• States: agent position (left or right room) + dirt status of each room (2 rooms × 2 dirt states = 8 states)
• Initial state: any of the 8 states
• Goal states: both rooms clean
• Actions: Left, Right, Suck
• Transition model: deterministic
• Path cost: number of actions taken

Simple enough to solve by exhaustive enumeration; useful for demonstrating completeness and optimality properties.

8-Puzzle (Sliding Tile)

• States: arrangement of 8 numbered tiles + blank in a 3×3 grid
• Initial state: some scrambled configuration
• Goal state: tiles 1-8 in order, blank in corner
• Actions: slide blank Left, Right, Up, or Down (i.e., move blank to adjacent tile)
• Transition model: blank and adjacent tile swap positions
• Path cost: number of moves
• State space size: 9!/2 = 181,440 reachable states (half are unreachable from any given start due to parity)

The 8-puzzle is a classic benchmark because: - Small enough for exact search but large enough to be nontrivial - Two natural admissible heuristics: misplaced tiles (h1) and Manhattan distance (h2) - Generalizes to the 15-puzzle (4×4, 16!/2 ≈ 10 trillion states) where heuristics are essential

15-Puzzle (4×4 Sliding Tile)

• States: 16!/2 ≈ 10.46 trillion reachable configurations
• Exact search without heuristics is completely infeasible
• Best practical approach: IDA* with Manhattan distance or pattern databases
• Generalizes to n×n puzzle which is NP-complete

Sokoban

• Push boxes in a warehouse grid to target positions
• Actions: move worker; boxes pushed if worker walks into them
• The challenge: boxes can be pushed into corners from which they cannot escape
• Much harder than 8-puzzle; typical state spaces have millions of states
• Interesting because deadlock detection requires domain knowledge

Knuth’s “4” Problem

• Goal: find a sequence of operations starting from 4 to reach any positive integer
• Operations: factorial, square root, floor
• State space: positive real numbers (infinite, continuous-like)
• Example: floor(sqrt(sqrt(sqrt(sqrt(4!))))) = 1 (reaching 1 from 4)
• Demonstrates that small-looking problems can have enormous (or infinite) state spaces

Real-World Problems

Route-Finding (Romania Map)

• States: cities in Romania (21 cities in the standard map)
• Initial state: Arad
• Goal state: Bucharest
• Actions: drive from current city to any directly connected city
• Action cost: road distance in km (positive, nonuniform)
• Heuristic: straight-line distance to Bucharest (admissible: roads are never shorter than straight lines)

Used throughout Chapter 3 as the running example. Key properties: - Nontrivial enough to illustrate algorithm differences - Small enough to trace by hand (21 nodes, ~25 edges) - Heuristic function h_SLD is easy to compute

Traveling Salesman Problem (TSP)

• States: partial tours (subsets of cities visited in some order)
• Initial state: starting city
• Goal state: all cities visited, return to start
• Action cost: road distance; minimize total tour cost
• Complexity: NP-hard; exhaustive search requires O(n!) time
• No known polynomial-time exact algorithm; heuristic and approximation methods used in practice

VLSI Layout

• Placing millions of components and routing wires on a chip
• Minimize area, signal delay, power consumption, heat
• Requires optimizing multiple objectives simultaneously
• State space is continuous and enormous; local search methods dominate

Robot Navigation / Motion Planning

• State: full configuration of robot (position + joint angles)
• Configuration space can be high-dimensional (e.g., 6-DOF arm = 6D space)
• Obstacles define forbidden regions of the state space
• Path planning must find a collision-free path
• Real problems require sampling-based methods (RRT, PRM) because explicit search is intractable

Assembly Sequencing

• States: partial assemblies of components
• Goal: fully assembled product (e.g., electric motor, protein)
• Constraint: some components must be placed before others; some assemblies are geometrically impossible if done out of order
• First demonstrated by FREDDY robot (Michie, 1972)

Protein Design

• Find a sequence of amino acids that folds into a 3D structure with desired properties
• Vast search space: 20^n sequences for length-n protein
• Goal formulation is partially unclear (what is “desired”?)
• Connects AI search to computational biology

Key Observations for Exam

1. State space size is the fundamental complexity driver — always estimate it first.
2. The 8-puzzle has exactly 181,440 reachable states (not 9! = 362,880) because of parity — this is a common exam trap.
3. TSP is NP-hard but solvable in practice for moderate n with good heuristics and branch-and-bound.
4. Real-world problems generally require abstraction — the art is in choosing what to keep.
5. Problem formulation choices (what counts as a state, what counts as an action) dramatically affect search difficulty.