AI_20111003
- 1. Problem Solving Agent: Searching Inteligensi Buatan (MKB6403) Kuliah 3 SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN TEKNIK KOMPUTER INDONESIA (STMIK-INDONESIA) 息 2011 Problem-Solving Agent Kelemahan re鍖ex agent tidak cocok untuk menangani masalah besar! Goal-based agent memiliki tujuan, memungkinkan untuk mengevaluasi tindakan dan memilih yang terbaik Pada Kuliah 3 akan dibahas suatu goal-based agent: problem-solving agent Problem-solving agent menghasilkan solusi dalam bentuk serangkaian tindakan untuk mencapai tujuan Apa permasalahannya? Apa solusinya? 10/19/2011 Problem Solving Agent: Searching 2
- 2. Cara Kerja Problem-Solving Agent 1. Perumusan tujuan (goal formulation): tentukan tujuan yang ingin dicapai 2. Perumusan masalah (problem formulation): tentukan tindakan (action) dan keadaan (state) yang dipertimbangkan dalam mencapai tujuan 3. Pencarian solusi masalah (searching): tentukan rangkaian tindakan yang perlu diambil untuk mencapai tujuan 4. Pelaksanaan solusi (execution): laksanakan rangkaian tindakan yang sudah ditentukan di tahap sebelumnya 10/19/2011 Problem Solving Agent: Searching 3 Program Problem-Solving Agent function SIMPLE-PROBLEM-SOLVING-AGENT(p) returns action inputs: p, a percept static: s, an action sequence, initially empty state, some description of the current world state g, a goal, initially null problem, a problem formulation state UPDATE-STATE(state,p) if s is empty then g FORMULATE-GOAL(state) problem FORMULATE-PROBLEM(state,g) s SEARCH(problem) action RECOMMENDATION(s,state) s REMAINDER(s,state) return action 10/19/2011 Problem Solving Agent: Searching 4
- 3. Sifat Problem-Solving Agent Secara umum, problem-solving agent mengasumsikan bahwa environment-nya: Accessible Deterministic Episodic Static Discrete Setelah mencari solusi, agent melakukan tindakan dengan mata tertutup tidak melihat percept! 10/19/2011 Problem Solving Agent: Searching 5 Contoh: Turis di Rumania Suatu tourist agent sedang berlibur di Rumania. Sekarang dia berada di kota Arad. Besok, dia harus terbang dari bandara yang ada di kota Bucharest! Perumusan tujuan: berada di Bucharest Perumusan masalah: Tindakan (action): menyetir dari kota ke kota Keadaan (state): kota-kota di Rumania Pencarian solusi: rangkaian kota yang dituju, misal: Arad-Sibiu-Fagaras-Bucharest 10/19/2011 Problem Solving Agent: Searching 6
- 4. Peta Rumania 10/19/2011 Problem Solving Agent: Searching 7 Perumusan Masalah: State Space (1) Initial state: keadaan awal si agent, misal: BeradaDi(Arad) Possible action: tindakan yang dapat dilakukan si agent, misal: Nyetir(Arad,Zerind) Sebuah successor function S menentukan untuk suatu state X, himpunan tindakan yang mungkin diambil beserta state yang dihasilkan. Contoh: X = BeradaDi(Arad) S(X) = {<Nyetir(Arad, Zerind), BeradaDi(Zerind)>, {<Nyetir(Arad, Sibiu), BeradaDi(Sibiu)>, {<Nyetir(Arad, Timisoara), BeradaDi(Timisoara)>} 10/19/2011 Problem Solving Agent: Searching 8
- 5. Perumusan Masalah: State Space (2) Initial state + successor function = state space State space himpunan state yang dapat dicapai dari initial state State space dapat direpresentasikan sebagai graph dengan path sebagai suatu rangkaian state ingat tourist agent Rumania!!! 10/19/2011 Problem Solving Agent: Searching 9 Menelusuri State Space Goal test: penentuan apakah suatu state adalah tujuan yang ingin dicapai Eksplisit: himpunan goal state, misal: {BeradaDi(Bucharest)} Implisit: deskripsi tujuan, misal dalam catur: skak mat Path cost function: fungsi yang memberikan nilai numerik terhadap setiap path. Fungsi ini merefleksikan performance measure si agent. Solusi: path dari initial state ke goal state Solusi optimal: solusi dengan path cost function minimal 10/19/2011 Problem Solving Agent: Searching 10
- 6. Contoh: The 8-Puzzle State: lokasi 8 buah angka dalam matriks 3x3 Possible action: kiri, kanan, atas, bawah Goal test: apakah susunan angka seperti goal state? Path cost: asumsi step cost = 1. Path cost = jumlah langkah dalam path 10/19/2011 Problem Solving Agent: Searching 11 Contoh: The 8-Queens Problem Letakkan 8 bidak menteri (queen) sedemikian rupa sehingga tidak terjadi saling makan antara satu menteri dengan yang lainnya State: papan catur dengan 0 sampai 8 bidak menteri Possible action: letakkan sebuah bidak menteri di posisi yang kosong Goal test: 8 menteri di papan, tidak ada saling makan Path cost: 0 10/19/2011 Problem Solving Agent: Searching 12
- 7. Contoh: The Vacuum World State: lokasi agent, status debu Possible action: DoKeKiri(L), DoKeKanan(R), Sedot(S) Goal test: apakah semua ruangan bebas debu? Path cost: jumlah langkah dalam path 10/19/2011 Problem Solving Agent: Searching 13 Mencari Solusi Melalui Search Tree Setelah merumuskan masalah cari solusinya menggunakan search algorithm Search tree merepresentasikan state space Search tree terdiri dari kumpulan node struktur data yang merepresentasikan suatu state pada suatu path, dan memiliki parent, children, depth, dan path cost Root node merepresentasikan initial state Node expansion merupakan penerapan successor function terhadap node menghasilkan children baru Kumpulan semua node yang belum di-expand disebut fringe (pinggir) sebuah search tree 10/19/2011 Problem Solving Agent: Searching 14
- 8. Contoh Penelusuran Search Tree Mulai dari root node (Arad) sebagai current node Lakukan node expansion Pilih salah satu node yang di-expand sebagai current node yang baru. Ulangi langkah sebelumnya Arad Sibiu Timisoara Zerind Fagaras Oradea Rimnicu Vilcea 10/19/2011 Problem Solving Agent: Searching 15 Algoritma Penelusuran Search Tree function GENERAL-SEARCH(problem,fringe) returns solution or failure fringe INSERT(MAKE-NODE(INITIAL-STATE(problem),fringe)) loop do if fringe is EMPTY than return failure node REMOVE-FIRST(fringe) if GOAL-TEST(problem) applied to STATE(node) succeeds then return node fringe INSERT-ALL(EXPAND(node,problem),fringe) end 1. Pada awal, fringe = himpunan node yang mewakili initial state 2. Pilih satu node dari fringe sebagai current node. Jika fringe kosong, selesai dengan gagal 3. Jika node tsb . lolos goal test, selesai dengan sukses! 4. Jika tidak, lakukan node expansion terhadap current node tsb. 5. Ulangi langkah 2 10/19/2011 Problem Solving Agent: Searching 16
- 9. Strategi Pencarian Ada berbagai jenis strategi dalam melakukan searching. Perbedaannya terdapat pada node expansion-nya Search strategy dievaluasi berdasarkan: Completeness: apakah solusi (jika ada) pasti ditemukan? Time complexity: berapa lama untuk mencari solusi? atau berapa banyak jumlah node yang di-expand? Space complexity: jumlah maksimum node di dalam memori Optimality: apakah solusi dengan minimum cost pasti ditemukan? 10/19/2011 Problem Solving Agent: Searching 17 Jenis-jenis Strategi Pencarian Ada 2 jenis strategi pencarian: Uninformed strategy, hanya menggunakan informasi dari definisi masalah Informed strategy, menggunakan informasi lainnya Uninformed strategy dapat diterapkan secara generik terhadap semua jenis masalah yang bisa direpresentasikan dalam sebuah state space 10/19/2011 Problem Solving Agent: Searching 18
- 10. Contoh-contoh Strategi Pencarian Uninformed Strategy: Informed Strategy: Breadth-first Search Uniform Cost Search Depth-first Search Greedy Best-first Depth-limited Search Search A* Search Iterative Deepening Search 10/19/2011 Problem Solving Agent: Searching 19 Latihan Suatu tourist agent sedang berlibur di Rumania. Sekarang dia berada di kota Bucharest. Besok, dia harus menghadiri pertemuan di kota Arad dan harus menyetir dari kota ke kota! 1. Tentukan task environment (PAGE)! 2. Tentukan state space (initial state + successor function)! 10/19/2011 Problem Solving Agent: Searching 20
- 11. Peta Rumania 10/19/2011 Problem Solving Agent: Searching 21