Problem Solving in Prolog

Reference: Bratko chapter 12

Aim:
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).
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: 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 simple solution.

Missionaries and Cannibals

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

	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

	path(Node, Node, _, [Node]).

	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:
	state(Missionaries, Cannibals, Side)

Representing the Solution

	[move(1, 1, right), move(2, 0, left)]

	[MostRecent_State | ListOfPreviousStates]

Overview of Solution

	state(0, 0, right).

Top-level 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

	carry(2, 0).
	carry(1, 0).
	carry(1, 1).
	carry(0, 1).
	carry(0, 2).

Feasible Moves

	M <= M1 and C <= C1

	M + M1 <= 3 and C + C1 <= 3

Legal Moves

	legal(X, X).
	legal(3, X).
	legal(0, X).

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:

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" problem.
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.