Problem Solving in Prolog
Reference: Bratko chapter 12
To illustrate search in AI using a fairly well-known example
problem. We also briefly introduce a number of different methods
for exploring a state space (or any other graph to be searched).
breadth first search,
depth first search,
edge in a graph,
directed acyclic graphs,
graph search algorithms,
- states, operators and searching
- representing state spaces using graphs
- finding a path from A to B in a graph
- missionaries & cannibals: representing states & operators
- methods of search: depth-first, breadth-first
Problem solving has traditionally been one of the key areas of concern for
Artificial Intelligence. Below, we present a common problem and demonstrate a
Missionaries and Cannibals
- There are three missionaries and three cannibals on the left bank of a
- They wish to cross over to the right bank using a boat that can only carry
two at a time.
- The number of cannibals on either bank must never exceed the number of
missionaries on the same bank, otherwise the missionaries will become the
- Plan a sequence of crossings that will take everyone safely accross.
kind of problem is often solved by a graph search method. We represent the
problem as a set of
States can be mapped to nodes of a graph and operators are the edges of the
graph. Before studying the missionaries and cannibals problem, we look at a
simple graph search algorithm in Prolog. the missionaries and cannibals program
will have the same basic structure.
- which are snapshots of the world and
- which transform one state into another
graph may be represented by a set of edge predicates and a list of vertices.
edge(1, 5). edge(1, 7).
edge(2, 1). edge(2, 7).
edge(3, 1). edge(3, 6).
edge(4, 3). edge(4, 5).
edge(6, 4). edge(6, 5).
edge(8, 6). edge(8, 7).
vertices([1, 2, 3, 4, 5, 6, 7, 8]).
Finding a path
- Write a program to find path from one node to another.
- Must avoid cycles (i.e. going around in circle).
- A template for the clause is:
path(Start, Finish, Visited, Path).
- is the name of the starting node
- is the name of the finishing node
- is the list of nodes already visited.
- is the list of nodes on the path, including Start and Finish.
The Path Program
- The search for a path terminates when we have nowhere to go.
path(Node, Node, _, [Node]).
- A path from Start to Finish starts with a node, X, connected to Start
followed by a path from X to Finish.
path(Start, Finish, Visited, [Start | Path]) :-
path(X, Finish, [X | Visited], Path).
Here is an example of the path algorithm in action.
Representing the state
Now we return to the problem of representing the missionaries anc cannibals
- A state is one "snapshot" in time.
- For this problem, the only information we need to fully characterise the
All other information can be deduced from these three items.
- the number of missionaries on the left bank,
- the number of cannibals on the left bank,
- the side the boat is on.
- In Prolog, the state can be represented by a 3-arity term,
state(Missionaries, Cannibals, Side)
Representing the Solution
- The solution consists of a list of moves, e.g.
[move(1, 1, right), move(2, 0, left)]
- We take this to mean that 1 missionary and 1 cannibal moved to the right
bank, then 2 missinaries moved to the left bank.
- Like the graph search problem, we must avoid returning to a state we have
- The visited list will have the form:
[MostRecent_State | ListOfPreviousStates]
Overview of Solution
- We follow a simple graph search procedure:
The search terminates whe we have found the state:
- Start from an initial state
- Find a neighbouring state
- Check that the new state has not been visited before
- Find a path from the neighbour to the goal.
state(0, 0, right).
Top-level Prolog Code
% mandc(CurrentState, Visited, Path)
mandc(state(0, 0, right), _, ).
mandc(CurrentState, Visited, [Move | RestOfMoves]) :-
make_move(CurrentState, NextState, Move),
mandc(NextState, [NextState | Visited], RestOfMoves]).
make_move(state(M1, C1, left), state(M2, C2, right), move(M, C, right)) :-
M is M1 - M2,
C is C1 - C2.
make_move(state(M1, C1, right), state(M2, C2, left), move(M, C, left)) :-
M is M2 - M1,
C is C2 - C1.
- A move is characterised by the number of missionaries and the number of
cannibals taken in the boat at one time.
- Since the boat can carry no more than two people at once, the only
possible combinations are:
- where carry(M, C) means the boat will carry M
missionaries and C cannibals on one trip.
- Once we have found a possible move, we have to confirm that it is feasible.
- I.e. it is not feasible to move more missionaries or more cannibals than
are present on one bank.
- When the state is state(M1, C1, left) and we try carry(M, C) then
M <= M1 and C <= C1
- must be true.
- When the state is state(M1, C1, right) and we try
carry(M, C) then
M + M1 <= 3 and C + C1 <= 3
- Once we have found a feasible move, we must check that is legal.
- I.e. no missionaries must be eaten.
- The only safe combinations are when there are equal numbers of
missionaries and cannibals or all the missionaries are on one side.
Generating the next state
newstate(state(M1, C1, left), state(M2, C2, right)) :-
M <= M1,
C <= C1,
M2 is M1 - M,
C2 is C1 - C,
newstate(state(M1, C1, right), state(M2, C2, left)) :-
M2 is M1 + M,
C2 is C1 + C,
M2 <= 3,
C2 <= 3,
The complete code, with instructions for use, is available at
Methods of Search
In the preceding example, the state space is explored in an order determined
by Prolog. In some situations, it might be necessary to alter that order
of search in order to make search more efficient. To see what this might
mean, here are two alternative methods of searching a tree.
Depth first search begins by diving down as quickly as possible to the leaf
nodes of the tree. Traversal can be done by:
- visiting the node first, then its children (pre-order traversal):
a b d h e i j c f k g
- visiting the children first, then the node (post-order traversal):
h d i j e b k f g c a
- visiting some of the children, then the node, then the other children (in-order traversal)
h d b i e j a f k c g
There are many other search methods and variants on search methods.
We do not have time to cover these in COMP9414, but you can find out
about some of them in the text by Bratko. For example, chapter 12
deals with best-first search.
|Summary: Problem Solving and Search in AI|
We introduced the concepts of states and operators and gave a
graph traversal algorithm that can be used as a problem solving tool.
We applied this to solve the "missionaries and cannibals"
We also outlined depth-first search, breadth-first search, and alluded
to the existence of a range of other search methods.
CRICOS Provider Code No. 00098G
Copyright (C) Bill Wilson, 2002, except where another source is acknowledged.