Problem Solving in Prolog
Reference: Bratko chapter 12
Aim: 
To illustrate search in AI using a fairly wellknown example
problem. We also briefly introduce a number of different methods
for exploring a state space (or any other graph to be searched).

Keywords:
breadth first search,
depth first search,
edge in a graph,
goal state,
graph,
directed acyclic graphs,
trees,
binary trees,
adjacency matrices,
graph search algorithms,
initial state,
node,
operator,
state,
initial state,
goal state,
path,
search,
vertex

Plan: 
 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: depthfirst, breadthfirst

Problem solving has traditionally been one of the key areas of concern for
Artificial Intelligence. Below, we present a common problem and demonstrate a
simple solution.
Missionaries and Cannibals
 There are three missionaries and three cannibals on the left bank of a
river.
 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
cannibals' dinner!
 Plan a sequence of crossings that will take everyone safely accross.
This
kind of problem is often solved by a graph search method. We represent the
problem as a set of
 states
 which are snapshots of the world and
 operators
 which transform one state into another
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.
Graph Representation
A
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(5, 8).
edge(6, 4). edge(6, 5).
edge(7, 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).
 Start
 is the name of the starting node
 Finish
 is the name of the finishing node
 Visited
 is the list of nodes already visited.
 Path
 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]) :
edge(Start, X),
not(member(X, Visited)),
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
problem:
 A state is one "snapshot" in time.
 For this problem, the only information we need to fully characterise the
state is:
 the number of missionaries on the left bank,
 the number of cannibals on the left bank,
 the side the boat is on.
All other information can be deduced from these three items.
 In Prolog, the state can be represented by a 3arity 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
visited before.
 The visited list will have the form:
[MostRecent_State  ListOfPreviousStates]
Overview of Solution
 We follow a simple graph search procedure:
 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.
The search terminates whe we have found the state:
state(0, 0, right).
Toplevel Prolog Code
% mandc(CurrentState, Visited, Path)
mandc(state(0, 0, right), _, []).
mandc(CurrentState, Visited, [Move  RestOfMoves]) :
newstate(CurrentState, NextState),
not(member(NextState, Visited)),
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.
Possible Moves
 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:
carry(2, 0).
carry(1, 0).
carry(1, 1).
carry(0, 1).
carry(0, 2).
 where carry(M, C) means the boat will carry M
missionaries and C cannibals on one trip.
Feasible Moves
 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
Legal Moves
 Once we have found a feasible move, we must check that is legal.
 I.e. no missionaries must be eaten.
legal(X, X).
legal(3, X).
legal(0, X).
 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)) :
carry(M, C),
M <= M1,
C <= C1,
M2 is M1  M,
C2 is C1  C,
legal(M2, C2).
newstate(state(M1, C1, right), state(M2, C2, left)) :
carry(M, C),
M2 is M1 + M,
C2 is C1 + C,
M2 <= 3,
C2 <= 3,
legal(M2, C2).
The complete code, with instructions for use, is available at
http://www.cse.unsw.edu.au/~billw/cs9414/notes/mandc/mandc.pro
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 (preorder traversal):
a b d h e i j c f k g
 visiting the children first, then the node (postorder traversal):
h d i j e b k f g c a
 visiting some of the children, then the node, then the other children (inorder 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 bestfirst 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"
problem.
We also outlined depthfirst search, breadthfirst 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.