Formulating a Problem for Search

Two roads in that table are deliberately unusual and both will matter.

Amba to Erandol costs 33 km for a straight-line distance of 12.65. It is the old ghat road, and it goes a long way round a hill. Erandol is genuinely close to the goal and the road to it is terrible. Greedy Best First Search walks straight into it.

Hivra to Jalna costs 16 km for a straight-line distance of 3.16. There is a river between them and the bridge is upstream. Hivra is three km from the goal as the crow flies and seven km from it by road, through Fanas.

Formulated:

• Initial state: in Amba.
• Actions: take any road leaving the current town.
• Transition model: the town at the other end.
• Goal test: is the town Jalna.
• Step cost: the road's length in km. Path cost: the sum.

The state space has nine states, one per town. Note what a state is NOT: it is not the route taken so far. Two agents standing in Chinch, one having come by Amba and one by Bori, are in the same state. That is the single most useful fact about state spaces and the reason The Search Tree, and How an Algorithm Is Judged can talk about avoiding repeated work.

Problem two: the 8-puzzle

Eight numbered tiles in a three by three frame with one blank. A tile next to the blank can slide into it. The goal is a fixed arrangement.

# The 8-puzzle formulated as a search problem. A state is the nine squares read
# left to right, top to bottom, with 0 for the blank.
START = (7, 2, 4,
         5, 0, 6,
         8, 3, 1)
GOAL = (0, 1, 2,
        3, 4, 5,
        6, 7, 8)

def show(state):
    return "\n".join(" ".join("_" if v == 0 else str(v) for v in state[r * 3:r * 3 + 3])
                     for r in range(3))

def actions(state):
    """The blank can move Up, Down, Left or Right, if it stays on the board."""
    i = state.index(0)
    row, col = divmod(i, 3)
    out = []
    if row > 0: out.append("Up")
    if row < 2: out.append("Down")
    if col > 0: out.append("Left")
    if col < 2: out.append("Right")
    return out

def result(state, action):
    i = state.index(0)
    j = i + {"Up": -3, "Down": 3, "Left": -1, "Right": 1}[action]
    lst = list(state)
    lst[i], lst[j] = lst[j], lst[i]
    return tuple(lst)

def is_goal(state):
    return state == GOAL

print("initial state"); print(show(START))
print()
print("actions available:", actions(START))
print()
for action in actions(START):
    print("after %s:" % action)
    print(show(result(START, action)))
    print("   goal reached?", is_goal(result(START, action)))
    print()
print("step cost is 1 for every move, so path cost = number of moves")

initial state
7 2 4
5 _ 6
8 3 1

actions available: ['Up', 'Down', 'Left', 'Right']

after Up:
7 _ 4
5 2 6
8 3 1
   goal reached? False

after Down:
7 2 4
5 3 6
8 _ 1
   goal reached? False

after Left:
7 2 4
_ 5 6
8 3 1
   goal reached? False

after Right:
7 2 4
5 6 _
8 3 1
   goal reached? False

step cost is 1 for every move, so path cost = number of moves

Three formulation decisions in that code are worth defending, because a paper may ask you to justify one.

The actions move the BLANK, not the tiles. Eight tiles with up to four moves each would be thirty-two actions, most of them illegal. The blank has at most four, and every one of them is legal. The two formulations describe the same puzzle and one of them is four times smaller.

A state is a tuple, not a list. A tuple can be put in a set or used as a dictionary key, which is what every search algorithm needs in order to remember where it has been. A list cannot.

Every step costs 1, so the path cost is the number of moves and finding the cheapest path is finding the shortest solution.

Abstraction: what to leave out

A formulation is an abstraction, and choosing it is the real skill.

The road from Amba to Bori has a surface, a gradient, traffic, potholes and a tea stall halfway along. The formulation above keeps one number. That is not laziness; it is a claim, and the claim is testable: any route that is good in the abstract problem can actually be driven. If the abstraction dropped something that made a road impassable, the claim fails and the formulation is wrong.

Two properties make an abstraction valid:

1. Every abstract solution corresponds to a real solution. A sequence of towns can be turned into a real drive.
2. Every abstract action is easier to carry out than the original problem. Driving from Amba to Bori is a smaller problem than driving from Amba to Jalna, and it can be solved without search.

An abstraction that fails the first property produces plans that cannot be executed, and no amount of searching detects it. This is the commonest way a formulation goes wrong in practice and the reason the first property is worth stating explicitly.

How big a state space gets

The state count is what bounds the work, so it is worth being able to compute.

# How big is a state space? Counted, so the reader need not take it on trust.
import math

