Problem Solving and Search in AI

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

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 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 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).

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

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

must be true.

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