PadhaikoAll subjects

Problem Solving and Search (part 1: 2.1–2.4)

Artificial Intelligence (ENCT 351)

Open in the Padhaiko app

2.1 Formal problem definition: States, actions, transitions, well-defined problems

A problem-solving agent is a goal-based agent that decides what to do by finding a sequence of actions leading to a desirable state. Before searching, it must formulate the goal and the problem formally.

Definition

Well-Defined Search Problem (Five Components)

A well-defined problem is specified formally by five components:

  1. Initial state (): The state in which the agent starts.
  2. Actions (): The set of legal actions available to the agent in state .
  3. Transition model (): Returns the state produced by performing action in state . Together, the initial state, actions, and transition model implicitly define the state space (a directed graph whose nodes are states and edges are actions).
  4. Goal test (): Determines whether a given state satisfies the goal condition (either an explicit set of goal states or an abstract property such as checkmate).
  5. Path cost (): Assigns a non-negative numerical cost to each step . The cost of a path is the sum of its step costs, and an optimal solution is a solution with minimum path cost among all solutions.
Formulation of Standard AI Search Problems
ProblemInitial StateActionsTransition ModelGoal TestPath Cost
Route finding (map)Drive to an adjacent citySum of road distances ()
8-PuzzleAny tile configurationSlide blank Swap blank with adjacent tileTiles in target order per move
8-QueensEmpty board (or queens placed)Place a queen in column with no conflictAdd queen to board queens placed, none attacking (any solution is valid)
2-Square Vacuum WorldAgent in or , squares clean/dirty, , Moves agent or cleans current squareBoth squares clean per action

2.2 Constraint satisfaction problems: Node consistency, path consistency, backtracking

Standard search treats each state as an indivisible black box. A Constraint Satisfaction Problem (CSP) uses a factored representation—a set of variables and constraints—which lets the solver prune impossible values early rather than waiting until a full assignment fails.

Definition

Constraint Satisfaction Problem (CSP)

A CSP is a triple where:

An assignment is consistent if it violates no constraints, complete if every variable is assigned, and a solution if it is both consistent and complete.

Types of Constraints and Consistency

Inference (constraint propagation) shrinks domains before or during search:

Definition

Node, Arc, and Path Consistency

  1. Node consistency (1-consistency): A variable is node-consistent if every value in its domain satisfies all unary constraints on .
  2. Arc consistency (2-consistency): A variable is arc-consistent with respect to another variable if for every value , there exists at least one value such that satisfies the binary constraint between and . Enforced by the AC-3 algorithm in time ( constraints, max domain size ).
  3. Path consistency (3-consistency): A two-variable pair is path-consistent with respect to a third variable if, for every consistent assignment , there exists an assignment that is consistent with both and .
Comparison of CSP Consistency Levels
Consistency LevelScope CheckedRemoves InconsistentComplexity / Strength
Node consistencySingle variable Values violating unary constraintsLinear ; weakest
Arc consistency (AC-3)Directed pair Values in with no support in ; detects many failures early
Path consistency (PC-2)Triples Consistent pairs lacking a valid third value Stronger; narrows binary relations

Backtracking Search for CSPs

Because variable assignment order is commutative, CSP search fixes one unassigned variable at a time, giving at most leaves instead of .

Backtracking search with inferenceText
function BACKTRACK(assignment, csp):
    if assignment is complete: return assignment
    var = SELECT-UNASSIGNED-VARIABLE(csp, assignment)   // MRV + Degree heuristic
    for each value in ORDER-DOMAIN-VALUES(var, assignment, csp):  // LCV heuristic
        if value is consistent with assignment:
            add {var = value} to assignment
            inferences = INFERENCE(csp, var, value)    // Forward checking or MAC
            if inferences != failure:
                add inferences to csp
                result = BACKTRACK(assignment, csp)
                if result != failure: return result
            remove {var = value} and inferences from assignment / csp
    return failure

