Kecerdasan Buatan (KI092301)
Problem-Solving Agent &
Search
Chastine Fatichah
Teknik Informatika
Institut Teknologi Sepuluh Nopember
November 2012
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 1 / 38
(KI092301)
Pokok Bahasan
• Problem-solving agent
• Representasi masalah : state space
• Pencarian solusi : search
• Search strategies
• Uninformed search
• Ringkasan
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 2 / 38
(KI092301)
Problem-Solving Agent
• Goal-based agent mempertimbangkan
action-action yang akan datang dan hasil
yang ingin dicapai
• Agent problem solving Menemukan
rangkaian tindakan (sequence action)
untuk mencapai tujuannya
• Algoritma Uninformed Tidak ada
informasi untuk problem, hanya deskripsi
pada masalah tersebut
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 3 / 38
(KI092301)
Simple Problem-Solving Agent
Function Simple-Problem-Solving-Agent(percept) return an
action
Input : percept //a percept
Static : seq //an action sequence, initially empty
state //some description of the current world state
goal //a goal, initially null
problem //a problem formulation
State Update-State(state, percept)
If seq is empty then do
goal Formulate-Goal(state)
problem Formulate-Problem(state,goal)
seq Search(Problem)
Action First(seq)
Seq Rest(seq)
Return action
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 4 / 38
(KI092301)
Mekanisme Kerja Problem-
Solving Agent
• Perumusan tujuan (goal formulation): tentukan tujuan yang
ingin dicapai
• Kondisi saat ini
• Performance measure
• Perumusan masalah (problem formulation): tentukan
tindakan (action) dan keadaan (state) yang
dipertimbangkan dalam mencapai tujuan
• Pencarian solusi masalah (searching) : tentukan rangkaian
tindakan yang perlu diambil untuk mencapai tujuan
• Input: problem, output: solusi dalam bentuk rangkaian tindakan
• Pelaksanaan solusi (execution): laksanakan rangkaian
tindakan yang sudah ditentukan di tahap sebelumnya
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 5 / 38
(KI092301)
Well-Define Problem & Solution
• Problem dapat dirumuskan dengan 5
komponen
• Initial state
• Actions : Successor function :
Successor-Fn(x) = <Action,Successor>
• Goal Test
• Path Cost
• Optimal Solution path cost terkecil
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 6 / 38
(KI092301)
Contoh Kasus : Romania
• Seorang agent sedang berlibur dan
sekarang sedang di kota Arad Romania
• Besok dia harus naik pesawat dari
Bucharest
• Goal dari agent sekarang adalah pergi ke
Bucharest
• Action yang tidak berhubungan dengan
goal akan dibuang -> decision agent
lebih sederhana
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 7 / 38
(KI092301)
Contoh Kasus: Romania
• Agent Mencapai tujuan (ke Bucharest)
dengan naik mobil
• Kemana akan pergi setelah dari Arad ?
• Ada tiga jalan : ke Sibiu, Timisoara, Zerind
• Agent kita ini masih belum tahu jalan disana
(mana yang tercepat) tapi hanya memiliki
peta.
• Dari informasi peta, dilakukan hipotesa
terhadap ketiga jalur tsb untuk sampai ke
Bucharest
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 8 / 38
(KI092301)
Contoh Kasus: Romania
(Agent & Environment)
• Static
• Tidak perlu memperhatikan perubahan yang
terjadi pada environment
• Observable
• Ada peta, initial state diketahui (di Arad)
• Discreet
• Enumeration action
• Deterministic
• Tidak bisa menangani terhadap hal-hal yang
tidak diperkirakan
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 9 / 38
(KI092301)
Contoh Kasus: Romania
(Well-Defined problem agent)
• Initial State di Arad
• Actions : Successor function
• {<Go(Sibiu),In(Sibiu)>,
<Go(Timisoara),In(Timisoara)>,
<Go(Zerind),In(Zerind)>}
• Goal Test In(Bucharest)
• Path Cost di slide berikutnya
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 10 / 38
(KI092301)
Contoh Kasus: Romania
(Path Cost Solusi Agent)
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 11 / 38
(KI092301)
Contoh Kasus: Romania
(Perumusan Tujuan, Masalah, & Solusi)
• Perumusan Tujuan
• Tiba di Bucharest besok
• Perumusan Masalah
• States : kota-kota
• Actions : mengemudi antar kota
• Pencarian Solusi
• Rangkaian kota : Arad, Sibiu, Fagaras,
Bucharest
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 12 / 38
(KI092301)
Contoh Kasus: Vacuum Cleaner
• Vacuum Cleaner
• States : Berada di salah satu dari
dua lokasi yang ada, yg masing2
mungkin bersih atau kotor. Jadi
jml kemungkinan state = 2 * 22
• Initial State ?
• Successor Function ?
.
• Goal Test ?
• Path Cost ?
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 13 / 38
(KI092301)
Contoh Kasus: Vacuum Cleaner
• Vacuum Cleaner
• States : Berada di salah satu dari
dua lokasi yang ada, yg masing2
mungkin bersih atau kotor. Jadi
jml kemungkinan state = 2 * 22
• Initial State : Sembarang state
• Successor Function :
(kekiri,kekanan,bersihkan)
• Goal Test : Semua lokasi bersih
• Path Cost : Setiap aksi = 1 point
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 14
(KI092301)
Contoh Kasus: 8-Puzzles
• 8-Puzzles
• State : ?
• Initial State : ?
• Successor Function : ?
.
• Goal Test : ?
• Path Cost : ?
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 15 / 38
(KI092301)
Contoh Kasus: 8-Puzzles
• 8-Puzzles
• State : lokasi dari 8 kotak angka dan 1 kotak kosong
• Initial State : Sembarang state
• Successor Function : (kotak kosong bergerak kekiri,
kekanan, keatas atau kebawah)
• Goal Test : Tersusun kotak angka yang diinginkan
• Path Cost : Setiap bergerak bernilai 1
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 16
(KI092301)
Contoh Kasus: 8-Queen
Problem
• 8-Queen Problem
• State : ? .
• Initial State : ? .
• Successor Function : ?
.
• Goal Test : ?
.
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 17
(KI092301)
Contoh Kasus: 8-Queen
Problem
• 8-Queen Problem
• State : susunan 0..8 ratu pada
papan catur
• Initial State : Tidak ada ratu pada
papan catur
• Successor Function : Masukkan
ratu ke papan catur
• Goal Test : Tidak ada ratu yang
saling serang
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 18 / 38
(KI092301)
Real World Problem
• Airline Travel Problem
• Touring Problem
• Traveling Salesman Problem
• VLSI Layout
• Robot Navigation
• Automatic Assembly Sequencing
• Internet Searching
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 19 / 38
(KI092301)
Searching for Solution
• Search Tree
• Search Node Root of search tree : Initial State : In(Arad)
• Cek node apakah ini goalnya?
• Jika tidak, Expanding menghasilkan state baru
• State mana yang akan di expand? search strategy
• Representasi Node :
• State
• Parent-Node
• Action
• Path-Cost
• Depth
• Fringe node collection hasil generate yang belum diexpand
Function Tree-Search(problem,strategy) return a solution or a failure
initialize the search tree using the initial state
loop do
if there are no candidates for expansion then return failure
choose a leaf node for expansion according strategy
if the node contains a goal state then return the coresponding solution
else expand the node and add the resulting node to the search tree
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 20 / 38
(KI092301)
Contoh Search Tree
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 21 / 38
(KI092301)
Tree Search Secara Umum
Function Tree-Search(problem,fringe) return a solution or a failure
fringe Insert(Make-Node(Initial-State[problem]),fringe)
loop do
if empty ?(fringe) then return failure
node Remove-First(fringe)
if Goal-Test[problem] applied to State[node] succeds then
return Solution(node)
fringe Insert-All(Expand(node,problem),fringe)
_________________________________________________________________________
Function Expand(node,problem) return a set of nodes
successor the empty set
for each (action,result) in Successor-Fn[problem](State[node]) do
s a new Node
State[s] result
Parent-node[s] node
Action[s] action
Path-Cost[s] Path-Cost[node] + Step-Cost(node,action,s)
Depth[s] Depth[node] + 1
add s to successor
return successors
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 22 / 38
(KI092301)
Search Strategies
• Strategy memilih node yang akan diexpand :
• Completeness Menemukan solusi jika ada
• Optimality Optimal solution (cost terkecil)
• Time Complexity berapa lama menemukan
solusinya ?
• Space Complexity berapa banyak memory yang
dibutuhkan ?
• Time dan Space Complexity bisa dilihat dari
ukuran :
• b maks branch factor
• d depth dari solusi terkecil
• m maks depth dari state space
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 23 / 38
(KI092301)
Uninformed Search Strategies
• Breadth-First search
• Uniform-cost search
• Depth-first search
• Depth-limited search
• Iterative deepening search
• Bidirectional search
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 24 / 38
(KI092301)
Breadth-First Search (BFS)
• Setelah Root di expand, selanjutnya
successor dari root, selanjutnya successor
dari successor mereka expand melebar
• Mengimplementasikan fringe FIFO
A
B C
D E F G
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 25 / 38
(KI092301)
Keterangan pada BFS
• Complete ? Ya, jika b terbatas
• Time ? 1 + b + b + b + … + b + b(b -1) = O(b )
2 3 d d d+1
• Space ? O(bd+1)
• Optimal ? Ya, jika semua aksi bernilai sama
• Masalah Space & Time. Lihat buku hal
74
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 26 / 38
(KI092301)
Uniform Cost Search
• Hampir sama dengan BFS melebar
• Bedanya pada pemilihan node yang akan diexpand cost
terkecil
• Fringe = queue berdasarkan cost terkecil
• Jika masing-masing node memiliki cost yang sama = BFS
• Complete ? Ya jika step cost >= Є (positif const)
• Time ? O(b C*/ Є) ; C* = Optimal solution
• Jumlah node dengan g <= cost optimal solution
• Space ? O(b C*/ Є)
• Jumlah node dengan g <= cost optimal solution
• Optimal ? Ya, node diekspand urutan penambahan g(n)
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 27 / 38
(KI092301)
Depth-First Search (DFS)
• Expand node yang terdalam • Complete ?
•
• Fringe LIFO Tidak jika memiliki depth tak
terbatas,
• Modifikasi untuk limited
depth
• Ya, jika depth terbatas
A • Time ? O(bm)
• Bermasalah jika m jauh lebih
besar dari d
B C
• Jika solusinya
banyak/dense, bisa lebih
cepat dari BFS
• Space ? O(bm), linier space
D E F G • Optimal ? Tidak
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 28 / 38
(KI092301)
Depth-Limited Search
• Sama dengan DFS dengan deep limit l
• Implementasi dengan Rekursif
Function Depth-Limited-Search(problem,limit) return a solution or a failure/cutoff
return Recursive-DLS(Make-Node(Initial-State[problem]),problem,limit)
Function Recursive-DLS(node,problem,limit) return a solution or failure/cutoff
cutoff_occured? false
if Goal-Test[problem](State[node]) then return solution
else if Depth[node] = limit then return cutoff
else for each successor in Expand(node,problem) do
result recursive-DLS(successor,problem,limit)
if result cutoff then cutoff_occured? true
else if result <> failure then return result
if cutoff_occured? Then return cutoff
else return failure
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 29 / 38
(KI092301)
Iterative-deepening Search
• Merupakan DFS yang diiterasi berdasarkan
kedalamannya
• Mengkombinasi DFS dan BFS
• Bottom level digenerate 1x, sedangkan
dilevel berikutnya digenerate 2x, 3x dan
seterusnya
Function Iterative-Deepening-Search(problem) return a solution or a failure
input problem // a problem
for depth 0 to do
result Depth-Limited-Search(problem,depth)
if result <> cutoff then return result
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 30 / 38
(KI092301)
Iterative-deepening Search
Limit = 3
0
1
2 A
B C
D E F G
H I J K L M
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 31 / 38
(KI092301)
Keterangan pada IDS
• Complete ? Ya
• Time ? (d+1)b0 + (d)b + (d-1)b2+…+bd= O(bd)
• BFS menggenerate node sampai d + 1 sementara IDS hanya d
IDS lebih cepat dari BFS
• Space ? O(bd)
• Optimal ? Ya, jika memiliki cost yang sama untuk
tiap aksi
• Bisa dimodifikasi untuk uniform cost
• Perbandingan IDS >< BFS : b = 10; d = 5
• N(IDS) : 50 + 400 + 3.000 + 20.000 + 100.000 = 123.450
• N(BFS) : 10 + 100 + 1.000 + 10.000 + 100.000 + 999.990 = 1.111.100
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 32 / 38
(KI092301)
Bidirectional Search
• Mencari dari 2 arah secara simultan
• Motivasi bd/2 + bd/2 jauh lebih kecil dari bd
• Misal d = 6, masing2 menggunakan BFS depth=3, b=10;
dengan bidirectional hanya 22.200 node sedang dengan
BFS standar mencapai 11.111.000 node
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 33 / 38
(KI092301)
Perbandingan: Uninformed
search strategies
Criteria BFS Uniform DFS DLS IDS bdirect
Complete Ya Ya No No Ya Ya
Time O(bd+1) O(bC*/ Є) O(bm) O(bl) O(bd) O(bd/2)
Space O(bd+1) O(bC*/ Є) O(bm) O(bl) O(bd) O(bd/2)
Optimal Ya Ya No No Ya Ya
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 34 / 38
(KI092301)
Menghindari Repeated States
• Pada beberapa kasus, ada kemungkinan terjadi state
yang berulang looping
• solveable problem unsolveable problem
• Dibuat closed list menyimpan node yang sudah
diexpand
• Node yang tidak bisa diexpand open list
Function Graph-Search(problem,fringe) return a solution or a failure
closed empty set
fringe Insert(Make-Node(Initial-State[problem]),fringe)
loop do
if empty ?(fringe) then return failure
node Remove-First(fringe)
if Goal-Test[problem](State[node]) then return Solution(node)
if State[node] is not in closed then
add State[node] to closed
fringe Insert-All(Expand(node,problem),fringe)
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 35
(KI092301)
Pencarian dengan Informasi Parsial
• Deterministic, Fully Observable Single state problem
• Agent tahu pasti state-state apa saja yang akan dimasuki
• Solusi berupa sequence
• Non Observable Sensorless/Conformant Problem
• Agent masih belum tahu pasti dimana posisinya
• Solusi (jika ada) berupa sequence
• Nondeterministic and/or partially observable
contingency problem
• Percept memberikan informasi baru mengenai kondisi saat itu
• Solusi berupa tree or policy
• Interleace search
• Unknown state space Exploration Problem (“online”)
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 36 / 38
(KI092301)
Ringkasan
• Problem solving agents
• Perumusan masalah state space
• Pencarian solusi penelusuran search tree
• Breadth-first search: completeness terjamin, tapi rakus memory
• Uniform-cost search: mirip BFS, optimality terjamin jika cost path
untuk > 0
• Depth-first search: Space complexity linier, tetapi tidak complete
(maupun optimal)
• Depth-limited search: mirip DFS, tetapi kedalaman search dibatasi
sampai
• Iterative-deepening search: lakukan DLS secara bertahap dengan =
0, 1, 2, . . ..
• Pengulangan state bisa dihindari dengan mencatat state yang
sudah pernah dicoba
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 37 / 38
(KI092301)
Sumber :
1. Slide perkuliahan Stuart Russell's (Berkeley) [Link]
2. Slide perkuliahan Sistem Cerdas Ruli Manurung (Universitas Indonesia)
[Link]
12/7/2012 Problem-Solving Agent & Search @ Kecerdasan Buatan 38 / 38
(KI092301)