Problem solving by search

Intermediate

Introduction

A goal-based agent must find a sequence of actions that reaches its goal: a route to the airport, a series of moves that solves a puzzle, a plan that assembles a product. If it can describe the problem precisely, it can search for the answer. Search is the oldest technique in AI, and it is still behind route planners, puzzle solvers, game engines and planning systems.

How it works

A search problem has five parts:

  1. an initial state, such as "at Home";
  2. the actions possible in each state, such as "drive to Park";
  3. a transition model: the state each action leads to;
  4. a goal test, such as "at Office";
  5. a step cost for each action, such as the length of the road.

All the states and actions form the state space. A search keeps a frontier of states it has found but not yet expanded, and repeats: take a state from the frontier, stop if it passes the goal test, otherwise add the states it leads to. A parent link for each state lets it rebuild the path at the end, and an explored set stops it from going round in circles.

The searches differ only in which state they take next:

  • Breadth-first search (BFS) uses a queue: oldest first. It explores level by level, so it finds a solution with the fewest steps.
  • Depth-first search (DFS) uses a stack: newest first. It dives down one path, using little memory, but its solution can be long and costly.
  • Uniform-cost search (UCS) uses a priority queue: cheapest path first. With non-negative costs it finds the cheapest solution; it is Dijkstra's algorithm, stopped at the goal.

If each state has at most b successors and the best solution is d steps deep, BFS may store about b^d states. Iterative deepening runs depth-first searches with limits 0, 1, 2, … and gets BFS's fewest-steps answer with DFS's small memory.

Syntax

frontier = deque([start])           # BFS: popleft(); DFS: a list and pop(); UCS: heapq
parent = {start: None}
while frontier:
    state = frontier.popleft()
    if state == goal: break
    for nxt in successors(state):
        if nxt not in parent:
            parent[nxt] = state
            frontier.append(nxt)

Example

from collections import deque
import heapq

roads = {
    "Home": {"Mall": 2, "Park": 4},
    "Mall": {"Home": 2, "School": 5, "Bank": 10},
    "Park": {"Home": 4, "School": 1, "Lake": 7},
    "School": {"Park": 1, "Mall": 5, "Bank": 3, "Lake": 2},
    "Bank": {"Mall": 10, "School": 3, "Office": 4},
    "Lake": {"Park": 7, "School": 2, "Office": 6},
    "Office": {"Bank": 4, "Lake": 6},
}


def path_to(parent, goal):
    path = [goal]
    while parent[path[-1]]:
        path.append(parent[path[-1]])
    return path[::-1]


def breadth_first(start, goal):
    frontier, parent, order = deque([start]), {start: None}, []
    while frontier:
        town = frontier.popleft()
        order.append(town)
        if town == goal:
            return path_to(parent, goal), order
        for nxt in sorted(roads[town]):
            if nxt not in parent:
                parent[nxt] = town
                frontier.append(nxt)


def depth_first(start, goal):
    frontier, parent, order, seen = [start], {start: None}, [], set()
    while frontier:
        town = frontier.pop()
        if town in seen:
            continue
        seen.add(town)
        order.append(town)
        if town == goal:
            return path_to(parent, goal), order
        for nxt in sorted(roads[town], reverse=True):
            if nxt not in seen:
                parent[nxt] = town
                frontier.append(nxt)


def uniform_cost(start, goal):
    frontier, best, parent, order, done = [(0, start)], {start: 0}, {start: None}, [], set()
    while frontier:
        cost, town = heapq.heappop(frontier)
        if town in done:
            continue
        done.add(town)
        order.append(town)
        if town == goal:
            return path_to(parent, goal), order
        for nxt, step in roads[town].items():
            if nxt not in best or cost + step < best[nxt]:
                best[nxt], parent[nxt] = cost + step, town
                heapq.heappush(frontier, (cost + step, nxt))


for name, search in [("breadth-first", breadth_first), ("depth-first", depth_first), ("uniform-cost", uniform_cost)]:
    path, order = search("Home", "Office")
    km = sum(roads[a][b] for a, b in zip(path, path[1:]))
    print(f"{name}: {' -> '.join(path)} ({len(path) - 1} roads, {km} km)")
    print(f"    expanded: {', '.join(order)}")
Open in compiler

Line by line

  1. roads is the state space: each town, the towns it connects to, and the distances.
  2. BFS takes the oldest town first and finds a route with only three roads, but it is 16 km long.
  3. DFS dives along the first road each time; here it happens to find the same route while expanding only four towns.
  4. UCS takes the cheapest path first and finds Home → Park → School → Bank → Office: four roads, but only 12 km.
  5. Each "expanded" line shows the order in which the search took towns from its frontier.

Expected result

breadth-first: Home -> Mall -> Bank -> Office (3 roads, 16 km)
    expanded: Home, Mall, Park, Bank, School, Lake, Office
depth-first: Home -> Mall -> Bank -> Office (3 roads, 16 km)
    expanded: Home, Mall, Bank, Office
uniform-cost: Home -> Park -> School -> Bank -> Office (4 roads, 12 km)
    expanded: Home, Mall, Park, School, Lake, Bank, Office

In the real world

Map applications run fast variants of uniform-cost search over road networks with millions of junctions. Puzzle solvers, robot motion planners and network routing protocols such as OSPF use the same ideas. Web crawlers explore the link graph breadth-first so that they find pages close to the start first.

Common mistakes

  • Using BFS when actions have different costs: fewest steps is not cheapest.
  • Forgetting the explored set, so the search loops between two states forever.
  • Testing for the goal too early in UCS: a cheaper path may still be in the frontier, so test when a state is expanded.
  • Running DFS on an infinite or very deep state space without a depth limit.

Best practices

  • Write the five parts of the problem down before choosing an algorithm.
  • Use BFS for fewest steps, UCS for lowest cost, and iterative deepening when memory is tight.
  • Count the states expanded; it is the fairest way to compare searches.

Summary

A search problem has an initial state, actions, a transition model, a goal test and step costs. Searches keep a frontier and an explored set and differ only in which state they expand next: BFS (oldest, fewest steps), DFS (newest, little memory) and UCS (cheapest, lowest cost).

Quick check

1. Which data structure makes a search breadth-first?
2. Which search finds the cheapest route when roads have different lengths?
3. What does the explored set prevent?
4. Why did BFS return a longer route in kilometres than UCS?

Key takeaways

  • Every search is the same loop; the order in which it takes states from the frontier decides its behaviour.
  • Breadth-first search finds the fewest steps; uniform-cost search finds the lowest cost.
  • An explored set stops the search from revisiting states.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.