AI sebagai Masalah Pelacakan
Lesson 2
Pendahuluan • “Semua Bidang AI adalah Pelacakan” – Game – Ruang masalah (problem spaces) • Setiap masalah adalah “pohon virtual” dari seluruh solusi yang mungkin (berhasil atau tidak berhasil) • Tujuannya menentukan/mencari strategi pelacakan yang efisien
State-Space Approach for AI Problem Solving • Di dalam permasalahan AI dikenal istilah state • State merepresentasikan status sistem pada saat tertentu • State-space approach adalah metode untuk menyelesaikan masalah dengan melakukan operasi-operasi tertentu pada state saat ini untuk menghasilkan next-state terus menerus hingga dicapai final-state yang diinginkan
State-Space Approach for AI Problem Solving • Langkah awal penyelesaian masalah adalah merepresentasikan masalah ke dalam representasi state-space (ruang keadaan) • Untuk memperoleh state space (ruang keadaan), diperlukan state-state dan rules yang membentuk hubungan antar state • Kemudian dilakukan teknik penyelesaian masalah yang pada dasarnya merupakan proses pencarian ruang keadaan (state space search)
State-Space Approach for AI Problem Solving • Secara sederhana, langkah2 penyelesaian masalah menggunakan State Space Approach adalah sbb. 1. Nyatakan masalah ke dalam bentuk state space (ruang keadaan) 1) Tentukan definisi state untuk masalah tersebut 2) Tentukan rules/operasi-operasi yang mungkin ada di dalam masalah tersebut untuk menghasilkan next-state 2. Gunakan teknik pencarian tertentu untuk mendapatkan solusi, mulai dari initial state hingga mendapatkan goal/final state
Contoh 1 – 4 Puzzle Problem • Puzzle yang terdiri atas 4 buah cell • Tiga cell berisi digit angka, 1 cell kosong (blank) • Terdapat 4 operasi swapping: Blank-Up (BU), Blank-Down (BD), Blank-Left (BL), dan BlankRight (BR) • BU berarti posisi Blank (B) ditukar dengan posisi cell di atasnya, dst. • Masalahnya adalah: bagaimana mencapai final state dari sebuah initial state dengan langkah seminimum mungkin?
Contoh 1 – 4 Puzzle (lanj.) • Contoh:
• Jawabannya : 2 langkah (BL lalu BU) • Bagaimana memperoleh solusi tersebut menggunakan state-space approach?
Contoh 1 – 4 Puzzle (lanj.) • Untuk mendapatkan solusi menggunakan statespace approach, yang harus dilakukan adalah: 1.
Menyatakan masalah dalam bentuk ruang state 1) 2)
2.
Definisikan dulu state Nyatakan operasi2 yang mungkin digunakan untuk menghasilkan next-state
Menerapkan teknik searching tertentu untuk mendapatkan solusi
Contoh 1 – 4 Puzzle (lanj.) • State-space (ruang state, ruang keadaan) dari masalah 4 Puzzle ini adalah kumpulan state puzzle yang mungkin terjadi • Tentukan inisial dan final state • Beberapa state yang mungkin terjadi di antaranya: – (1, 2, 3, B) – (1, 2, B, 3) – (1, B, 3, 2) – dst..
Contoh 1 – 4 Puzzle (lanj.) • Jadi, state dalam masalah 4 Puzzle ini dapat didefinisikan sebagai: – (w, x, y, z), dengan nilai yang mungkin untuk w, x, y, z adalah 1, 2, 3, B dan tidak boleh sama satu sama lain • Maka akan terdapat 4 x 3 x 2 x 1 = 24 state yang mungkin • Setelah mendefinisikan state, tentukan operasi-operasi yang mungkin terjadi.
Contoh 1 – 4 Puzzle (lanj.) • Aturan-aturan (rules) yang dapat digunakan di antaranya: 1. op BU: (1, 2, 3, B) (1, B, 3, 2), 2. op BL: (1, 2, 3, B) (1, 2, B, 3), 3. ... 4. dst.
• Rules dapat dibuat lebih generik, semakin generik semakin baik
Contoh 1 – 4 Puzzle (lanj.) • Contoh rules yang lebih generik: 1. p4 = B BU:(swap p2-p4) atau BL:(swap p3-p4) 2. P3 = B BU:(swap p1-p3) atau BL:(swap p4-p3) 3. ... 4. dst. pi = nilai di kotak ke-i pada 4-Puzzle • Setelah rules dibuat, tentukan initial state dan final state • Lakukan pencarian (state-space search) untuk menemukan solusi permasalahan
Contoh 1 – 4 Puzzle (lanj.) • ruang state yang dihasilkan • Dengan menerapkan teknik seraching tertentu (yang akan dipelajari di bagian berikutnya) maka akan diperoleh solusinya adalah 2 langkah, yaitu BL lalu BU
Cara Merepresentasikan Ruang Keadaan
1. Graf Keadaan 2. Pohon Pelacakan 3. Pohon And/Or
Graf Keadaan • Terdiri dr simpul (node) dan busur (arc). Simpul menunjukkan keadaan, yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. • Busur menghubungkan suatu simpul dengan simpul lainnya. • Busur menunjukkan arah dr suatu keadaan ke keadaan berikutnya. • Dalam praktek, sangat sulit menggambarkan keadaan dengan graph.
Graf Keadaan
M
Simpul M menunjukkan keadaan awal. Simpul T adalah tujuan. Ada 4 lintasan dr M ke T: 1. M-A-B-C-E-T 2. M-A-B-C-E-H-T 3. M-D-C-E-T 4. M-D-C-E-H-T
Lintasan yang tidak sampai ke tujuan (menemui jalan buntu) : 1. M-A-B-C-E-F-G 2. M-A-B-C-E-I-J 3. M-D-C-E-F-G 4. M-D-C-E-I-J 5. M-D-I-J
Pohon Pelacakan • Untuk menghindari kemungkinan adanya proses pelacakan simpul secara berulang pada Graph Keadaan, digunakan Pohon Pelacakan, berupa struktur pohon.
Pohon Pelacakan M
Pohon Pelacakan • Simpul pada Level 0 disebut akar (root). Simpul akar menunjukkan keadaan awal yang biasanya merupakan topik atau obyek. • Simpul akar memiliki beberapa percabangan yang terdiri atas beberapa simpul successor yang disebut anak (child) dan merupakan simpul perantara. • Namun, jika dilakukan pelacakan mundur , maka dapat dikatakan bahwa simpul tersebut memiliki predecessor.
Pohon Pelacakan • Simpul yang tidak memiliki anak disebut daun (leaf) yang menunjukkan akhir dr suatu pencarian. • Simpul daun dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).
Contoh 2 : Water Jug Problem[1] • Terdapat dua buah wadah/ember berukuran 4 L dan 3 L. Bagaimana memperoleh air sebanyak 2 L dengan menggunakan kedua wadah tersebut, dengan asumsi kedua ember awalnya kosong?
Contoh 2 : Water Jug Problem[1]lanj. • Nyatakan masalah dalam representasi state • State: – (x, y); x = 0, 1, 2, 3 atau 4, dan y = 0, 1, 2 atau 3; – x = jumlah air (liter) pada ember bervolume 4 liter, dan y = jumlah air (liter) pada ember bervolume 3 liter • Initial state: (0,0) • Final state: (2, n), atau (n, 2) untuk sembarang nilai n (persoalan ini tidak menentukan berapa berapa liter air yang ada di ember bervolume 3 liter atau sebaliknya)
Contoh 2 : Water Jug Problem[1]lanj. •
Buatlah deskripsi formal dari rules/operasi yang mungkin dilakukan di dalam permasalahan ini, dengan melist operasi2 yg mungkin dilakukan
•
Operasi yang dapat digunakan untuk menyelesaikan masalah adalah sbb: 1.
Mengisi ember bervolume 4 liter dari luar sampai penuh.
2.
Mengisi ember bervolume 3 liter dari luar sampai penuh.
3.
Mengisi sejumlah air dari ember bervolume 4 liter ke ember 3 liter (tidak sampai penuh).
4.
Mengisi sejumlah air dari ember bervolume 3 liter ke ember 4 liter (tidak sampai penuh).
5.
Mengosongkan/membuang air dari ember bervolume 4 liter.
6.
Mengosongkan/membuang air dari ember bervolume 3 liter.
Contoh 2 : Water Jug Problem[1]lanj. • (lanjutan): 7.
Menuangkan air dari ember bervolume 3 liter ke ember bervolume 4 liter sampai ember bervolume 4 liter menjadi penuh.
8. Menuangkan air dari ember bervolume 4 liter ke ember bervolume 3 liter sampai ember bervolume 3 liter menjadi penuh.
9. Menuangkan semua air dari ember bervolume 3 liter ke ember bervolume 4 liter. 10. Menuangkan semua air dari ember bervolume 4 liter ke ember bervolume 3 liter.
Contoh 2 : Water Jug Problem[1]lanj. • Rules/operasi tersebut dapat dideskripsikan secara formal sbb: 1. (x, y x < 4) (4, y)
2. (x, y y < 3) (x, 3) 3. (x, y x > 0, y + D < 3) (x-D, y+D) 4. (x, y y > 0, x + D < 4) (x+D, y-D)
5. (x, y x > 0) (0, y)
Contoh 2 : Water Jug Problem[1]lanj. • Rules operasi yang digunakan untuk menyelesaikan masalah adalah sbb: 6. (x, y y > 0) (x, 0)
7. (x, y x+y 4 y > 0) (4, y-(4-x)) 8. (x, y x+y 3 x > 0) (x-(3-y), 3) 9. (x, y x+y 4 y > 0) (x+y, 0)
10.(x, y x+y 3 x > 0) (0, x+y)
Contoh 2 : Water Jug Problem[1]lanj. • Salah satu solusi yang diperoleh adalah sbb: Aturan yang Jumlah air (liter) dalam diterapkan
ember bervolume 4 liter
ember bervolume 3 liter
0
0
2
0
3
9
3
0
2
3
3
7
4
2
5
0
2
9
2
0
Contoh 2 : Water Jug Problem[1]lanj. • Jadi urutan langkahnya adalah 2-9-2-7-5-9
Representasi Ruang Keadaaan untuk masalah Ember Air dengan Pohon Pelacakan
• Contoh pohon pelacakan parsial untuk masalah Water Jug[1] sebelumnya:
Representasi Ruang Keadaaan untuk masalah Ember Air dengan Pohon Pelacakan
• Contoh pohon pelacakan parsial untuk masalah Water Jug[1] sebelumnya:
(0, 0)
(4, 0)
(4, 3)
(0, 0)
(0, 3)
(1, 3)
(4, 3)
(0, 0)
(3, 0)
Pohon And/Or • Digunakan untuk menunjukkan bahwa masalah yang hendak diselesaikan dengan Pohon Pelacakan dapat diselesaikan dengan mengambil salah satu sub-goal atau hanya dapat diselesaikan dengan mengambil lebih dr satu subgoal sekaligus.
Pohon And/Or
Gambar [a] menunjukkan ada suatu masalah M yang hendak dicari solusinya dengan 3 kemungkinan yaitu A, B, atau C. Artinya, masalah M bisa diselesaikan jika salah satu dr sub-goal A, B, atau C terpecahkan. OR Gambar [b] menunjukkan bahwa masalah M hanya bisa diselesaikan dengan memecahkan sub-goal A, B, dan C terlebih dulu sekaligus. AND
Pohon And/Or • Dengan pohon AND/OR bisa mempersingkat level Pohon Pelacakan.
Teknik Pencarian sebagai Struktur Kontrol • Untuk dapat memecahkan problema, dibutuhkan juga suatu struktur pengendalian/kontrol yang melakukan pengulangan (looping) melalui siklus sederhana • Selama melakukan proses pencarian untuk mendapatkan solusi dari sebuah problema, kita tentu akan bertanya-tanya tentang bagaimanakah caranya memutuskan aturan berikutnya yang akan digunakan kemudian atau memutuskan state berikutnya?
Teknik Pencarian sebagai Struktur Kontrol • Teknik Pencarian atau Struktur Kontrol yang baik haruslah 1. Dapat menimbulkan adanya ‘gerak’ (movement). Teknik Pencarian atau Struktur Kontrol yang tidak menyebabkan adanya ‘gerak’ tidak akan pernah sampai pada sebuah solusi. Pada problema ember air, jika kita mulai dengan memilih aturan yang pertama lalu kedua atau sebaliknya, maka kita tidak akan pernah dapat menyelesaikan problema.
Teknik Pencarian sebagai Struktur Kontrol 2. Sistematik Teknik Pencarian atau Struktur Kontrol yang tidak sistematik akan menyebabkan penggunaan serangkaian operator aturan beberapa kali sebelum sampai pada sebuah solusi.
Teknik Pencarian sebagai Struktur Kontrol Jika kita memilih aturan-aturan secara acak (random) pada setiap siklus, walaupun akan menimbulkan adanya ‘gerak’ dan akan menghasilkan solusi, namun kita akan sampai pada keadaan yang sama beberapa kali dan menggunakan lebih banyak langkah yang semestinya diperlukan. • Strategi sistematik (non heuristic) yang dapat digunakan di antaranya breadth-first search, depth-first search, dan best-first search.
Latihan 1 – Water Jug Problem[2] • Terdapat dua buah wadah/ember berukuran 5 L dan 3 L. Bagaimana memperoleh air sebanyak 4 L dengan menggunakan kedua wadah tersebut, dengan asumsi kedua ember awalnya kosong?
Latihan 2 Petani Kambing Srigala Rumput • Seorang Petani akan menyeberangkan seekor Kambing, seekor Srigala, dan Rumput dengan menggunakan perahu menyeberangi sungai. • Perahu hanya bisa memuat Petani dan salah satu dari yang hendak diseberangkan (Kambing / Srigala / Rumput). • Jika ditinggalkan oleh Petani, maka Rumput akan dimakan oleh Kambing dan Kambing akan dimakan oleh Srigala.p
Latihan 2 Petani Kambing Srigala Rumput-lanj. • Deskripsikan secara formal problema PKSR tersebut! • Bagaimanakah salah satu solusi masalah PKSR tersebut dengan deskripsi formal yang dibuat? • Bagaimanakah representasi ruang keadaan dengan Pohon Pelacakan untuk masalah tersebut?
