Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 40 ยท Applications

Graph Search and Planning in Prolog

Search graphs and state spaces in Prolog. Write paths with a visited list, breadth-first search with a queue, iterative deepening and weighted routes, then solve the water-jug puzzle as a planning problem.

Searching is what Prolog does best. Its execution model is already depth-first search with backtracking, so a graph, a maze or a puzzle can be written as a few facts and rules, and Prolog explores it for you. This lesson covers finding paths in a graph, the pitfalls (cycles, infinite loops), breadth-first search for shortest paths, and then planning: treating a puzzle as a graph whose nodes are states.

Prolog is not available on this site, so the runnable examples use the stand-in interpreter (a Python program that runs facts, rules, the cut, negation and findall/3); the programs themselves are ordinary Prolog.

A graph as facts

Represent a directed graph with one edge/2 fact per arrow:

PROLOG
edge(a, b).  edge(a, c).  edge(b, d).  edge(c, d).
edge(d, e).  edge(c, e).  edge(e, f).
flowchart LR
  a --> b
  a --> c
  b --> d
  c --> d
  d --> e
  c --> e
  e --> f

The example graph. There are three paths from a to f.

For an undirected graph, either store both directions or define a helper: link(X, Y) :- edge(X, Y). and link(X, Y) :- edge(Y, X).

Reachability and the cycle trap

The obvious definition of "there is a path" is:

PROLOG
reach(X, Y) :- edge(X, Y).
reach(X, Y) :- edge(X, Z), reach(Z, Y).

It works on an acyclic graph, but on one that contains a cycle, such as edge(x, y) and edge(y, x), a failing query reach(x, z) never terminates: Prolog keeps walking around the loop. The standard fix is to carry a list of visited nodes and never step onto one of them again:

PROLOG
path(X, Y, Path) :-
    walk(X, Y, [X], Rev),
    reverse(Rev, Path).

walk(X, X, Visited, Visited).
walk(X, Y, Visited, Path) :-
    edge(X, Z),
    \+ member(Z, Visited),
    walk(Z, Y, [Z|Visited], Path).

The visited list is built backwards (newest first), so the answer is reversed at the end. The test \+ member(Z, Visited) comes after edge(X, Z) has bound Z: generate first, then negate. On backtracking the predicate enumerates every simple path, in the order the facts are written, which is depth-first order.

Breadth-first search for shortest paths

Depth-first search finds a path, not the shortest. To find the path with the fewest edges, search breadth-first: keep a queue of partial paths and always extend the oldest first. Each partial path is stored with its newest node at the head:

PROLOG
bfs(Start, Goal, Path) :-
    bfs_queue([[Start]], Goal, Rev),
    reverse(Rev, Path).

bfs_queue([[Goal|T]|_], Goal, [Goal|T]) :- !.
bfs_queue([[N|T]|Rest], Goal, Path) :-
    findall([M, N|T], ( edge(N, M), \+ member(M, [N|T]) ), Next),
    append(Rest, Next, Queue),
    bfs_queue(Queue, Goal, Path).

findall/3 collects all one-step extensions of the first path, and append/3 puts them at the end of the queue, which is what makes the search breadth-first. The first time a path ends in the goal, it is a shortest one. If you put the new paths at the front instead, you get depth-first search with an explicit stack.

Python Depth-first and breadth-first paths (Python stand-in interpreter)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The depth-first query returns [a,b,d,e,f] first (it follows the first edge each time), while the breadth-first query returns [a,c,e,f], a path with only three edges.

Other search strategies

  • Iterative deepening runs depth-first search with a depth limit of 1, then 2, then 3, and so on. It finds shortest paths like breadth-first search but needs memory only for the current path. A short version uses length/2 to enumerate path lengths: length(Path, N), path_of_length(Path). SWI-Prolog also offers call_with_depth_limit/3.
  • Weighted graphs use edge(From, To, Cost). Keep the cost with each partial path, and pick the cheapest with keysort/2 or a priority queue: this is Dijkstra's algorithm, and with a heuristic estimate added it becomes A*.
  • Tabling (see Tabling and Performance) makes reach/2 terminate on cyclic graphs without a visited list, because Prolog remembers the answers it has already found.
  • Libraries such as ugraphs and assoc provide ready-made graph structures when you need more than a few facts.

