TUGAS RANGKUMAN “ARTIFICIAL INTELLIGENCE” Universitas "45" Makassar

TUGAS RANGKUMAN “ARTIFICIAL INTELLIGENCE”

BAB III

NAMA : AKBAR RAHMAN

NIM : 4512073027

PRODI : MANAJEMEN INFORMATIKA

Rangkuman kali ini saya membahas beberapa poin yaitu sebagai berikut:

BAB 3. REASONING

3.1    Propositional Logic (Propositional Calculus)

3.1.1 Tata bahasa pada propositional logic

3.1.2 Semantik pada propositional logic

3.1.3 Aturan inferensi untuk  propositional logic

3.1.4 Masalah dunia wumpus

3.1.5 Knowledge based system (KBS)

3.1 Propositional Logic (Propotional Calculus)

          Sebagai logic yang paling sederhana ,propositional logic sangat mudah dipahami dan membuat kita lebih mudah membedahkan teknik reasoning dengan teknik searching. Di sini kita akan melihat penggunaan propositional logic untuk suatu permainan sederhana

3.1.1 Tata bahasa pada propositional Logic

            Secara sintak ,simbol-simbol yang digunakan pada propositional logic adalah: logical constans (true and false),propositional symbols (misalnya P or Q),logical connectives (˄,˅,↔,→,¬),dan kurang buka/tutup ‘( )’,Secara formal,tata bahasa propositional logic diilustrasikan oleh gambar 3-2 berikut ini [RUS95]

Sentence → AtomicSentence | ComplexSentence AtomicSentence → True|False                                  |P|Q|R|... ComplexSentence → (Sentence)                                    |Sentence Connective Sentence                                    | ¬ Sentence Connective →  (˄|˅|ó| => )

­­

Gambar 3.2 : Tata bahasa menggunakan BNF (Backus Naur Form) untuk sentence propositional logic

Berdasarkan gambar diatas kita dapat membangun kalimat atomik yang sederhana maupun kalimat kompleks. Sebagai contoh True adalah sebuah kalimat atomik. P juga merupakan sebuah kalimat atomik.P ˄ Q adalah sebuah kalimat kompleks yang terdiri dari dua buah kalimat atomik yang dihubungkan dengan penghubung ˄. Contoh kalimat kompleks yang lain adalah (P˄Q) → R

3.1.2 Sematik pada Propositional Logic

Secara semantik, propositional logic sangatlah sederhana. Kita tinggal mendefinisikan nilai kebenaran ‘TRUE’ atau ‘FALSE’ pada setiap simbol. Sebuah simbol P dapat menyatakan fakta apapun yang kita inginkan,misalnya P bisa berarti’Bandung adalah kota yang nyaman’ dan  Q berarti ‘Bandung kota yang selalu macet’. Sedangkan logical constants,’Trues’ menyatakan konstanta yang selamanya bernilai benar dan ‘False’ menyatakan konstata yang selamanya bernilai salah.

Setiap penghubung (connective) bisa dibayangkan sebagai suatu fungsi.sematik untuk kelima penghubung yang ada diilustrasikan oleh tabel 3-2 berikut ini.

Tabel 3-2: tabel kebenaran untuk kelima penghubung (connective)

P	Q	¬P	P˄Q	P˅Q	P→Q	P↔Q
False False True True	False True False True	True True False False	False False False True	False True True True	True True False True	True False False True

3.1.3 Aturan inferensi untuk propositional logic

Inference atau inferensi dapat diartikan sebagai proses menurunkan kalimat baru dari kalimat-kalimat yang sudah ada menggunakan aturan-aturan inferensi (inference rules). Sedangkan reasoning adalah proses penalaran untuk membuat suar]tu kesimpulan atau keputusan , daiman proses ini membutuhkan satu atau lebih proses inferensi sampai didapatkan kesimpulan yang diinginkan. Tujuh aturan inferensi untuk propositional logic diilustrasikan oleh gambar 3-3 berikut ini [RUS95]

1.      Modus ponens atau implication-elimination:                            2.      And-elimination: α1 ˄ α2 ˄...˄ αn           αi 3.      Or-Introduction:         αi α1 ˅ α2 ˅...˅ αn 4.      And-Introduction: α1, α2,... αn α1˄ α2˄...˄ αn 5.      Double-negation-elimination: ¬¬α               α 6.      Resolution: α˅β, ¬β ˅ γ evikalen dengan ¬α =>β, β=>γ    α˅γ                                           ¬α => γ 7.      Unit resolution: α˅β,¬β     α

Gambar 3-3: tujuh aturan inferensi untuk propositional logic