print("the vacuum world with n squares")
for n in (2, 3, 10):
    print("  %2d squares: %d positions x 2**%d dirt patterns = %d states"
          % (n, n, n, n * 2 ** n))
print()
print("the sliding-tile puzzles")
for tiles, side in ((8, 3), (15, 4), (24, 5)):
    total = math.factorial(side * side)
    print("  %2d-puzzle: %d! = %d arrangements, of which %d are reachable"
          % (tiles, side * side, total, total // 2))

the vacuum world with n squares
   2 squares: 2 positions x 2**2 dirt patterns = 8 states
   3 squares: 3 positions x 2**3 dirt patterns = 24 states
  10 squares: 10 positions x 2**10 dirt patterns = 10240 states

the sliding-tile puzzles
   8-puzzle: 9! = 362880 arrangements, of which 181440 are reachable
  15-puzzle: 16! = 20922789888000 arrangements, of which 10461394944000 are reachable
  24-puzzle: 25! = 15511210043330985984000000 arrangements, of which 7755605021665492992000000 are reachable

Only half the arrangements of a sliding-tile puzzle are reachable from any given one. The set of arrangements splits into two halves and no sequence of legal moves crosses between them, which is why a puzzle bought in a shop with two tiles swapped can never be solved. The 8-puzzle has 181,440 reachable states, which a computer can enumerate; the 24-puzzle has about 7.8 times ten to the twenty-fourth, which it cannot.

Toy problems and real problems

MU's row is taught on toy problems for a reason worth stating: a toy problem has an exact, agreed formulation, so two algorithms can be compared on it. Real problems have no agreed formulation, which makes them useless for comparing algorithms and is why every textbook uses puzzles.

Distinctions

What it does not mean

A state is not a path. Standing in Chinch is one state however you got there. A formulation that put the route into the state would make the state space infinite and the search pointless.

The goal test is not a single goal state. It is a test. "Any arrangement with the blank in the middle" is a perfectly good goal test with many satisfying states.

The path cost is not always the number of steps. It is for the 8-puzzle because each step costs 1. On the map it is kilometres, and the cheapest route has more steps than the shortest one, which is the whole subject of Uniform Cost Search.

Actions are not the same as their effects. The action is the name, "take the road to Bori"; the effect is what the transition model returns. Keeping them separate is what lets the same algorithm solve both problems in this chapter.

Abstraction is not approximation. The abstract problem must be exactly solvable and every abstract solution must be realisable. If the answer is merely close, the formulation is wrong rather than approximate.

Quick revision

• Five components: initial state, actions, transition model (successor function), goal test, path cost (a sum of step costs).
• State space: the graph of states and actions. Expanding a state means generating its successors.
• A state is a configuration, not a route. Two different routes into the same town are the same state.
• The standing map: nine towns, start at Amba, goal Jalna. Two deliberate oddities: Amba to Erandol is 33 km for a 12.65 km straight line, and Hivra to Jalna is 16 km for 3.16.
• The 8-puzzle: a nine-tuple with 0 for the blank; the actions move the blank, which gives at most four legal actions instead of thirty-two mostly illegal ones; a tuple is used so states can be stored in a set.
• Abstraction is valid when every abstract solution is realisable and every abstract action is easier than the whole problem.
• The 8-puzzle has 181,440 reachable states, half of 9!. Only half the arrangements are reachable from any one of them.

Test yourself

1. List the five components of a search problem. The initial state; the actions available in each state; the transition model giving the result of an action; the goal test; and the path cost, normally a sum of step costs.

2. Formulate the district map problem. Initial state: in Amba. Actions: take any road leaving the current town. Transition model: the town at the far end of the road taken. Goal test: is the current town Jalna. Step cost: the road's length in kilometres, and the path cost is their sum.

3. Why do the 8-puzzle's actions move the blank rather than the tiles? Because the blank has at most four moves and every one of them is legal, whereas eight tiles would give thirty-two candidate actions of which most are illegal in any given state. The two formulations describe the same puzzle and the first is four times smaller.

4. What are the two conditions for a valid abstraction? Every solution of the abstract problem must correspond to a solution of the real one, and every abstract action must be easier to carry out than solving the original problem.

5. Two travellers stand in Chinch, one having come from Amba and one from Bori. Are they in the same state? Yes. A state is the configuration of the world, here simply which town you are in. How they arrived is a property of the path, not of the state.

6. How many states does the vacuum world with ten squares have? Ten possible agent positions times two to the power ten dirt patterns, which is 10,240.

7. A shopkeeper's 15-puzzle has two tiles swapped and nobody can solve it. Explain. The arrangements split into two halves and no legal move crosses between them, so exactly half of all arrangements are reachable from the goal. Swapping two tiles moves the puzzle into the unreachable half.