Russel and Norvig, Chapter 11 L. Manevitz, Slide Presentasi, http://www.cs.uiowa.edu
LSR, AI: IK103
12/11/2009
1
The blocks world problem
Initial State
•
Goal
Bagaimana mendapatkan goal dari initial state ?
LSR, AI: IK103
12/11/2009
2
LSR, AI: IK103
12/11/2009
3
•
•
•
Planning adalah metode yang telah dipikirkan secara detail sebelum menyelesaikan suatu pekerjaan. Misalkan: ide atau metode untuk mengalahkan tim lawan dalam pertandingan sepakbola. Planning is action or process of making plans for something. Planning penting untuk solusi yang tidak dapat dibalik kembali (undo).
LSR, AI: IK103
12/11/2009
4
Planning adalah kasus khusus dari searching. Pada searching, pelacakan dilakukan dari initial state ke goal state dengan mengikuti path yang ada. Path yang merupakan solusi adalah sebuah plan langkah dari initial ke goal state. Sedangkan pada planning, tidaklah harus masalah itu dipecahkan dari initial ke goal state, tetapi dapat juga dengan memecahkan subgoal. LSR, AI: IK103
12/11/2009
5
STRIPS (STanford Research Institute Planning System-1971 by Fikes and Nilsson)
Goal Stack Planning Constraint Posting NOAH etc
LSR, AI: IK103
12/11/2009
6
• •
• • •
Memilih rule terbaik berdasarkan informasi heuristik yang tersedia. Mengimplementasikan rule yang dipilih dan menghitung masalah yang muncul dari implementasi ini. Mendeteksi ketika solusinya tidak ditemukan. Mendeteksi jalan buntu(dead end) sehingga bisa menghindarinya. Mendeteksi ketika hampir ditemukan solusi dan menggunakan metode khusus untuk benar-benar menemukan solusi. LSR, AI: IK103
12/11/2009
7
Pertama, mendeteksi/mengumpulkan perbedaan antara goal dan initial dan kemudian mengidentifikasi rule yang relevan untuk mengurangi perbedaan ini. Jika terdapat beberapa rule yang dapat dipilih, maka gunakan informasi heuristik untuk memilih diantara mereka.
LSR, AI: IK103
12/11/2009
8
Setiap rule yang akan diimplementasikan akan memberikan kondisi yang baru/perubahan. Kita harus bisa mengidentifikasi - kondisi yang harus dipenuhi untuk menjalankan rule tertentu. - Akibat dari menjalankan suatu rule tertentu.
LSR, AI: IK103
12/11/2009
9
Planning sistem dikatakan menemukan solusi jika telah menemukan sequence operasi dari initial state ke goal state.
LSR, AI: IK103
12/11/2009
10
Jika perubahan yang dihasilkan setelah iterasi cukup lama, tidak signifikan untuk mengurangi perbedaan antara initial dgn goal. Jika kita menggunakan metode forwardchaining: operasi menuju suatu state yang tidak dapat dicapai oleh operasi dari goal state. Jika metode backward: sebaliknya.
LSR, AI: IK103
12/11/2009
11
Jika masalah tersebut dapat didekomposisi(dipecah-pecah) maka solusi tiap subbagian telah ditemukan maka solusi masalah merupakan gabungannya.
LSR, AI: IK103
12/11/2009
12
•
• • •
Metode ini menggunakan satu stack yang mengandung goal dan operator yang diusulkan untuk mencapai goal. Adanya set operator yang mendeskripsikan daftar PRECONDITION, ADD, dan DELETE. Jika goal lebih dari satu, metode ini akan memecahkan goal satu persatu. Solusi yang diperoleh yaitu sequence operator dari goal pertama kemudian diikuti oleh sequence operator goal kedua dan seterusnya.
LSR, AI: IK103
12/11/2009
13
Setiap langkah adalah untuk menemukan goal pada stack teratas. Kemudian diikuti oleh goal dibawahnya sampai semua goal telah dipenuhi. Jika terdapat komponen goal yang tidak dipenuhi maka bagian yang salah dari goal dikembalikan ke dalam stack dan proses dilanjutkan kembali.
LSR, AI: IK103
12/11/2009
14
Initial State
Goal
Langkah: 1. Mendefinisikan Operator apa saja. 2. Spesifikasi/Deskripsi Operator (PRECONDITION, ADD dan DELETE). 3. Pendefinisikan Initial dan Goal state. 3. Membuat Stack 4. Implementasi Operator dan menemukan goal LSR, AI: IK103
12/11/2009
15
Operators: ◦ UNSTACK(A,B) – Pick up block A from its current position on block B. The arm must be empty and block A must have no blocks on top of it. ◦ STACK(A,B) – Place block A on block B. The arm must already be holding A and the surface of B must be clear.
LSR, AI: IK103
12/11/2009
16
◦ PICKUP(A) – Pick up block A from the table and hold it. Te arm must be empty and there must be nothing on top of block A. ◦ PUTDOWN(A) – Put block A down on the table. The arm must have been holding block A.
LSR, AI: IK103
12/11/2009
17
Predicates: (Kondisi) ◦ ON(A,B) – Block A is on block B. ◦ ONTABLE(A) – Block A is on the table. ◦ CLEAR(A) – There is nothing on top of block A. ◦ HOLDING(A) – The arm is holding block A. ◦ ARMEMPTY – The arm is holding nothing.
LSR, AI: IK103
12/11/2009
18
Inference rules: ◦ [ x : HOLDING(x)]
◦
x : ONTABLE(x)
◦
x:[
y : ON(y,x)]
ARMEMPTY
y : ON(x,y) CLEAR(x)
LSR, AI: IK103
12/11/2009
19
A
B
ON(A,B) ONTABLE(B) CLEAR(A)
LSR, AI: IK103
12/11/2009
20
PRECONDITION: daftar predicate yang harus benar sebelum suatu operator dipilih. ADD: daftar predicate baru (bernilai true) setelah operator diimplementasikan. DELETE: daftar operator lama yang ketika operator yang diimplementasikan salah.
LSR, AI: IK103
12/11/2009
22
STACK(A, B): P: CLEAR(B) HOLDING(A) D: CLEAR(B) HOLDING(A)
A: ARMEMPTY ON(A, B) UNSTACK(A, B): P: ON(A, B) CLEAR(A) ARMEMPTY
PICKUP(A): P: CLEAR(A) ONTABLE(A) ARMEMPTY D: ONTABLE(A) ARMEMPTY A: HOLDING(A) PUTDOWN(A):
P: HOLDING(A)
D: ON(A, B) ARMEMPTY
D: HOLDING(A)
A: HOLDING(A) CLEAR(B)
A: ONTABLE(A) ARMEMPTY
LSR, AI: IK103
12/11/2009
23
Initial State
start: ON(B, A) ONTABLE(A) ONTABLE(C) ONTABLE(D) ARMEMPTY
Goal
goal: ON(C, A) ON(B, D) ONTABLE(A) ONTABLE(D) ARMEMPTY
ON(A,B): Balok A menempel diatas balok B ONTABLE(A): Balok A berada dipermukaan meja CLEAR(A): Tidak ada balok yg sedang menempel di A ARMEMPTY: Robot tidak sedang memegang balok LSR, AI: IK103
12/11/2009
24
Stack
Database
Goals
Operators to satisfy the Goals
Current situation
+
Specification of Operators/Actions
LSR, AI: IK103
12/11/2009
25
Kondisi yang mungkin terjadi: a). Kondisi 1: jika slot berisi kondisi yang sudah memenuhi current state, tetapi slot ini terletak diatas operator maka, slot diambil dari stack dan pemeriksaan dilanjutkan pada slot berikutnya. b). Kondisi 2: Operator yang memenuhi suatu kondisi, dimasukkan ke dalam stack.
LSR, AI: IK103
12/11/2009
26
c). Kondisi 3: jika slot yang diperiksa adalah slot paling dasar, maka uji kesamaan antara current state dan goal state. Jika sama berarti solusi tercapai.
LSR, AI: IK103
12/11/2009
27
1)
Initial goal stack:
ON(C,A)Λ ON(B,D)Λ ONTABLE(A)Λ ONTABLE(D)
Initial State
Goal
LSR, AI: IK103
12/11/2009
28
2)
Choose to work on ON(C,A) before ON(B,D):
ON(C,A) ON(B,D) ON(C,A)Λ ON(B,D)Λ OTAD
Initial State
Goal
LSR, AI: IK103
12/11/2009
29
3)
Achieve ON(C,A) with STACK(C,A):
ON(C,A) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD
Initial State
Goal
LSR, AI: IK103
12/11/2009
30
4)
Add STACK’s preconditions:
CLEAR(A) HOLDING(C) CLEAR(A) HOLDING(C) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD
Initial State
GoalLSR, AI: IK103
12/11/2009
31
5)
Achieve CLEAR(A) with UNSTACK(B,A):
ON(B,A) CLEAR(B) ARMEMPTY ON(B,A) CLEAR(B) ARMEMPTY UNSTACK(B,A) CLEAR(A) HOLDING(C) CLEAR(A) HOLDING(C) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD Initial State
Goal
LSR, AI: IK103
12/11/2009
32
6)
Pop satisfied predicates:
ON(B,A) CLEAR(B) ARMEMPTY ON(B,A) CLEAR(B) ARMEMPTY UNSTACK(B,A) HOLDING(C) CLEAR(A) HOLDING(C) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD Initial State
Goal
LSR, AI: IK103
12/11/2009
33
7)
Achieve HOLDING(C) with UNSTACK(C,x):
ON(C,x) CLEAR(C) ARMEMPTY ON(C,x) CLEAR(C) ARMEMPTY UNSTACK(C,x) HOLDING(C) CLEAR(A) HOLDING(C) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD Initial State
Goal LSR, AI: IK103
12/11/2009
34
8)
Achieve ON(C,x) by STACK(C,x): CLEAR(x) HOLDING(C) CLEAR(x) HOLDING(C) ON(C,x) STACK(C,x) CLEAR(C) ARMEMPTY ON(C,x) CLEAR(C) ARMEMPTY UNSTACK(C,x) CLEAR(A) HOLDING(C) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD Initial State
Goal LSR, AI: IK103
12/11/2009
35
9)
Terminate path because HOLDING(C) is duplicated. CLEAR(x) HOLDING(C) CLEAR(x) HOLDING(C) STACK(C,x) CLEAR(C) ARMEMPTY ON(C,x) CLEAR(C) ARMEMPTY UNSTACK(C,x) CLEAR(A) HOLDING(C) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD Initial State
Goal LSR, AI: IK103
12/11/2009
36
10)
Achieve HOLDING(C) with PICKUP, not UNSTACK:
ONTABLE(C) CLEAR(C) ARMEMPTY ONTABLE(C) CLEAR(C) ARMEMPTY PICKUP(C) CLEAR(A) HOLDING(C) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD Initial State
Goal
LSR, AI: IK103
12/11/2009
37
11)
Pop ONTABLE(C) and CLEAR(C), and achieve ARMEMPTY by STACK(B,D): CLEAR(D) ONTABLE(C) HOLDING(B) CLEAR(C) HOLDING(B) CLEAR(D) ARMEMPTY STACK(B,D) ONTABLE(C) CLEAR(C) ARMEMPTY PICKUP(C) CLEAR(A) HOLDING(C) STACK(C,A) ON(B,D) ON(C,A) ON(B,D) OTAD
Initial State
Goal
LSR, AI: IK103
12/11/2009
38
12)
Pop entire stack, and return plan: i. ii. iii. iv.
UNSTACK(B,A). STACK(B,D). PICKUP(C). STACK(C,A).
Initial State
Goal LSR, AI: IK103
12/11/2009
39
1. 2. 3.
Tempatkan seluruh kondisi goal-state pada slot stack paling bawah. Masukkan setiap kondisi goal state yang belum tercapai ke dalam sebuah slot stack. Loop Keluarkan kondisi yang sudang dicapai dari dalam stack. Ganti kondisi yang belum tercapai dengan operator yang sesuai. Pindahkan operator yang bisa diaplikasikan kedalam rencana penyelesaian. Cek apakah current-state == goal state. if current state == goal state then sukses end end LSR, AI: IK103
12/11/2009
40
LSR, AI: IK103
12/11/2009
41
LSR, AI: IK103
12/11/2009
42
LSR, AI: IK103
12/11/2009
43
LSR, AI: IK103
12/11/2009
44
LSR, AI: IK103
12/11/2009
45
LSR, AI: IK103
12/11/2009
46
LSR, AI: IK103
12/11/2009
47
LSR, AI: IK103
12/11/2009
48
NOAH plans by developing a hierarchy of subgoals. The procedural net contains several levels of representation of a plan, each level more detailed than the previous one. For example: the node representing the abstract goal make coffee may be expanded to : grind coffee, boil water, put the coffee in a filter, pour the water through it.
LSR, AI: IK103
12/11/2009
49
LSR, AI: IK103
12/11/2009
50
We’ll use NOAH to solve the blocks problem. The operators used in this example are slightly different from those we have been using . STACK – will put any object on any other (including the table), provided that both objects are clear. It includes the picking up of the object to be moved.
LSR, AI: IK103
12/11/2009
51
A reminder of the problem : A C A
B B
Start: ON(C,A) ONTABLE(A)
C
Goal: ON(A,B) ON(B,C)
ONTABLE(B)
ARMEMPTY LSR, AI: IK103
12/11/2009
52
The initial state of the problem solver:
(ON(A,B) ON(B,C))
Level 1
LSR, AI: IK103
12/11/2009
53
The first thing that it does is to divide the problem into two subproblems: ON(A,B) S
J
Level 2
ON(B,C) Split
Join
LSR, AI: IK103
12/11/2009
54
At the third level the preconditions of STACK are considered – the two blocks involved must be clear. Level 3: before criticism 1
CLEAR(A)
S
J 2
3
STACK(A,B)
CLEAR(B)
S
J 4
CLEAR(B)
S
J
5
6
STACK(B,C)
CLEAR(C)
LSR, AI: IK103
12/11/2009
55
Now NOAH employs a set of critics to examine the plan and detect interactions among the subplans. Each critic is a little program that makes specific observations about the proposed plan.
LSR, AI: IK103
12/11/2009
56
The Resolve Conflicts critic – constructs a table that lists all the literals that are mentioned more than once in the plan.
CLEAR(B):
asserted: node 2 “Clear B” denied: node 3 “Stack A on B” asserted: node 4 “Clear B”
CLEAR(C):
asserted: node 5 “Clear C” denied: node 6 “Stack B on C”
LSR, AI: IK103
12/11/2009
57
Constraints on the ordering of operation arise when a given literal must be true before one operation can be performed but will be undone by another.
CLEAR(B):
denied: node 3 “Stack A on B” asserted: node 4 “Clear B”
LSR, AI: IK103
12/11/2009
58
Conclusion: Since putting A on B could undo the preconditions for putting B on C, putting B on C needs to be done first.
LSR, AI: IK103
12/11/2009
59
The third level after criticism to resolve conflicts: Level 3 CLEAR(A) S
J
STACK(A,B)
CLEAR(B)
S CLEAR(B) S
J
STACK(B,C)
CLEAR(C)
LSR, AI: IK103
12/11/2009
60
Can be invoked to eliminate the redundant specification of subgoals. In this case CLEAR(B) appears twice and is only denied by the last step of the plan.
LSR, AI: IK103
12/11/2009
61
The third level after all criticism: Level 3
CLEAR(A) J
STACK(A,B)
S CLEAR(B) S
J
STACK(B,C)
CLEAR(C)
LSR, AI: IK103
12/11/2009
62
To clear A, C must be removed from A. in order to do that C must be clear : Level 4: before criticism CLEAR(C)
STACK(C,x)
S
J
STACK(A,B)
CLEAR(B) S
J
STACK(B,C)
CLEAR(C)
LSR, AI: IK103
12/11/2009
63
The critic observes that putting B on C will make CLEAR(C) false, so everything that depends on C being clear will have to be done before B is put on C.
LSR, AI: IK103
12/11/2009
64
The Resolve Conflicts critic is employed: CLEAR(C)
STACK(C,x)
S J
STACK(B,C)
STACK(A,B)
CLEAR(B)
S CLEAR(C)
Level 4: after criticism to resolve conflicts
LSR, AI: IK103
12/11/2009
65
It notices that CLEAR(C) is required twice. Since putting C somewhere must occur before putting B on C, and both require C being clear then we know that when we get to putting B on C, C will be clear. CLEAR(C) can be eliminated from the lower path.
LSR, AI: IK103
12/11/2009
66
The Eliminate Redundant Preconditions critic is called: Level 4: after all criticism CLEAR(C)
STACK(C,x)
S CLEAR(B)
J
STACK(B,C)
LSR, AI: IK103
STACK(A,B)
12/11/2009
67
The system observes that the remaining goals , CLEAR(C) and CLEAR(B), are true in the initial state. Therefore the final plan is:
Final plan STACK(C,x)
STACK(B,C)
STACK(A,B)
LSR, AI: IK103
12/11/2009
68
C B A
B
A
C
LSR, AI: IK103
12/11/2009
69