Pada aturan inferensi di atas, aturan modus ponens α => β, α   dapat dibaca:

                                                                                          β

“Jika terdapat kalimat α => β dan ada kalimat lain yaitu α , maka dapat diturunkan sebuah kalimat baru yaitu β” .Pada tabel dibawah kali ini mengilustrasikan bahwa jika kalimat α=> β benar dan α juga benar maka β pasti benar.

Tabel 3-3: tabel kebenaranuntuk α => β

α	β	α => β
False False True True	False True False True	True True False True

Aturan And-Elimination (Atau Penghilangan ˄) dapat dibaca: “Jika kalimat α_{1 ˄} α2 ˄...˄α_n benar, maka dapat diturunkan sebuah kalimat baru, yaitu α₁ yang menayatakan sala satu dari kalimat: α₁ , α₂ , ... atau α_n yang berdiri sendiri (tanpa penghubung ˄)”

Aturan And-Itroduction (atau pemunculan ˄) merupakan kebalikan dan atutan And-Elimination. Jika _n kalimat α₁ ˄ α_{2 ˄...˄} α_n. Aturan Or-Introduction (atau pemunculan ˅) menyatakan bahwa jika kalimat α_i benar (dimana i = 1 sampai n), maka dapat dibuat kalimat baru yaitu α_{1 ˅} α_{2 ˅...˅} α_n  . Pada tabel 3-2 dinyatakan bahwa jika sala satu dari kalimat P atau kalimat Q adalah benar,maka kalimat P˅Q adalah benar. Hal ini berlaku untuk lebih dari dua kalimat yang dihubungkan dengan ˅. Aturan Double-negation-elimination sudah jelas bahwa jika ¬¬ α maka α.

Aturan Unit Resolution menyatakan bahwa jika α ˅ β dan terdapat kalimat ¬β ,maka α . Hal ini dapat dijelaskan menggunakan tabel 3-2, dimana jika sala satu dari kalimat P atau kalimat Q adalah benar , maka kalimat P˅Q adalah benar. Jika Q salah , maka P harus benar supaya P˅Q tetap benar.

3.1.4  Masalah Dunia Wumpus

Untuk mempermudah pemahaman tentang propositional logic ,perhatikan sebuah studi berupa permainan Dunia Wumpus berikut [RUS95].

Masalah 3-1: Dunia Wumpus

Wumpus adalah seekor monster yang tinggal disebuah gua yang terbagi dalam 16 ruangan (lihat gambar 3-4). Di dalam gua terdapat 3 lubang mematikan (Pit) yang mengeluarkan angin (Breeze) sehingga sampai di ruangan-ruangan disekitarnya. Wumpus mengeluarkan bau busuk (Stench). Wumpus menjerit (Scream) dan mati jika terkena panah. Sebuah agent dilengkapi dengan tiga anak panah yang hanya bisa diarahkan menuju ruangan-ruangan yang searah dengan arah agent meghadap. Agent bisa bergerak hadap kanan, hadap kiri, atau maju. Agent memanjat keluar gua jika berada pada posisi terjepit ,agent akan benjol (bump) jika menabrak dinding gua.Agent akan mati jika memasuki kotak yang terdapat Wumpus atau Pit ,tetapi akan aman jika memasuki kotak yang didalamnya ada Wumpus yang telah mati. Saat permainan dimulai ,Agent berada pada posisi (1,1). Tugas agent adalah menemukan emas dan membawahnya kembali ke kotak start (1,1) secepat mungkin dengan jumlah aksi yang seminimum mungkin,tanpa terbunuh. Sebagai hadiah, 1000 poin diberikan pada agent jika berhasil keluar gua dengan membawa emas. Tetapi agent mendapat poin -1 untuk setiap aksi yang dilakukan dan -10.000 jika agent terbunuh.

Stech		Breeze	Pit
Wumpus Stench	Breeze, Stench, Gold(glitter)	Pit	Breeze
Stench		Breeze
START Agent →	Breeze	Pit	Breeze

4

3

2

1
                        1                      2                                  3                      4

Gambar 3-4: Permainan di dunia wumpus

Masalah dunia wumpus dapat dirumuskan ke dalam tiga kelompok: percept, action, dan goal, sebagai berikut:

1.  Percept (sesuatu yang ditangkap oleh agent)

·         Pecept : [stecnh , breeze , glitter , bump , scream]

·         [stecnh breez, Non, None, None] = ada stecnh dan breeze, tetapi tidak ada glitter, bump, ataupun scream.

2.  Action (aksi yang dapat dilakukan oleh agent)

·         Move   : Hadap kiri, hadap kanan, atau maju

