informed search (heuristic) &...
TRANSCRIPT
Informed Search (Heuristic) &
Eksplorasinya
Chastine Fatichah
Teknik Informatika
Institut Teknologi Sepuluh Nopember
November 2012
12/8/2012 1 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Kecerdasan Buatan (KI092301)
Pokok Bahasan
• Uninformed search strategies
• Best-first search
• Greedy best-first search
• A* Search
• Heuristic
• Ringkasan
12/8/2012 2 / 21 Informed Search (Heuristic) & Eksplorasinya @ Kecerdasan
Buatan (KI092301)
Informed Search Strategies
• Uninformed Search : menggenerate state baru, di cek apakah goal atau tidak kurang efisien
• Informed Search menggunakan informasi tambahan lebih efisien
• Bahasan : • Best-First Search
• Greedy Best-First Search
• A* Search
• Heuristics
12/8/2012 3 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Best-first Search
• Secara umum sama dengan Tree-Search
ataupun Graph-Search
• Node yang diexpand berdasarkan evaluation
function f(n) fungsi yang menyatakan perkiraan
seberapa “bagus” sebuah node dipilih yang
terkecil
• Fringe sebuah antrian (queue) di mana node
diurutkan berdasarkan f(n)
• Contoh: • Greedy best-first search
• A* search
12/8/2012 4 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Step Cost & Straight-Line Distance
12/8/2012 5 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Straight-Line Distance
• Arad 366
• Bucharest 0
• Craivora 160
• Dobreta 242
• Eforie 161
• Fagaras 176
• Giurgiu 77
• Hirsova 151
• Iasi 226
• Lugoj 244
• Mehadia 241
• Neamt 234
• Oradea 380
• Pitesti 100
• Rimnicu Vilcea 193
• Sibiu 253
• Timisoara 329
• Urziceni 80
• Vaslui 199
• Zerind 374
12/8/2012 6 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Greedy best-first Search
• Evaluation Function h(n) (Heuristics)
= Estimasi cost dari n ke goal terdekat
Misalnya, hSLD(n)=Straight-Line Distance (jarak
lurus) dari Bucharest
• Best First Search mengekspand node
yang kelihatan mendekati goal
12/8/2012 7 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Contoh Greedy best-first Search
Arad 366 Arad
Sibiu Timisoara
Zerind
253 329
374
Sibiu
Arad Fagaras Rimnicu Videa
366 176 193
Oradea
380
Fagaras
Sibiu
253
Buchares
0
Buchares
12/8/2012 8 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Keterangan Greedy best-first
Search • Complete ?
• Tidak, bisa terjadi looping, misal : Oradea sebagai goal : Iasi Neamt Iasi Neamt …
• Time ? • O(bm) namun dengan heuristic yang baik akan
memberikan improvement yang besar
• Space ? • O(bm) Setiap node disimpan dalam memory
• Optimal ? • Tidak, perhatikan kasus rute ke Bucharest
sebelumnya, mestinya tidak melalui Fagaras untuk mencapai optimalnya
12/8/2012 9 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
A* Search
• Ide : Menghindari expanding path yang mahal
• Evaluation Function : f(n) = g(n) + h(n) • g(n) = Cost yang dicapai sampai di n
• h(n) = Estimasi cost untuk sampai pd goal dari n
• f(n) = Estimasi total cost dari path n sampai goal
• A* : admissible heuristic tidak overestimate • h(n) <= h*(n) dimana h*(n) cost sebenarnya
• h(n) >= 0 sehingga h(G) = 0 untuk goal G
• Contoh, hSLD(n) tidak overestimate terhadap jarak pada jalan sebenarnya
• A* search Optimal 12/8/2012 10 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Arad 366 = 0 + 366 Arad
Sibiu Timisoara
Zerind
393 = 140 + 253 447 = 118 + 329
449 = 75 + 374
Sibiu
Arad Fagaras Rimnicu Videa
646 = 280 + 366 415=239+176 413=220+193
Oradea
671=291+380
Contoh A* Search
Fagaras
Sibiu
591=338+253
Buchares
450=450+0
Rimnicu Videa
Craiova
526 = 366 + 160
Sibiu Pinesti
553=300+253 417=317+100
415=239+176
417=317+100
Sibiu
591=338+253
Rimnicu Videa
450=450+0
Bucharest
Pinesti
418=418+0
Bucharest
413=220+193 415=239+176
12/8/2012 11 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
• Seperti pada kasus sebelumnya, misal jika ada G2 (goal lain
yang suboptimal) yang telah digenerate dan masuk dalam
queue.
• Dan diketahui n merupakan node yang belum diexpand pada
path terpendek menuju Goal yang optimal
• f(G2) = g(G2), karena h(G2) = 0
> g(G1), karena G2 suboptimal
>= f(n), karena h admissible
• Karena f(G2) > f(n), maka A* tidak akan mengexpand G2
Pembuktian Optimalitas A*
12/8/2012 12 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Optimalitas A* (Kegunaan) • Lemma : A* mengexpand node menambah nilai f
• Dan secara berangsung-angsur menambah “f-
countour” node-node (bandingkan BFS yang
menambah layer)
• Countour i memiliki node-node dg f=fi dimana fi<fi+1
12/8/2012 13 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Keterangan A* Search
• Complete ? • Ya, selama jumlah node f <= f(G) terbatas
• Time ? • Exponensial
• Space ? • Setiap node disimpan dalam memory
• Optimal ? • Ya
• A* mengekspand node-node dengan f(n) < C*
• A* mengekspand beberapa node dengan f(n)=C*
• A* Tidak akan mengekspand node dengan f(n)>C*
12/8/2012 14 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Pembuktian Lemma : Consistency
• Fungsi Heuristic h(n) dikatakan konsisten jika setiap node n
dan setiap successor n’ dari n yang digenerate action a,
maka estimasi cost dari n sampai ke goal tidak lebih besar
dari cost sampai step n’ + estimasi cost n’ ke goal
• h(n) <= c(n,a,n’) + h(n’)
• Jika h(n) konsisten
maka nilai dari f(n) melalui suatu
path tidak berkurang/nondecreasing
• f(n’) = g(n’)+h(n’)
= g(n) + c(n,a,n’) + h(n’)
>= g(n) + h(n)
= f(n)
12/8/2012 15 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Heuristic Function
• Contoh pada 8-puzzles,
• Rata2 b = 3, d =22
• Dgn menghilangkan repeated state, total state
menjadi 9!/2 = 181.440 (tidak terlalu besar)
• Tetapi jika pada 15-puzzle ? Secara
kasarnya mencapai 1013 state (wow!!!)
• Dibutuhkan suatu good heuristic function
12/8/2012 16 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
8-Puzzle Heuristic Function • Contoh pada 8-puzzles, diusulkan 2 h(n)
• h1 = Jumlah kotak yang salah penempatan
• h2 = Manhatan distance jumlah dari jarak masing-
masing kotak ke tujuan, dengan aturan aturan tidak bisa
bergerak secara diagonal
• Contoh :
• h1 = 8
• h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
• Dari kedua fungsi heuristic tersebut sudah sama-sama
tidak overestimate (solusi sebenarnya = 26 step)
12/8/2012 17 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Pengaruh Akurasi Heuristic pada
Performanya • Cara menentukan kualitas
heuristic adalah dengan efective branching factor b*
N+1 = 1 + b* + (b*) 2 + ..+ (b*)d
• Misal jika solusi pada d=5 dgn 52 node maka b* = 1.92
• Heuristic yang baik b* mendekati 1
• Jika h2(n)>h1(n) untuk semua n maka h2 dominates h1 dan memberi solusi yg lebih baik
Search Cost Effective Branching
Factor
d IDS A*(h1) A*(h2) IDS A*(h1) A*(h2)
2 10 6 6 2.45 1.79 1.79
4 112 13 12 2.87 1.48 1.45
6 680 20 18 2.73 1.34 1.30
8 6384 39 25 2.80 1.33 1.24
10 47127 93 39 2.79 1.38 1.22
12 3644035 227 73 2.78 1.42 1.24
14 - 539 113 - 1.44 1.23
16 - 1301 211 - 1.45 1.25
18 - 3056 363 - 1.46 1.26
20 - 7276 676 - 1.47 1.27
22 - 18094 1219 - 1.48 1.28
24 - 39135 1641 - 1.48 1.26
12/8/2012 18 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Relaxed Problem
• Relaxed Problem mengurangi action pada problem
• Admissible Hueristic dapat diturunkan dari exact solution
pada relaxed problem
• Jika rule 8-puzle dikendurkan(relaxed) sehingga setiap
kotak bisa berpindah kemanapun, maka h1(n) akan
memberikan solusi terpendek
• Jika perpindahan hanya boleh untuk yang berdekatan
saja, maka h2(n) memberikan solusi terpendek
• Key Point: biaya solusi optimal dari relaxed problem
tidak lebih besar dari biaya solusi optimal problem
sebenarnya
12/8/2012 19 / 21 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301)
Ringkasan
• Heuristic functions mengestimasi biaya pada rute
terpendek
• Good heuristics dapat secara drastis mengurangi biaya
pencarian
• Greedy best-first search mengekspan h terkecil
• incomplete dan tidak selalu optimal
• A* search mengekspan g + h terkecil
• complete dan optimal
• optimally efficient (up to tie-breaks, for forward
search)
12/8/2012 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301) 20 / 21
12/8/2012 Informed Search (Heuristic) & Eksplorasinya @
Kecerdasan Buatan (KI092301) 21 / 21
Sumber :
1. Slide perkuliahan Stuart Russell's (Berkeley) http://aima.cs.berkeley.edu/