Four standard speed-ups in backtracking CSPs:

  1. Minimum Remaining Values (MRV / fail-first): pick the variable with the fewest legal values left.
  2. Degree heuristic (tie-breaker): pick the variable involved in the most constraints with unassigned variables.
  3. Least Constraining Value (LCV): try the value that rules out the fewest choices for neighbouring variables.
  4. Forward checking / MAC: when is assigned, delete incompatible values from unassigned neighbours' domains; if any domain becomes empty, backtrack immediately.

2.3 Search algorithms, strategies and evaluations

A search tree is built on the fly from the initial state (root) by expanding nodes using the transition model. Notice the distinction between a state (a configuration in the world) and a search node (a data structure storing state, parent, action, path-cost , and depth).

Frontier, Tree Search, and Graph Search

Four Criteria for Evaluating Search Strategies

Definition

Search Evaluation Metrics

Every search algorithm is evaluated on four standard criteria, using branching factor (max successors per node), shallowest goal depth , and maximum path length (which may be ):

  1. Completeness: Is the algorithm guaranteed to find a solution if at least one exists?
  2. Optimality: Does it guarantee finding the lowest-cost solution?
  3. Time complexity: How many nodes are generated/expanded in the worst case (expressed in )?
  4. Space complexity: How many nodes must stay in memory at once (size of frontier and explored set)?

2.4 Uninformed: BFS, DFS, iterative deepening

Uninformed (blind) search strategies have only the problem definition and no domain-specific clue about which non-goal state is closer to the goal.

Breadth-First Search (BFS)

Depth-First Search (DFS)

Iterative Deepening Depth-First Search (IDDFS / IDS)

Comparison of BFS, DFS, and Iterative Deepening (IDS)
CriterionBFSDFSIterative Deepening (IDS)
Data structureFIFO QueueLIFO Stack / RecursionRepeated Depth-Limited Stack
Complete?Yes (if finite)No (can loop or go to )Yes (if finite)
Optimal?Yes (if unit step cost)NoYes (if unit step cost)
Time complexity
Space complexity (exponential) (linear) (linear)
Best use caseShallow goal, small Memory tight, many goalsLarge space, unknown goal depth

Worked Out Examples

Example 2.1

2.1 (6 marks)

Consider a CSP with variables , domains , , , and binary constraints , , . Enforce node and arc consistency using AC-3 and find the reduced domains.

Node consistency: There are no unary constraints, so all domains remain unchanged: , , .

Arc with constraint : Since , value has no supporting value in ( is false), while and are supported by . Remove from , giving .

Arc with constraint : Value has no support in , while is supported. Remove from , giving .

Re-checking arc after shrunk: Now . For , there is no value in with ; for , holds. Remove from , leaving .

Remaining arcs: Checking removes nothing further (, , ), so the queue empties and AC-3 solves the CSP without any backtracking!

Answer:

Reduced domains: , , (unique consistent assignment).

Example 2.2

2.2 (6 marks)

For a uniform search tree with branching factor and goal depth (assuming nodes at depth are counted as root, or counting generated non-root nodes ), compare the number of non-root nodes generated by BFS and IDS, and compute the ratio .

BFS non-root nodes generated up to depth :

IDS non-root nodes generated across depth limits : Nodes at depth are regenerated times:

Overhead ratio:

Answer:

BFS generates non-root nodes; IDS generates nodes, an overhead of only (ratio ) while using linear memory.

Example 2.3

2.3 (6 marks)

Consider a directed search graph with start node , goal , and alphabetical successor lists: , , , , , . Trace the order of expanded nodes for (a) Graph BFS and (b) Graph DFS (pushing right-to-left so alphabetical order is popped first), stopping as soon as is expanded.

Graph BFS (FIFO queue, goal tested on expansion):

  • Start: Frontier . Pop , expand Frontier .
  • Pop , expand Frontier .
  • Pop , expand Frontier .
  • Pop , expand Frontier .
  • Pop (no new nodes) Frontier .
  • Pop ( already in explored/frontier) Frontier .
  • Pop (goal reached!). Expanded order: . Path: (depth ).

