Problem Representation in AI: State Space, Worked Water-Jug Example and Exam Traps

“Measure exactly 2 litres” feels obvious to a person. A search program needs states, legal actions, a start, a goal test and a cost. Problem representation is this translation, not the search algorithm.

The model uses the 4-litre and 3-litre water-jug setup, traces BFS and exposes lossy representations. Jug A holds at most 4 litres, jug B at most 3, and both start empty. Pours stop only when the source empties or destination fills. Each operator costs 1 unless stated otherwise.

1. Problem representation is the model that makes search possible

The task says “obtain exactly 2 litres”. Representation defines states and actions; search decides which states to explore. An algorithm cannot repair a model missing information required for legal actions or success.

A classical search problem is (S, A, T, s0, G, c):

• S is the state set and A(s) contains the actions applicable in state s.

• T(s,a) returns the successor, while s0 is the initial state.

• G(s) tests success and c(s,a,s') gives the step cost.

A solution is an action sequence from s0 to a state satisfying G. An optimal solution minimises accumulated path cost.

Problem representation describes task states and changes. Knowledge representation describes domain facts, relations or rules. Search may use both, but the terms are not synonyms.

2. Translate the water-jug task into states, operators, goal and cost

Represent a state by (x,y), where x is the litres in A and y the litres in B. Thus 0 <= x <= 4, 0 <= y <= 3, s0=(0,0), and the main goal is G(x,y) := (x=2) OR (y=2).

The six operators are:

• FillA: (x,y) -> (4,y) if x<4; FillB: (x,y) -> (x,3) if y<3.

• EmptyA: (x,y) -> (0,y) if x>0; EmptyB: (x,y) -> (x,0) if y>0.

• PourAtoB: set d=min(x,3-y), then produce (x-d,y+d) if x>0 and y<3.

• PourBtoA: set d=min(y,4-x), then produce (x+d,y-d) if y>0 and x<4.

Every applied operator has c=1. For (4,2), PourAtoB gives d=min(4,1)=1, hence (3,3). For (1,3), PourBtoA gives d=min(3,3)=3, hence (4,0).

3. Count the state space, then distinguish possible from reachable

Jug A has 5 integer contents, {0,1,2,3,4}, and B has 4, {0,1,2,3}. Their Cartesian product therefore has 5 x 4 = 20 capacity-valid pairs. This does not mean all 20 are reachable from (0,0) under boundary pours.

The exact 14 reachable states are:

• (0,0), (4,0), (0,3), (4,3), (1,3), (3,0), (1,0)

• (3,3), (0,1), (4,2), (4,1), (0,2), (2,3), (2,0)

Pairs such as (1,1) and (2,2) satisfy the capacity bounds but are unreachable when every pour must end at a boundary.

Storing only total water is too coarse. It merges (4,0) and (1,3) as total 4, although their successors differ. PourAtoB takes (4,0) to (1,3), while EmptyB takes (1,3) to (1,0). The ordered pair preserves information required by T.

4. Worked breadth-first trace: reach 2 litres in four actions

Breadth-first graph search with a visited set discovers these new-state frontiers:

• Depth 0: {(0,0)}

• Depth 1: {(4,0),(0,3)}

• Depth 2: {(4,3),(1,3),(3,0)}

• Depth 3: {(1,0),(3,3)}

• Depth 4: {(0,1),(4,2)}

The highlighted route is (0,0) --FillB--> (0,3) --PourBtoA, d=3--> (3,0) --FillB--> (3,3) --PourBtoA, d=1--> (4,2). Here y=2, so G(4,2)=true. Four operators give total cost 4. Because BFS first reaches a goal at depth 4 under unit costs, no solution of depth 0 to 3 exists.

This is graph search because actions can revisit states. For example, EmptyB sends (0,3) back to (0,0). A visited set stops such fill-empty cycles. Graph Algorithms: BFS, DFS and Shortest Paths reviews the traversal mechanics.

5. Representation choices change what counts as a solution

Goal tests are not interchangeable. For x=2 OR y=2, (4,2) succeeds at depth 4. For x=2, the first goal states are (2,3) and (2,0) at depth 6. For the exact goal (2,0), one six-action route is (0,0) -> (0,3) -> (3,0) -> (3,3) -> (4,2) -> (0,2) -> (2,0).

Operator semantics also change the graph. Boundary pours make (1,1) unreachable. Allowing an arbitrary partial pour, such as moving 1 litre to change (1,3) into (2,2), adds states and edges. It defines a different problem.

So does changing cost. The four-action path costs 4 under unit costs. If cost instead means litres physically moved, its actions move 3 + 3 + 3 + 1 = 10 litres. Search can optimise only its stated metric.

6. Keep problem representation, knowledge representation and search separate

Knowledge representation might store Wet(Floor1) and the rule Wet(z) -> Slippery(z). These support inference, but do not specify a search start, actions, transitions or goal. Propositional and Predicate Logic: Truth Tables, Quantifiers covers facts, predicates and quantifiers.

If removing a field makes configurations with different successors look identical, the state is too coarse. Full action history is wasteful when legality and goals depend only on (x,y). Keep history only when it changes future legality or cost.

7. Common traps and the exam-style checks that expose them

Watch for these formulation errors:

• A bare goal pair misses valid states such as (4,2). Write the Boolean goal test.

• Treating all 20 valid pairs as reachable ignores operator constraints. Explore from s0.

• Omitting pour preconditions can overflow a jug. Compute d with min.

• Storing only x+y merges non-equivalent states. Retain (x,y).

• Skipping repeated-state detection creates cycles. Maintain a visited set.

Try four checks before reading the answers. How many capacity-valid pairs exist? What does PourAtoB do to (4,2)? What does PourBtoA do to (1,3)? What is the shortest unit-cost depth for x=2 OR y=2?

The answers are 20; (3,3) because d=1; (4,0) because d=3; and depth 4, where BFS first discovers (4,2). These checks test counting, successor calculation and optimal depth, not memorisation.

A question may ask you to find a missing component, choose a sufficient state, calculate a successor, separate valid from reachable states, trace a frontier, or spot a changed problem.

8. Problem representation in one minute: define first, search second

The irreducible checklist is: choose a sufficient state, list actions and preconditions, define transitions, fix the initial state, write the goal as a test, choose the cost, then search. Here the anchors are 20 capacity-valid pairs, 14 reachable states, goal (4,2) and optimal unit cost 4.

Now cover the operator list. Reconstruct every legal successor of (1,3) and (4,2), then rebuild the four-step path backwards from the goal. You should be able to justify every edge.

ZERO TO HERO is a structured computer-science path that covers state space representation. Artificial Intelligence (AI) is the broader course if you want to continue past this formulation.