Problem Solving
One of our abilities of which we are most proud, is the ability to solve problems
the ability to invent a sequence of actions to achieve a goal, from some given situation
In some cases, the problems we tackle are natural everyday ones
Copyright By PowCoder代写 加微信 powcoder
• getting the keys out of a locked car • obtaining food for lunch
In other cases, we solve artificial problems purely for amusement
• Rubik’s cube
• word problems
Here, we will examine a class of problems that can be solved using a single general method
cps721 Artificial Intelligence © Problem Solving 1
Problem 1: Three Coins
Here is the first example:
Given 3 coins arranged as below, make them all the same (i.e. either all heads or all tails) using exactly 3 moves. By a move is meant flipping one of the coins over (so that a head becomes a tail, or a tail becomes a head)
Example moves: after
T T H cps721 Artificial Intelligence
flip left T H T
flip middle T H H
© Problem Solving 2
Problem 1: Solution
There are many solutions
• flip middle, HHH middle
• flip left, HHH right
flip right, HTH right
flip middle HTT
middle HHT start
• and so on.
General properties:
flip left, HHT
flip right
• all of them end up with HHH
– why? after 1 move have even # of T’s after 2 moves have odd # of T’s
after 3 moves have even # of T’s • all of them move the right coin 1 or 3 times
• those that move it 1 time, move another 2 times cps721 Artificial Intelligence © Problem Solving 3
Problem 2: Monkey
The monkey and bananas:
A monkey is in a room where a bunch of bananas is hanging from the ceiling, too high to reach. In the corner of the room is a box, which is not under the bananas. The box is sturdy enough to support the monkey if he climbs on it, and light enough so that he can move it easily.
If the box is under the bananas, and the monkey is on the box, he will be able to reach the bananas.
How can the monkey get the bananas?
Artificial Intelligence © Problem Solving 4
The monkey’s moves
What are the possible actions?
• go to anywhere in the room
provided that monkey is not on the box
• climb on the box
provided the monkey is at the box
• climb off the box
provided the monkey is on the box
• push the box anywhere
provided the monkey is at the box, but not on it
• grab the bananas
provided the monkey can reach the bananas
These lead to states like this: Nice try…
cps721 Artificial Intelligence © Problem Solving 5
Problem 2: Solution
Here is what the monkey needs to do:
grab the bananas
climb onto the box
push the box to under the bananas
go to where the box is
Artificial Intelligence ©
Problem Solving 6
States and operators
In general, problems of this form can be thought of as characterized by
• states: the configurations we pass through – what side each coin is showing
– locations of monkey, bananas, and box
• operators: ways of moving between states – flipping a coin
– climbing on a box
• initial state: the starting state(s) for a problem – HHT
– as per first picture of monkey and bananas
• goal state: the desired final state(s) – HHH or TTT
– any state where the monkey has the bananas
The problem is always the same:
find a way of going from an initial state to a goal state by applying a sequence of operators
cps721 Artificial Intelligence © Problem Solving 7
State Space
Generates a state space: the graph of all states
• label each node with the state it represents
• put an edge between S1 and S2 iff there is an operator that takes you from S1 to S2
– put an arrow on the edge to indicate direction – put a label on the edge to indicate the operator
flip middle
flip right
all edges are bi-directional
A problem: find a path in the graph from an initial state to a goal state
cps721 Artificial Intelligence © Problem Solving 8
Using Prolog
Would like to solve problems of this type using Prolog:
We tell it
the initial state, goal state, operators
It should tell us
a list of moves that solve the problem
It will have to reason about the problem
“ If I was in state S and I did move M, that would put me into state S ́. ”
“ I start in an initial state. I would like to end up in a goal state. ”
Along the way, it will need to keep track of the moves it needs to make.
cps721 Artificial Intelligence © Problem Solving 9
Getting to any state
For a state S to be reachable from an initial state, there are only two general rules:
1. if S is an initial state, then S is trivially reachable with no moves;
2. if the state S is reachable using moves [Mn, Mn-1, …, M1]
there is a move M which takes you
from state S to state S ́,
then state S ́ is reachable using moves
[M, Mn, Mn-1, …, M1].
new move at front of list
For example
the state HTH of the coin problem is reachable using moves [flip_right, flip_middle],
there is a move which goes from HTH to HHH: it’s M = flip_middle
the state HHH is reachable
using [flip_middle, flip_right, flip_middle]
last first
Artificial Intelligence © Problem Solving 10
A Prolog problem solver
The predicate reachable(S,L) means the state S is reachable using list of moves L
reachable(S,[]) :-
initial_state(S).
reachable(S1,[M|L]) :-
reachable(S,L),
legal_move(S1,M,S).
An initial state S is reachable and no moves are required
If S is reachable using moves L, and there is a legal move M from S to S1, then S1 is reachable using moves [M | L].
To solve a problem, we try to reach a goal state:
solve_problem(L) :- A problem is solvable using a list
reachable(S,L),
goal_state(S).
of moves L if some goal state S is reachable using L
This is a general problem solver. For each specific problem we only need to specify the predicates:
• initial_state(S)
• goal_state(S)
• legal_move(S1,M,S)
cps721 Artificial Intelligence © Problem Solving 11
Representing the 3 coins
States: [left coin, middle coin, right coin], where each has a value of h or t
Operators: flip_left, flip_middle, flip_right with the obvious effects
Initial state: [h,h,t] initial_state([h,h,t]).
Goal state: [h,h,h] or [t,t,t] goal_state([X,X,X]).
Legal moves: for each flip
S ́ S legal_move([X,Y,Z],flip_middle,[X1,Y1,Z1])
provided that X = X1,
Y and Y1 are flip sides, Z = Z1.
which gives us… Artificial Intelligence © Problem Solving 12
The 3 coin program: the general solver +
initial_state([h,h,t]).
goal_state([X,X,X]).
legal_move([X,Y,Z],flip_left,[X1,Y,Z]) :-
flip(X,X1).
legal_move([X,Y,Z],flip_middle,[X,Y1,Z]) :-
flip(Y,Y1).
legal_move([X,Y,Z],flip_right,[X,Y,Z1]) :-
flip(Z,Z1).
flip(h,t).
flip(t,h).
The query:
solve_problem([M3,M2,M1]).
The result:
M3 = flip_right
M2 = flip_left
M1 = flip_left
cps721 Artificial Intelligence ©
want exactly 3 moves
first move Problem Solving 13
Tracing the solver
reachable(S,[M3,M2,M1]),
goal_state(S)
reachable(Sa,[M2,M1])
legal_move(S,M3,Sa),
goal_state(S)
reachable(Sb,[M1]),
legal_move(Sa,M2,Sb),
legal_move(S,M3,Sa),
goal_state(S)
reachable(Sc,[]),
legal_move(Sb,M1,Sc),
legal_move(Sa,M2,Sb),
legal_move(S,M3,Sa),
goal_state(S)
initial_state(Sc),
legal_move(Sb,M1,Sc),
legal_move(Sa,M2,Sb),
legal_move(S,M3,Sa),
goal_state(S)
Sc= [h,h,t]
legal_move(Sb,M1,[h,h,t]),
legal_move(Sa,M2,Sb),
legal_move(S,M3,Sa),
goal_state(S)
Artificial Intelligence © Problem Solving 14
Tracing continued
M1=flip_left, Sb=[Xa,h,t]
flip(Xa,h),
legal_move(Sa,M2,[Xa,h,t]),
legal_move(S,M3,Sa),
goal_state(S)
legal_move(Sa,M2,[t,h,t]),
legal_move(S,M3,Sa),
goal_state(S)
M2=flip_left, Sa=[Xb,h,t]
flip(Xb,t),
legal_move(S,M3,[Xb,h,t]),
goal_state(S)
legal_move(S,M3,[h,h,t]),
goal_state(S)
M3=flip_left, S=[X,h,t]
M3=flip_middle, S=[h,Y,t]
flip(X,h),
goal_state([X,h,t])
M3=flip_right, S=[h,h,Z]
flip(Z,t),
goal_state([h,h,Z])
goal_state([h,h,h])
goal_state([t,h,t])
flip(Y,h),
goal_state([h,Y,t])
Y=t goal_state([h,t,t])
cps721 Artificial Intelligence ©
Problem Solving 15
Execution notes
The Prolog program solve_problem works in two phases:
• first it reduces the problem to a number of legal_move subgoals using reachable
solve_problem([M3,M2,M1])
initial_state(S1),
legal_move(S2,M1,S1),
legal_move(S3,M2,S2),
legal_move(S,M3,S3),
goal_state(S)
• then it selects an initial state and tries to find appropriate legal moves from there to the goal
The list returned by solve_problem shows the moves in reverse order: the first element of the list is the one closest to the goal
When testing your own programs, it is a very good idea to make sure that reachable works correctly with intermediate states, close to an initial state.
e.g. reachable([h,h,h],[M]) reachable([t,h,h],[M2,M1])
cps721 Artificial Intelligence © Problem Solving 16
Getting bananas in Prolog
States: [bananas, monkey, box, OnBox?, HasBananas?]
where first 3 are locations and last 2 are y/n
For simplicity, assume 4 locations:
loc1, loc2, loc3, loc4
Operators: climb_on, climb_off, grab, go(X), push(X).
The program:
initial_state([loc3,loc4,loc1,n,n]).
goal_state([_,_,_,_,y]).
legal_move([B,L,L,y,H],climb_on,[B,L,L,n,H]).
legal_move(S1,climb_off,S) :-
legal_move(S,climb_on,S1).
legal_move([L,L,L,y,y],grab,[L,L,L,y,n]).
legal_move([B,X,L,n,H],go(X),[B,M,L,n,H]) :-
loc(X), not(X=M).
legal_move([B,X,X,n,H],push(X),[B,M,M,n,H]) :-
loc(X), not(X=M).
loc(loc1). loc(loc2). loc(loc3). loc(loc4).
cps721 Artificial Intelligence © Problem Solving 17
Banana queries
Responses to queries:
solve_problem([M3,M2,M1]).
solve_problem([M4,M3,M2,M1]).
no 3 step solution
a unique 4 step solution
several 5 step solutions
M3 = climb_on M2 = push(loc3) M1 = go(loc1) ;
first move
solve_problem([M5,M4,M3,M2,M1]).
M4 = climb_on M3 = push(loc3) M2 = push(loc2) M1 = go(loc1) ;
… (many other solutions) Can also do:
solve_problem(L).
L = [grab,climb_on,push(loc3),go(loc1)]. yes
cps721 Artificial Intelligence © Problem Solving 18
A rough trace
is there a 0 move solution?
is there a 1 move solution?
is there a 2 move solution?
is there a 3 move solution?
is there a 4 move solution?
initial_state(G),
goal_state(G)
initial_state(S1),
legal_move(G,A1,S1),
goal_state(G)
initial_state(S2),
legal_move(S1,A2,S2),
legal_move(G,A1,S1),
goal_state(G)
initial_state(S3),
legal_move(S2,A3,S3),
legal_move(S1,A2,S2),
legal_move(G,A1,S1),
goal_state(G)
initial_state(S4),
legal_move(S3,A4,S4),
legal_move(S2,A3,S3),
legal_move(S1,A2,S2),
legal_move(G,A1,S1),
goal_state(G)
reachable(G,L),
goal_state(G)
reachable(S1,L1),
legal_move(G,A1,S1),
goal_state(G)
reachable(S2,L2),
legal_move(S1,A2,S2),
legal_move(G,A1,S1),
goal_state(G)
reachable(S3,L3),
legal_move(S2,A3,S3),
legal_move(S1,A2,S2),
legal_move(G,A1,S1),
goal_state(G)
reachable(S4,L4),
legal_move(S3,A4,S4),
legal_move(S2,A3,S3),
legal_move(S1,A2,S2),
legal_move(G,A1,S1),
goal_state(G)
eventually succeeds …
cps721 Artificial Intelligence ©
Problem Solving 19
Warning: unbounded search
As can be seen, the predicate reachable first looks for solutions of length 0, then 1, then 2, then 3, etc.
This means that it will run forever if there happens to be no sequence of moves that works!
So it is much safer to first bound the length of the list. We can write a predicate max_length(L,N) that
holds when the length of list L is not more than N. max_length([],N).
max_length([_|L],N1) :-
N is N1-1,
max_length(L,N).
Then we get:
max_length(X,2).
X = [_4526] ;
X = [_4526,_4531] ; no
And so we can use
max_length(L,7), solve_problem(L).
L = [grab,climb_on,push(loc3),go(loc1)]
cps721 Artificial Intelligence © Problem Solving 20
Reversing a list
How about listing the actions in the “correct” order? We define a predicate reverse(L1,L2) to mean that
L2 has the elements of L1 in reverse order.
This is most easily defined using an auxiliary predicate rev(L1,L2,L3) which holds when L3 is made up of the elements of L1 in reverse order followed by those of L2 in regular order
reverse(L1,L2) :- rev(L1,[],L2).
rev([],L,L).
rev([X|L1],L2,L3) :- rev(L1,[X|L2],L3).
reverse([1,2,3], L) rev([1,2,3], [ ], L) rev([2,3], [1], L) rev([3], [2,1], L)
rev([ ], [3,2,1], L) L = [3,2,1]
Then we pose a query like:
solve_problem(L), reverse(L,In_order).
cps721 Artificial Intelligence © Problem Solving 21
Next problem: 15-puzzle
The 15-puzzle consists of 15 consecutively numbered tiles located in a 4 × 4 grid. The object of the puzzle is to move the tiles within the grid so that each tile ends up at its correct location, as shown:
initial state This can be handled in Prolog as before:
• States: [pos1, pos2, pos3, …, pos16]
where each posi is the number of the tile in that
position in the grid: 0 ! posi ! 15
pos5 = 10 means position 5 has tile 10
pos12 = 0 means position 12 is vacant goal state: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
initial state: [1,6,3,8,10,2,7,15,13,5,4,0,9,14,11,12] • Operators: move a tile up, down, left, or right
assuming the vacant spot is adjacent
cps721 Artificial Intelligence © Problem Solving 22
goal state
Simplified program
Here is the program for the 2 × 3 version of the puzzle initial_state([0,1,5,4,3,2]).
goal_state([1,2,3,4,5,0]).
legal_move([C,A,B,0,D,E],up(C),[0,A,B,C,D,E]).
legal_move([A,D,B,C,0,E],up(D),[A,0,B,C,D,E]).
legal_move([A,B,E,C,D,0],up(E),[A,B,0,C,D,E]).
legal_move(S1,down(X),S2) :-
legal_move(S2,up(X),S1).
legal_move([A,0,B,C,D,E],left(A),[0,A,B,C,D,E]).
legal_move([A,B,0,C,D,E],left(B),[A,0,B,C,D,E]).
legal_move([A,B,C,D,0,E],left(D),[A,B,C,0,D,E]).
legal_move([A,B,C,D,E,0],left(E),[A,B,C,D,0,E]).
legal_move(S1,right(X),S2) :-
legal_move(S2,left(X),S1).
For which we get:
solve_problem(L).
L = [left(5), up(2), right(3), down(5), left(2), up(3), left(1)] .
first move
Artificial Intelligence © Problem Solving 23
Scaling up?
As the problem to be solved becomes more and more complex, two difficulties arise:
1. Representation of state
It becomes increasingly awkward and inefficient to
deal with explicit states and the legal_move predicate. state: [aspect1, aspect2, … aspect10000]
Although all the aspects of a state can be changed by some operator, each operator only changes a very small number of them.
sliding a box under the bananas does not affect the position of the bananas, the color of the box, whether or not the window is open, objects in other rooms, …, the current Prime Minister, the price of tea in China, ….
2. Searching
Blindly searching (in phase two) for n moves becomes infeasible.
the number of states that may need to be examined grows exponentially in the number of required moves n
legal_move( ), …, legal_move( )
We’ve been lucky so far!
… … … Artificial Intelligence © Problem Solving 24
Search strategy 1
Many problems have a natural notion of sub- problem that can be solved independently and then combined
15-puzzle:
first goal next final goal
Why does this help?
Suppose a problem can be partitioned into
subproblems A and B such that A can be solved in 15 moves
B can be solved in 10 moves
so that 25 moves are sufficient overall.
solve each subproblem independently: 215 + 210 ” 33,000 states, at worst
vs. solve the problem directly:
225 ” 33,000,000 states, at worst
Assuming just two possible moves at each choice point
Artificial Intelligence © Problem Solving 25
Search strategy 2
The search strategy we’ve been using so far:
• for state S, choose a legal move: get new S#
• check to see if remaining moves can be found • if that fails, choose another legal move: get S##
initial state
goal state A better strategy: best-first search
• keep a big list of all states that have yet to be explored in the search (and how we got there)
• at the next step, find the legal moves for the most promising state on the list
• add these new states to the list
Need to determine most promising states cps721 Artificial Intelligence © Problem Solving 26
possibly the entire tree below S# will be explored before even looking at what is below S##
this is depth-first search …
Estimating the value of a state
Many problems have a natural measure that can be used to estimate how far a state is from a goal state.
Then, the most “promising” state during the search is the one which, according to the estimate, is the closest to a goal state.
For example, in the 15-puzzle, we can use the “Manhattan distance” to the goal state
For each tile, the minimum number of vertical and horizontal moves required to move the tile from where it is now to the goal state
Then sum over every tile
dist for tile 6 is 3 moves
This number is easy to calculate and is a lower bound on how many moves will actually be required from an initial state.
It is only a lower bound, since tiles get in the way of each other
cps721 Artificial Intelligence © Problem Solving 27
Much of the reasoning research in AI has centered around planning
problem solving (of the sort we have seen) where the moves are physical actions to be carried out by an autonomous agent / robot
Typical use:
• present a planning problem: some goal we are interested in achieving
• solve the problem: find a sequence of actions that achieves the goal
• send the actions to the robot for execution However, it is not feasible in practice to use
the representation of a state as an explicit list
• in typical planning problems, there are too many objects with too many properties to list them all in each clause of legal_move
• we want to use the fact that most objects are unaffected by most actions!
cps721 Artificial Intelligence © Problem Solving 28
A representation strategy
The purpose of a state is to track various aspects of the world affected by actions
• the action climb_on changes the OnBox? aspect of the state from n to y
• the action push(X) changes the box location to X When it is too awkward to enumerate all the aspects of
a state in a big list, there is another possible strategy:
• just keep track of what actions were performed from the initial state to get to the current state
• calculate what holds in a state as needed
this will depend on
• what actions were performed (in what order)
• what was true initially
For example, suppose we want to know the location of the box given only a list of the actions performed so far
• if push(X) is the most recent push action in the list, then the box is located at that X
• if there is no push(X) action, then the box is located wherever it was initially
cps721 Artificial Intelligence © Problem Solving 29
Situations and fluents
A list of actions used to represent a state is called a situation
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com