ai_20111003
TRANSCRIPT
![Page 1: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/1.jpg)
Problem Solving Agent: Searching
SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN TEKNIK KOMPUTER INDONESIA (STMIK-INDONESIA)
© 2011
Inteligensi Buatan (MKB6403)
Kuliah 3
Problem-Solving Agent
• Kelemahan reflex agent → tidak cocok untukmenangani masalah besar!
• Goal-based agent → memiliki tujuan, memungkinkan untuk mengevaluasi tindakandan memilih yang terbaikdan memilih yang terbaik
• Pada Kuliah 3 akan dibahas suatu goal-based agent: problem-solving agent
• Problem-solving agent menghasilkan solusi dalambentuk serangkaian tindakan untuk mencapaitujuan
• Apa permasalahannya? Apa solusinya?
10/19/2011 Problem Solving Agent: Searching 2
![Page 2: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/2.jpg)
Cara Kerja Problem-Solving Agent
1. Perumusan tujuan (goal formulation): tentukantujuan yang ingin dicapai
2. Perumusan masalah (problem formulation): tentukan tindakan (action) dan keadaan (state) yang dipertimbangkan dalam mencapai tujuanyang dipertimbangkan dalam mencapai tujuan
3. Pencarian solusi masalah (searching): tentukanrangkaian tindakan yang perlu diambil untukmencapai tujuan
4. Pelaksanaan solusi (execution): laksanakanrangkaian tindakan yang sudah ditentukan ditahap sebelumnya
10/19/2011 Problem Solving Agent: Searching 3
Program Problem-Solving Agent
function SIMPLE-PROBLEM-SOLVING-AGENT(p) returns action
inputs:static:
p, a percepts, an action sequence, initially emptystate, some description of the current world stateg, a goal, initially nullproblem, a problem formulation
state ← UPDATE-STATE(state,p)if s is empty then
10/19/2011 Problem Solving Agent: Searching 4
if s is empty theng ← FORMULATE-GOAL(state)problem ← FORMULATE-PROBLEM(state,g)s ← SEARCH(problem)
action ← RECOMMENDATION(s,state)s ← REMAINDER(s,state)return action
![Page 3: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/3.jpg)
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 BucharestPerumusan 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
![Page 4: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/4.jpg)
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 siagent, misal: Nyetir(Arad,Zerind)
• Sebuah successor function S menentukan untuk• Sebuah successor function S menentukan untuksuatu state X, himpunan tindakan yang mungkindiambil 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
![Page 5: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/5.jpg)
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 • 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• 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
![Page 6: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/6.jpg)
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 tidakterjadi 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
![Page 7: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/7.jpg)
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 solusinyamenggunakan search algorithm
• Search tree merepresentasikan state space
• Search tree terdiri dari kumpulan node → strukturdata yang merepresentasikan suatu state pada suatupath, dan memiliki parent, children, depth, dan path data yang merepresentasikan suatu state pada suatupath, 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 disebutfringe (pinggir) sebuah search tree
10/19/2011 Problem Solving Agent: Searching 14
![Page 8: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/8.jpg)
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
10/19/2011 Problem Solving Agent: Searching 15
Arad
Sibiu ZerindTimisoara
Fagaras Oradea Rimnicu Vilcea
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 failurenode ← REMOVE-FIRST(fringe)if GOAL-TEST(problem) applied to STATE(node) succeeds then return node
fringe ← INSERT-ALL(EXPAND(node,problem),fringe)
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
fringe ← INSERT-ALL(EXPAND(node,problem),fringe)end
![Page 9: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/9.jpg)
Strategi Pencarian
• Ada berbagai jenis strategi dalam melakukan
searching. Perbedaannya terdapat pada node
expansion-nya
• Search strategy dievaluasi berdasarkan: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– 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
![Page 10: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/10.jpg)
Contoh-contoh Strategi Pencarian
Uninformed Strategy:
• Breadth-first Search
• Depth-first Search
• Depth-limited
Informed Strategy:
• Uniform Cost Search
• Greedy Best-first
Search
10/19/2011 Problem Solving Agent: Searching 19
• Depth-limited
Search
• Iterative Deepening
Search
Search
• A* Search
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
![Page 11: AI_20111003](https://reader038.vdokumen.com/reader038/viewer/2022100500/555caac4d8b42ab2358b4d9a/html5/thumbnails/11.jpg)
Peta Rumania
10/19/2011 Problem Solving Agent: Searching 21