artificial intelegent (planning)
TRANSCRIPT
AI: Planning System
Russel and Norvig, Chapter 11
L. Manevitz, Slide Presentasi,
http://www.cs.uiowa.edu
Overview
• Bagaimana mendapatkan goal dari initial state ?
Initial State Goal
The blocks world problem
Overview Planning
• Planning adalah metode yang telah dipikirkansecara detail sebelum menyelesaikan suatupekerjaan.
Misalkan: ide atau metode untuk mengalahkantim lawan dalam pertandingan sepakbola.
• Planning is action or process of making plans for something.
• Planning penting untuk solusi yang tidak dapatdibalik kembali (undo).
Overview Planning (2)
• 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.
Metode Planning
STRIPS (STanford Research Institute Planning System-1971 by Fikes and Nilsson)
• Goal Stack Planning
• Constraint Posting
• NOAH
• etc
Komponen planning system
• Memilih rule terbaik berdasarkan informasiheuristik yang tersedia.
• Mengimplementasikan rule yang dipilih danmenghitung masalah yang muncul dariimplementasi 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-benarmenemukan solusi.
Memilih Rule
• 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.
Implementasi Rule
• 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.
Mendeteksi solusi
• Planning sistem dikatakan menemukan solusi jika telah menemukan sequence operasi dari initial state ke goal state.
Mendeteksi dead ends (jalan buntu)
• 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.
Teknik mendapatkan solusi
• Jika masalah tersebut dapat didekomposisi(dipecah-pecah) maka solusi tiap subbagian telah ditemukan maka solusi masalah merupakan gabungannya.
Metode Goal Stack Planning
• Metode ini menggunakan satu stack yang mengandung goal dan operator yang diusulkanuntuk mencapai goal.
• Adanya set operator yang mendeskripsikan daftarPRECONDITION, ADD, dan DELETE.
• Jika goal lebih dari satu, metode ini akanmemecahkan goal satu persatu.
• Solusi yang diperoleh yaitu sequence operator dari goal pertama kemudian diikuti olehsequence operator goal kedua dan seterusnya.
Goal Stack Planning
• 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.
Studi kasusDunia Balok (Blocks World)
Langkah:1. Mendefinisikan Operator apa saja.2. Spesifikasi/Deskripsi Operator (PRECONDITION, ADD dan DELETE).3. Pendefinisikan Initial dan Goal state.3. Membuat Stack4. Implementasi Operator dan menemukan goal
Initial State Goal
All rights reserved © L. Manevitz Lecture 6 16
The Blocks World
• 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.
The Blocks World cont.
– 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.
The Blocks World cont.
• 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.
The Blocks World cont.
• Inference rules:
– [ x : HOLDING(x)] ARMEMPTY
– x : ONTABLE(x) y : ON(x,y)
– x : [ y : ON(y,x)] CLEAR(x)
A Simple Blocks World Description
B
A
ON(A,B)
ONTABLE(B)
CLEAR(A)
Spesifikasi Operator
• 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.
Spesifikasi Operator Blocks World
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
D: ON(A, B) ARMEMPTY
A: HOLDING(A) CLEAR(B)
PICKUP(A):
P: CLEAR(A) ONTABLE(A) ARMEMPTY
D: ONTABLE(A) ARMEMPTY
A: HOLDING(A)
PUTDOWN(A):
P: HOLDING(A)
D: HOLDING(A)
A: ONTABLE(A) ARMEMPTY
Pendefinisian State
ON(B, A)
ONTABLE(A)
ONTABLE(C)
ONTABLE(D)
ARMEMPTY
start: ON(C, A)
ON(B, D)
ONTABLE(A)
ONTABLE(D)
ARMEMPTY
goal:
Initial State Goal
ON(A,B): Balok A menempel diatas balok BONTABLE(A): Balok A berada dipermukaan mejaCLEAR(A): Tidak ada balok yg sedang menempel di AARMEMPTY: Robot tidak sedang memegang balok
Membuat Stack
Goals
Operators to
satisfy
the Goals
Current situation
Specification of
Operators/Actions
Stack Database
+
Implementasi GSP
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.
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.
28
Goal Stack Planning
1) Initial goal stack:
ON(C,A) ON(B,D) ONTABLE(A) ONTABLE(D)ΛΛΛ
Initial State Goal
29
Goal Stack Planning cont.
2) Choose to work on ON(C,A) before ON(B,D):
ON(C,A) ON(B,D) OTADON(B,D)ON(C,A)
ΛΛ
Initial State Goal
30
Goal Stack Planning cont.
3) Achieve ON(C,A) with STACK(C,A):
ON(C,A) ON(B,D) OTADON(B,D)ON(C,A)STACK(C,A)
Initial State Goal
31
Goal Stack Planning cont.
4) Add STACK’s preconditions:
ON(C,A) ON(B,D) OTADON(B,D)STACK(C,A)
HOLDING(C)CLEAR(A)
CLEAR(A) HOLDING(C)
Initial State Goal
32
Goal Stack Planning cont.
5) Achieve CLEAR(A) with UNSTACK(B,A):
ON(C,A) ON(B,D) OTADON(B,D)STACK(C,A)
HOLDING(C)CLEAR(A) HOLDING(C)
UNSTACK(B,A)
ON(B,A) CLEAR(B) ARMEMPTY
ON(B,A)CLEAR(B)ARMEMPTY
CLEAR(A)
Initial State Goal
33
Goal Stack Planning cont.
6) Pop satisfied predicates:
ON(C,A) ON(B,D) OTADON(B,D)STACK(C,A)
HOLDING(C)CLEAR(A) HOLDING(C)
UNSTACK(B,A)
ON(B,A) CLEAR(B) ARMEMPTY
ON(B,A)CLEAR(B)ARMEMPTY
Initial State Goal
34
Goal Stack Planning cont.
7) Achieve HOLDING(C) with UNSTACK(C,x):
ON(C,A) ON(B,D) OTADON(B,D)STACK(C,A)
HOLDING(C)CLEAR(A) HOLDING(C)
UNSTACK(C,x)ON(C,x) CLEAR(C) ARMEMPTY
ON(C,x)
CLEAR(C)ARMEMPTY
Initial State Goal
35
Goal Stack Planning cont.
8) Achieve ON(C,x) by STACK(C,x):
ON(C,A) ON(B,D) OTADON(B,D)STACK(C,A)CLEAR(A) HOLDING(C)
UNSTACK(C,x)ON(C,x) CLEAR(C) ARMEMPTY
ON(C,x)
CLEAR(C)ARMEMPTY
STACK(C,x)CLEAR(x) HOLDING(C)HOLDING(C)CLEAR(x)
Initial State Goal
36
Goal Stack Planning cont.
9) Terminate path because HOLDING(C) is duplicated.
ON(C,A) ON(B,D) OTADON(B,D)STACK(C,A)CLEAR(A) HOLDING(C)
UNSTACK(C,x)ON(C,x) CLEAR(C) ARMEMPTY
CLEAR(C)ARMEMPTY
STACK(C,x)CLEAR(x) HOLDING(C)HOLDING(C)CLEAR(x)
Initial State Goal
37
Goal Stack Planning cont.
10) Achieve HOLDING(C) with PICKUP, not UNSTACK:
ON(C,A) ON(B,D) OTADON(B,D)STACK(C,A)CLEAR(A) HOLDING(C)
PICKUP(C)ONTABLE(C) CLEAR(C) ARMEMPTY
CLEAR(C)ARMEMPTY
ONTABLE(C)
Initial State Goal
38
Goal Stack Planning cont.
11) Pop ONTABLE(C) and CLEAR(C), and achieve ARMEMPTY by STACK(B,D):
ON(C,A) ON(B,D) OTADON(B,D)STACK(C,A)CLEAR(A) HOLDING(C)
PICKUP(C)ONTABLE(C) CLEAR(C) ARMEMPTY
CLEAR(C)ARMEMPTY
ONTABLE(C)
STACK(B,D)CLEAR(D) HOLDING(B)
HOLDING(B)CLEAR(D)
Initial State Goal
39
Goal Stack Planning cont.
12) Pop entire stack, and return plan:
i. UNSTACK(B,A).
ii. STACK(B,D).
iii. PICKUP(C).
iv. STACK(C,A).
Initial State Goal
Algorithma GSP
1. Tempatkan seluruh kondisi goal-state pada slot stack paling bawah.
2. Masukkan setiap kondisi goal state yang belum tercapai ke dalam sebuah slot stack.
3. 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
Contoh lain
Solusi
All rights reserved © L. Manevitz Lecture 6 48
The Problem Solving System NOAH
• 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.
All rights reserved © L. Manevitz Lecture 6 49
All rights reserved © L. Manevitz Lecture 6 50
NOAH cont.
• 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.
All rights reserved © L. Manevitz Lecture 6 51
The Blocks Problem
• A reminder of the problem :
A
C
B C
B
A
Start: ON(C,A)
ONTABLE(A)
ONTABLE(B)
ARMEMPTY
Goal: ON(A,B)
ON(B,C)
All rights reserved © L. Manevitz Lecture 6 52
NOAH Solution
• The initial state of the problem solver:
(ON(A,B) ON(B,C)) Level 1
All rights reserved © L. Manevitz Lecture 6 53
NOAH Solution cont.
• The first thing that it does is to divide the problem into two subproblems:
ON(A,B)
Level 2
ON(B,C)
S J
Split Join
All rights reserved © L. Manevitz Lecture 6 54
NOAH Solution cont.
• At the third level the preconditions of STACK are considered – the two blocks involved must be clear.
CLEAR(A)
Level 3: before criticism
CLEAR(B)
S J
CLEAR(B)
CLEAR(C)
S J
S
STACK(A,B)
STACK(B,C)
J
1
2
4
5
6
3
All rights reserved © L. Manevitz Lecture 6 55
NOAH Solution cont.
• 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.
All rights reserved © L. Manevitz Lecture 6 56
The Resolve Conflicts critic
• 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”
All rights reserved © L. Manevitz Lecture 6 57
The Resolve Conflicts critic cont.
• 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”
All rights reserved © L. Manevitz Lecture 6 58
The Resolve Conflicts critic cont.
• Conclusion:
Since putting A on B could undo the preconditions for putting B on C, putting B on C needs to be done first.
All rights reserved © L. Manevitz Lecture 6 59
NOAH Solution cont.
• The third level after criticism to resolve conflicts:
CLEAR(A)
Level 3
CLEAR(B)
S J
CLEAR(B)
CLEAR(C)
S J
S
STACK(A,B)
STACK(B,C)
All rights reserved © L. Manevitz Lecture 6 60
Eliminate Redundant Preconditions
• 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.
All rights reserved © L. Manevitz Lecture 6 61
NOAH Solution cont.
• The third level after all criticism:
CLEAR(A)
Level 3
J
CLEAR(B)
CLEAR(C)
S J
S
STACK(A,B)
STACK(B,C)
All rights reserved © L. Manevitz Lecture 6 62
NOAH Solution cont.
• To clear A, C must be removed from A. in order to do that C must be clear :
CLEAR(C)
Level 4: before criticism
J
CLEAR(B)
CLEAR(C)
S J
S STACK(A,B)
STACK(B,C)
STACK(C,x)
All rights reserved © L. Manevitz Lecture 6 63
The Resolve Conflicts critic
• 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.
All rights reserved © L. Manevitz Lecture 6 64
NOAH Solution cont.
• The Resolve Conflicts critic is employed:
CLEAR(C)
Level 4: after criticism to
resolve conflicts
CLEAR(B)
CLEAR(C)
S
J
S
STACK(A,B)STACK(B,C)
STACK(C,x)
All rights reserved © L. Manevitz Lecture 6 65
Eliminate Redundant Preconditions
• 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.
All rights reserved © L. Manevitz Lecture 6 66
NOAH Solution cont.
• The Eliminate Redundant Preconditions critic is called:
CLEAR(C)
Level 4: after all criticism
CLEAR(B) J
S
STACK(A,B)STACK(B,C)
STACK(C,x)
All rights reserved © L. Manevitz Lecture 6 67
NOAH Solution cont.
• 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(A,B)STACK(B,C)STACK(C,x)