A planning problem is a graph search in disguise. A state is a snapshot of the world, a move changes one state into another, and a plan is a path from the start state to any goal state. The only change from the graph code is that edge(X, Y) becomes move(State, NewState), which is defined by rules instead of facts.

The classic example: you have a 3-litre jug and a 5-litre jug and no measuring marks. How do you end up with exactly 4 litres in the big jug? A state is j(A, B), the litres in each jug. The moves are: fill a jug, empty a jug, or pour one into the other until the source is empty or the target is full.

PROLOG
move(j(A, B), j(3, B)) :- A < 3.                  % fill the small jug
move(j(A, B), j(A, 5)) :- B < 5.                  % fill the big jug
move(j(A, B), j(0, B)) :- A > 0.                  % empty the small jug
move(j(A, B), j(A, 0)) :- B > 0.                  % empty the big jug
move(j(A, B), j(A2, B2)) :-                       % pour small into big
    A > 0, B < 5, T is A + B,
    (   T > 5 -> B2 = 5, A2 is T - 5
    ;   B2 = T, A2 = 0 ).
move(j(A, B), j(A2, B2)) :-                       % pour big into small
    B > 0, A < 3, T is A + B,
    (   T > 3 -> A2 = 3, B2 is T - 3
    ;   A2 = T, B2 = 0 ).

goal(j(_, 4)).

Breadth-first search with a visited check over states solves it with the fewest moves:

Python Water jugs by breadth-first search (Python stand-in interpreter)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer is a path of seven states, six moves: fill the big jug, pour into the small one, empty the small one, pour the remaining 2 litres across, refill the big jug and top up the small one, which leaves 4 litres in the big jug. Longer solutions exist, but BFS always returns a shortest one first.

For larger problems, the same program structure works with a better strategy: depth-limited search, a heuristic function, or constraint solving (see CLP(FD) Puzzles) when the plan is better described by arithmetic constraints than by moves.

Common mistakes

  • Forgetting the visited check, and getting an infinite loop on a cyclic graph.
  • Putting \+ member(Z, Visited) before the goal that binds Z; the test then runs with an unbound variable and fails.
  • Using append/3 to add to the end of a long list inside a hot loop; fine for small queues, slow for large ones. Use difference lists or library(queues)-style structures when speed matters.
  • Counting a goal state as the end of the search without a cut, so BFS keeps producing longer solutions on backtracking.
  • Modeling states with too much information, which makes the visited check useless because no two states are ever equal.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does reach(X, Y) :- edge(X, Z), reach(Z, Y). loop on a cyclic graph?

    Without remembering visited nodes, depth-first search can follow a cycle endlessly when no path exists.
  2. 2. What makes bfs_queue breadth-first?

    Oldest partial paths are extended first, so shorter paths are always explored before longer ones.
  3. 3. Which search strategy does Prolog's own execution perform?

    Clauses and goals are tried top to bottom and left to right, with chronological backtracking.
  4. 4. In a planning model, what plays the role of edge/2?

    States are nodes and moves are edges, defined by rules rather than stored as facts.

Summary

  • A graph is a set of edge/2 facts; Prolog's backtracking already searches it depth-first.
  • Carry a visited list (and test with \+ member/2 after the node is bound) to avoid loops on cycles.
  • A queue of partial paths gives breadth-first search and shortest paths; iterative deepening and Dijkstra/A* extend the idea.
  • Planning is search in a state space: states are nodes, moves are edges, a plan is a path to a goal state.

Next: Meta-Interpreters and Expert Systems