GPS

GeneralProblemSolver
Monkey and Banana
2013 Artificial Intelligence
Lecture no. 14
GeneralProblemSolver
人間の問題解決過程のモデル
与えられた知識 → 問題を解決
与えられた知識
Given Knowledge
•
•
•
•
初期状態(Initial State)
目的状態(target State)
オペレータ(operator)
状態表現(state
representation)
など
Monkey and Banana
How the monkey gets banana？
Needs to climb up on the box
状態表現(State Representaiton)
AT(A, X)
ON(A, X)
EMPTY
HOLD
A is at X
A is on X
Monkey’s HAND is EMPTY
Monkey HOLDS banana
初期状態(initial state),目的状態(target state)
AT(monkey, a)
AT(box, b)
EMPTY
Initial State
HOLD
(monkey holds banana)
Target State
Operators
GOTO(a)
Monkey goes to “a”
CLIMB
Monkey climbs up on the Box
PC前提条件
(none)
PC前提条件
AT(monkey, y),AT(box, y)
D削除リスト AT(monkey, x)
D削除リスト
AT(monkey, y)
A追加リスト AT(monkey, a)
A追加リスト
ON(monkey, box)
MOVEBOX(a) Monkey moves the box to
“a”
GRASP
バナナを掴む
PC前提条件
AT(box, c), ON(monkey,box)
D削除リスト AT(monkey, y) , AT(box, y)
D削除リスト
EMPTY
A追加リスト AT(monkey, a) AT(box, a)
A追加リスト
HOLD
PC前提条件
AT(monkey, y) ,AT(box, y)
問題解決How to solve the problem？
現在の状態(S)と目的状態(G)を近づける
S → G
S=G：同じ状態
Reduce
difference
=
G-S
Importance of Differences
D3 = distance between monkey and banana
Most important
D2= distance between the box and banana
Necessary to solve D3
D1 = distance between monkey and banana
Necessary to solve D2
importance D3 > D2 > D1
Operators to reduce distances
operators
distances
D1(monkey)
D2(box)
D3(monkey’s
hand)
GOTO
MOVEBOX
CLIMB
○
○
○
GRASP
○
○
GPS algorithm
1.LOOP1: if S satisfy then exit(S)
2.find D=most important difference between G & S
3.put all the operators to reduce D into oplist
4.LOOP2: if empty(oplist) then return(null)
5. operator:=first(oplist),
remove(operator, oplist),
pc := operatorの前提条件,
if not effective(operator) then goto LOOP2 :
give up, if operator fails to reduce d
6. if (pc = null) then goto APPLY
7. S1 = GPS(S, pc)
8. If S1=fail then goto LOOP2
9. APPLY : S := operator (S1)
10.goto LOOP1
GPS algorithm solves
“Monkey and Banana”
Introduction
AT(monkey, a)
AT(box, b)
EMPTY
Initial state S0
HOLD
Monkey gets banana
Final state G0
GPS(S0 , G0)
GPS(S0, G0)
Step 1:
Continue GPS unless S0=G0
Step 2:
Find differences between S0 and G0
D3 = |monkey – banana|
D2 = |box – banana|
D1 = |box – monkey|
D3 is most important!
GPS(S0, G0)
Step 3
Operator to reduce D3 is
GRASP
→
GRASP is put into oplist
Step 4
oplist is not empty
Continue GPS
GPS(S0, G0)
Step 5
operator = first(oplist),
first(oplist) is removed
from oplist,
pc
GRASP solves D !
GPS(S0, G0)
Step 6
Continue to Step 7
if pc exists
(if not, jump to
Step 9)
Step 7
GPS(S0, pc)
GPS(S0, G1)
Step 1
Continue GPS, unless
S0=G1
Step 2
Distances between S0& G1
D2 =|box - banana|
D1 = |monkey – box|
D2 is most important
GPS(S0, G1)
Step 3
D is solved by
MOVEBOX,
Put MOVEBOX into
oplist
Step 4
Continue GPS unless
oplist is empty
GPS(S0, G1)
Step 5
Substitute prerequisit conditions
into pc
AT(box, y), AT(monkey, y)}
where y=b is necessary to solve D2
pc = {AT(box, b), AT(monkey, b)}
Continue,
since MOVEBOX reduces D2
GPS(S0, G1)
Step 6
Continue to Step 7
since pc is not
empty
(if not, jump to
Step9)
Step 7
Run GPS(S0, pc)
GPS(S0, G2)
Step 1
Continue GPS unless
S0=G2
Step 2
Distance between S0
and G2
D1 =|monkey - box|
D1 is most important
GPS(S0, G2)
Step 3
Find operators to reduce D1す
and put them into oplist
GOTO and CLIMB are put into
oplist
Step 4
Continue GPS unless oplist
is empty
GPS(S0, G2)
Step 5
oplist = {CLIMB} , operator = GOTO
Prerequisit conditions of the
operator are substituted to pc
pc = (none)
GOTO reduces D1
Step 6
No more pc exist
Jump to Step 9
GPS(S0, G2) → GPS(S1, G2)
Step 9
Apply operator on S0
operator = GOTO(b)
New state S1
GPS(S1, G2) → GPS(S1, G1)
Step 10
Go to Step 1
Step 1
S0=G1
End GPS(S1, G2)
Go back to GPS(S1,
G1)
GPS(S1, G1) → GPS(S2, G1)
Step 8
Continue if S1 is not fail
Step 9
Apply operator on S1
operator = MOVEBOX(c)
New state S2
GPS(S2, G1)
Step10
Go to Step1
Step 1
Continue GPS unless
S0=G1
Step 2
Difference between S2and
G1
D1 =|monkey – box|
D1 is most important
GPS(S2, G1)
Step3
Operators to solve D1 are
GOTO and CLIMB
Add GOTO and CLIMB to
oplist
Step 4
Continue GPS unless
oplist is empty
GPS(S2, G1)
Step5
oplist = {CLIMB} , operator = GOTO
Substitute prerequisite
conditions to pc
pc = (none)
Go to Step 4, since
No operator can reduce D1
GPS(S2, G1)
Step 5
oplist = {} , operator = CLIMB
Substitute prerequisite
conditions of operators into pc
AT(box, y), AT(monkey, y)}
where y=c reduces D1
pc= {AT(box, c), AT(monkey, c)}
Continue since
CLIMB reduces D1
GPS(S2, G1)
Step 6
Continue since pc exists
Step 7
Run GPS(S2, pc)
GPS(S2, G3) → GPS(S2, G1)
Step1
S2=G3
GPS ends.
Go upwards
GPS(S2, G1) → GPS(S3, G1)
Step 8
Continue since S2 is not fail
Step 9
Apply operator on S1
operator = CLIMB
New state S3
GPS(S3, G1) → GPS(S3, G0)
Step 10
Go to Step 1
Step 1
S3=G1
Finish GPS
Go upwards.
GPS(S3, G0) → GPS(S4, G0)
Step8
Continue since S2 is not fail
Step 9
Apply operator on S1
operator = DRASP
New state S4
GPS(S4, G0)
Step10
Go to Step 1
Step 1
S4=G0
Finish GPS
End

Download Report