·         Grab   : Mengambil objek yang berada dikotak dimana agent berada

·         Shoot  : Memanah dengan arah lurus sesuai dengan arah agent menghadap

·         Climb  : memanjat keluar gua

3. Goal (Tujuan)

Menemukan emas dan membawahnya kembali ke kotak start (1,1) secepat mungkin dengan jumlah action yang seminimum mungkin , tanpa terbunuh. Hadiah 1000 poin diberikan kepada agent jika berhasil keluar gua dengan membawa emas. Tetapi agent mendapatkan -1 untuk action yang dilakukannya dan -10000 jika Agent terbunuh.

Apakah masalah Wumpus ini bisa diselesaikan dengan teknik searching? Tentu saja bisa, pertama suatu state dinyatakan dengan 16 ruangan dengan posisi-posisi Wumpus , pit dan gold. Operator dan aturan produksinya ada enam yaitu: hadap kiri ,hadap kanan ,maju ,memanah ,mengambil objek, dan memanjat keluar gua. Dengan mengidentifikasikan intial state,goal state,dan strategi searching , maka kita dapat menyelesaikan masalah tersebut. Tetapi , representasi state tersebut akan membutuhkan memori sangat besar

Jika masalah ini diselesaikan dengan teknik reasoning menggunakan propotional logic ,kita harus mepresentasikan fakta atau keadaan kedalam simbol-simbol propotional logic, beberapa simbol yang digunakan ialah :

·         S_1,2 menyatakan ada stench dikotak (1,2)

·         B_2,1menyatakan ada breeze dikotak (2,1)

·         G_2,3menyatakan ada glitter dikotak (2,3)

·         M_1,4menyatakan bump dikotak (1,4)

·         C_1,3menyatakan ada scream dikotak (1,3)

·         W_1,3menyatakan ada wampus dikotak (1,3)

·         ¬S_1,1menyatakan tidak ada stench diposisi (1,1)

3.1.5 Knowledge-Based System (KBS)

Agent disini dapat dikatakan sebagai knowledge-based system karena agent akan melakukan aksi berdasarkan hasil penalaran suatu percept terhadap Knwoledge Based (KB) yang dimilikinya. Pada awal permainan, didalam KB tidak ada fakta sama sekali karena agent belum menerima percept. KB hanya berisi beberapa aturan (rule) yang merupakan pengetahuan tentang environment , misalnya seperti gambar 3-5 dibawah ini. Aturan R₁ dapat dibaca: “jika tidak ada stench di (1,1) maka tidak ada Wumpus di (1,1), (1,2), maupun (2,1)”.

R1: ¬S1,1      => ¬W1,1 ˄ ¬W1,2 ˄ ¬W2,1 R2: ¬S2,1      => ¬W1,1 ˄ ¬W2,1 ˄ ¬W2,2 ˄ ¬W3,1 R3: ¬S1,2     => ¬W1,1 ˄ ¬W1,2 ˄ ¬W2,2 ˄ ¬W1,3 R4: ¬S1,2     => ¬W1,3 ˄ ¬W1,2 ˄ ¬W2,2 ˄ ¬W1,1 ... R33: ¬B1,1  =>  ¬P1,1 ˄ ¬P1,2 ˄ ¬P2,1 R34: B2,1    => P1,1 ˅  P2,1 ˅  P2,2 ˅  P3,1 ...

         

Gambar 3-5: Pengetahuan tentang Environment yang memiliki Agent

Untuk melakukan aksi yang tepat, agent harus dibekali aturan untuk menerjemahkan pengetahuan menjadi aksi sebagai contoh aturan yang bisa di gunakan adalah sebangai berikut:

T1 : A2,1 ˄ EastA ˄ P3,1                           => ¬Forward  T2 : A1,2  ˄ NorthA ˄ W1,3       => ¬Forward

Gambar 3-6: Aturan penerjemahanaan (Translation) pengetahuan menjadi aksi

Pada setiap langakah, percept yang diterima agent dikonversi mejadi suatu kalimat dan dimasukkan ke dalam KB bersama dengan kalimat-kalimat lain yang di anggap benar oleh kalimat yang telah diterima sebelumnya. Perhatikan gambar 3-4 diatas , pada saat agent berada diposisi (1,1) dan dimualai menerima percept maka percept yang diterima agent adalah [None, None, None, None, None] yang artinya tidak ada stecnh, breeze, glitter, bump, ataupun scream.

            Proses infrensi dilakukan sampai dihasilkan kalimat yang pailng sederhana atau bahkan atomik. Setelah proses infrensi tersebut maka terdapat enam fakta baru yang ditambhakan kedalam KB , sehingga menjadi:

