Artificial Intelligence
3
PROBLEM SOLVING & SEARCH Problem : z Definisi problemnya jelas z
Ada cara-cara yang jelas juga untuk pemecahan problem tsb.
∴ AI’s PROBLEM : ¾ Segala problem, kecuali problem yang sudah mempunyai cara/teknik pemecahan yang pasti, seperti persamaan linear. ¾ Try and error cara-cara yang paling cocok untuk pemecahan suatu permasalahan (searching).
1. REPRESENTASI PROBLEM z Maze Mencari path atau rute dari start ke goal.
Goal
4 3
2 Start 1
2
3
4
Untuk pemecahan problem ini, caranya adalah penelusuran mencari jalan. Dengan sekali telusuran, akan terjadi perpindahan dari satu titik ke titik lain (transisi state). Gerakan terjadinya perpindahan tersebut disebut dengan operator. Dan dengan menentukan sederetan operator yang tepat, maka problem akan terpecahkan. z
Building Blocks Kalau di maze problem, absolut position adalah hal yang penting, tapi kalau di building blocks, relative position-lah yang lebih penting. Untuk merepresentasikan state/keadaan, biasanya digunakan “state description”. Misalnya, untuk building blocks ini, kita gunakan state description sebagai berikut:
Artificial Intelligence
4
ON(u,v) u,v Table
: Block u berada diatas v : variable dari block : menunjukkan meja A
A C
B B
Initial State
C Goal State
ON(A,C) ON(B,TABLE)
ON(A,B) ON(B,C)
ON(C,TABLE)
ON(C,TABLE)
Dan sebagai operator untuk memindahkan dari satu state ke state lain, kita bisa gunakan:
Pickup(u) Putdown(u) Takeoff(u,v) Puton(u,v)
Problem disinipun sama seperti pada maze problem, yakni mencari dan menentukan sederetan urutan operator-operator yang dapat menghantarkan dari initial state ke goal state.
STATE SPACE Dengan operator, transisi state dapat terjadi. Transisi state dapat dianggap sebagai perubahan posisi dalam state space. State space untuk maze problem, sudah jelas dari awal, sementara untuk building blocks problem tidak. Untuk menunjukkan posisi dalam state space, diperlukan state description. Pada maze, sebagai state descriptioan adalah posisi orang, sedangkan pada building block adalah posisi blocks.
OPERATOR Adalah alat untuk memindahkan/berpindah dari satu state ke state lain dalam state space PreCondition operator ¾ Delete list suatu operator ¾
: syarat yang harus terpenuhi untuk menjalankan : state description yang terhapus setelah dijalankannya
Artificial Intelligence
5
¾ Add list suatu operator
: state description yang muncul setelah dijalankannya
CONSTRAINT Persyaratan yang harus dipenuhi untuk pencapaian tujuan. Misalnya, untuk maze problem, tidak diperbolehkan belok kiri. Constraint dibuat untuk menyederhanakan permasalahan. Jadi tanpa constraint-pun juga boleh, tapi biasanya akan membuat sistem semakin kompleks. Contoh constraint lain: jalan terpendek.
2. REPRESENTASI STATE SPACE DENGAN GRAPH Graph terdiri dari beberapa node dan edge. Edge menghubungkan 2 node dan edge bisa mempunyai arah dan tidak. Bila pada graph tersebut tidak terdapat loop-ing, maka dikatakan graph tersebut sebagai tree. Jadi pada tree, 2 node hanya dihubungkan oleh satu path/rute. State dari problem dapat diibaratkan sebagai node, dan perpindahan dari satu state ke state yang lain dengan suatu operator dapat diibaratkan sebagai edge. Jadi initial state = initial node, goal state = goal node. Node
START
=
posisi
(1,1)
orang pada sb_x,
3
sb_y Edge = operator,
(2,4)
1
(2,3)
1
karena
(2,2)
satu tidak perlu
1 1
1
(1,4)
label
2
Angka
1 1
(3,4)
1
1
edge
(3,2)
(4,4)
GOAL
cuma
4
(3,1)
disisi adalah
jarak
(3,3)
Graph dari maze problem
3. BASIC SEARCH Problem : pencarian jalan dari start ke goal Basic dari search adalah iterasi dari : Check apakah initial(current) node = goal node Jalankan operator untuk pindah dari node satu ke node lain Biasanya node-node yang akan diperiksa, sudah disimpan terlebih dahulu dalam suatu list, misalnya open. Berikut procedure dari search:
Artificial Intelligence
6
1. masukkan initial node dan node-node ke list open 2. LOOP : if open=kosong then exit (fail) 3. n := first (open) 4. 5. 6. 7.
if goal (n) then exit (n) remove (n, open) refresh (open) goto LOOP
NONHEURISTIC SEARCH Apabila knowledge/pengetahuan terhadap state space dari suatu permasalahan tidak ada, maka pencarian/searching state space harus dilakukan dengan aturan yang konstan. Selama state space-nya mempunyai batas (limited), dan solusi/jawabannya ada, maka dipastikan jawaban tersebut akan didapatkan. Berikut metode searching yang dapat kita lakukan meskipun kita tidak mempunyai pengetahuan tentang state-spacenya. ¾ Depth-first-search Depth-first-tree-search 1. masukkan initial node ke list open 2. LOOP : if open=kosong then exit (fail) 3. 4. 5. 6.
n := first (open) if goal (n) then exit (n) remove (n, open) expand (n), masukkan anak node dari n di bagian depan list
open, hubungkan pointer dari anak node tsb ke n. 7. goto LOOP S
B
A
C
E
D
H
F
G
Perubahan yang terjadi pada list open: (S), (A B), (C D B), (D B), (B), (E F), (H G F), (G F)
Artificial Intelligence
7
Depth-first-search 1. masukkan initial node ke list open 2. LOOP : if open=kosong then exit (fail) 3. n := first (open) 4. if goal (n) then exit (n) 5. remove (n, open) add (n, closed) 6. expand (n), masukkan anak node dari n yang tidak ada pada list open dan list closed di bagian depan list open, hubungkan pointer dari anak node tsb ke n. 7. goto LOOP S
A
C
B
D
F
E
G
H
Perubahan yang terjadi pada list open: (S), (A B), (C D B), (D B), (F B), (B), (E), (G H) ¾ Breadth-first-search 1. masukkan initial node ke list open 2. 3. 4. 5.
LOOP : if open=kosong then exit (fail) n := first (open) if goal (n) then exit (n) remove (n, open)
add (n, closed) 6. expand (n), masukkan anak node dari n yang tidak ada pada list open dan list closed di bagian belakang list open, hubungkan pointer dari anak node tsb ke n. 7. goto LOOP Perubahan yang terjadi pada list open: (S), (A B), (B C D), (C D E), (D E), (E F), (F G H), (G H)