Graph DFS (LIFO stack, alphabetical pop priority):

  • Start: Stack . Pop , push then Stack (top on right).
  • Pop , push then Stack .
  • Pop , push Stack .
  • Pop (goal reached!). Expanded order: . Path: .
Answer:

BFS expands (7 expansions, finds path ); DFS expands (4 expansions, finds path ).

Exercises

Exercise: Problem Formulation, CSPs, and Uninformed Search

Question 1

Define the five components of a well-defined search problem and formulate the 8-puzzle problem formally using them.

Five components: (1) Initial state, (2) Actions available at each state, (3) Transition model , (4) Goal test, and (5) Step/path cost function.

8-puzzle formulation:

  • States: Any arrangement of the numbered tiles and blank space in a grid.
  • Initial state: The given starting tile configuration.
  • Actions: Move the blank , , , or (when valid inside the grid).
  • Transition model: Swaps the blank with the adjacent tile in the chosen direction.
  • Goal test: Checks whether the grid matches the target arrangement (e.g., in order with the blank at the corner/end).
  • Path cost: Each move costs , so total path cost equals the number of moves.
Answer:

A well-defined problem has initial state, actions, transition model, goal test, and path cost. For the 8-puzzle, states are tile boards, actions slide the blank in four directions, transitions swap the blank with an adjacent tile, the goal test checks target tile order, and each step costs .

Question 2

A uniform search tree has branching factor and a goal at depth . How many total nodes (including the root at depth ) exist up to depth ? Also compare non-root nodes generated by BFS vs. IDS up to depth .

Total nodes up to depth (including root):

Non-root nodes generated by BFS:

Non-root nodes generated by IDS ():

Answer:

Total nodes (including root) . BFS generates non-root nodes; IDS generates non-root nodes (an overhead of ).

Question 3

Differentiate between node consistency, arc consistency, and path consistency in CSPs, and explain the MRV and LCV heuristics in backtracking search.

Consistency levels: Node consistency removes domain values violating unary constraints on a single variable; arc consistency removes values in that have no valid partner in under binary constraints; path consistency ensures every consistent pair can be extended consistently to any third variable .

Heuristics: MRV (Minimum Remaining Values) selects the unassigned variable with the fewest legal values left (fail-first, shrinking the branching factor early). LCV (Least Constraining Value) orders values of the chosen variable to try first the value that eliminates the fewest choices from neighbouring variables (leaving maximum flexibility to succeed).

Answer:

Node consistency enforces 1-variable unary constraints, arc consistency enforces binary support between pairs, and path consistency enforces 3-variable consistency on pairs. MRV chooses the most constrained variable first; LCV tries the value that restricts neighbours least.

Question 4

Consider a CSP with variables having domains , , , and constraints and . Enforce arc consistency and determine whether a solution exists.

Check arc with : is supported by ; is supported by . So .

Check arc with : For , satisfies . For and , there is no with . Thus and are pruned from , leaving .

Propagate to with : Neither nor in satisfies . Hence becomes (empty!).

Answer:

Arc consistency reduces to , proving immediately that no solution exists.

Question 5

Compare Breadth-First Search, Depth-First Search, and Iterative Deepening Search on completeness, optimality, time complexity, and space complexity. Why is IDS preferred over BFS when memory is limited?

Comparison: BFS is complete and optimal (for unit step costs), with time and space. DFS is neither complete (in infinite/cyclic spaces without cycle checks) nor optimal, with time and space. IDS is complete and optimal (unit cost), with time and space.

Why IDS is preferred: BFS stores the entire frontier of size , which exhausts RAM quickly for moderate and . IDS keeps only the current path of nodes in memory while repeating upper levels at a small constant factor of extra time.

Answer:

BFS takes time and space (complete, optimal for unit cost); DFS takes time and space (incomplete, non-optimal); IDS combines BFS's completeness and optimality with DFS's linear memory at time.

← IntroductionProblem Solving and Search (part 2: 2.5–2.8) →