| 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: |
|
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.
- states
- which are snapshots of the world and
- operators
- which transform one state into another
Graph Representation
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.
- 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.
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
| 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. |
Copyright (C) Bill Wilson, 2002, except where another source is acknowledged.
http://www.cse.unsw.edu.au/~billw/cs9414/notes/mandc/mandc.html
No comments:
Post a Comment