¬S1,1    ¬B1,1      ¬G1,2    ¬M1,1   ¬C1,2           ¬W1,1       ¬P1,1                                                                                            ¬W2,1        ¬P2,1                                                                                             ¬W1,2        ¬W1,2

Gambar 3-7: kondisi Knowledge Base setelah agent menerima percept pertama diposisi (1,1)

            Dari KB yang baru ini dapat diketahui bahwa diposisi (1,2) dan (2,1)ada ada wumpus ada pit sehingga aman bagi agent untuk melangkah ke posisi (1,2) ataupun (2,1), misalnya agent adalah [None, Breeze, None, None, None] yang artinya ada Breeze, tetapi tidak ada stench, bump, ataupun scream.supaya ebih fokus pada penemuan lokasi wumpus , maka infrensi hanya dilakukan pada kalimat yang berhubungan dengan wumpus dan Pit yaitu  ¬S_2,1 dan ¬B_2,1. Perhatikan proses infresnsi dibawah ini:

·         Lakukan Modus Ponens untuk ¬S_2,1  dan  R₂  sehingga diperoleh:

¬W1,1 ˄ ¬W2,1 ˄ ¬W2,2 ˄ ¬W3,1

·         Lakukan And-Elimination terhadap hasil tersebut sehinggal diperoleh:

˄ ¬W_1,1   ˄ ¬W_2,1   ¬W_2,2  ¬W_3,1

·         Lakukan Modus Ponens untuk B_2,1 dan R₃₄ sehingga diperoleh:

P1,1 ˅ P2,1 ˅ P2,2 ˅ P3,1

·         Lakukan Unit Resolution terhadap hasil tersebut dengan ¬P_1,1 kemudian ¬P_2,1 sehingga dapat P2,2 ˅ P3,1

Setelah proses infrensi tersebut, maka terdapt tiga kalimat (fakta) baru yang ditambahkan ke dalam KB, sehingga menjadi:

¬S1,1  ¬B1,1  ¬G1,2 ¬M1,1  ¬C1,2                ¬W1,1         ¬P1,1           P2,2  ˅ P3,1                                                                                       ¬W2,1         ¬P2,1                                                                                       ¬W1,2         ¬P1,2                                                                                        ¬W2,2                                                                                        ¬W3,1

Gambar 3-8: Kondisi Knowledge Base setelah agent menerima percept kedua pada posisi (2,1)

            Kalimat P_2,2  ˅ P_3,1  menyatakan bahwa ada pit diposisi (2,2) atau (3,1), sehingga langkah yang aman bagi agent adalah kembali ke posisi (1,1), pada Kb gambar 3-7 terapat kalimat ¬W_1,2  dan ¬P_1,2  sehingga posisi (1,2) adalah aman. Misalnya agent melangkah pada posisi tersebut , pada posisi tersebut , percept tang diterima agent adalah [Stecnh, None, None, None, None]  yang atrinya ada stench , tetapi tidak ada breeze, glitter, bump, atau scream.

            Supaya lebih fokus pada penenmuan lokasi wumpus, maka infrensi hanya dilakukan pada kalimat yang berhubungan dengan wumpus, yaitu S_1,2. Perhatikan pada kalimat yang berhubungan proses infrensi dibawah ini :

·         Lakukanlah Modus Ponens untuk S_1,2 dan R₄ , sehingga didapat:

W1,3 ˅ W1,2 ˅ W2,2 ˅ W1,1

·         Kemudian lakukan Unit Resolution trerhadap hasil diatas dengan ¬W_2,2 , sehingga didapat _:

W1,3 ˅ W1,2

·         Terakhir , lakukanlah Unit Resolution terhadap hasil diatas dengan ¬W_1,2, sehingga memberikan kesimpulan bahwa Wumpus berada diposisi (1,3):W1,3

Ketika lokasi wumpus sudah diketahui agent bisa menggunakan panah untuk membunuhnys atau fokus pada pencarian emas dengan menghindari lokasi wumpus.kita bisa membuat berbagai strategi sehingga bisa membawa emas kembali keposisi (1,1) dengan jumlah aksi yang seminimum mungkin.

Pada kasus wumpus tersebut agent harus dibekali aturan yang merupakan pengetahuan tenatang Environment(gambar 3-5) danaturan untuk menterjemahakan pengetahuan menjadi aksi(3-6). Utnuk 16 ruangan yang ada di dalam gua diperlukan sangat banyak aturan tentang Environment ada aturan penterjemah. Pada kasus wumpus ini, teknik manakah yang lebih efisien dalam reprentasikan masalah, searching atau reasoning