Masalah Ruang Dan Keadaan

Masalah Ruang Dan Keadaan

Masalah, Ruang Keadaan dan Pencarian

Untuk membangun sistem yang mampu menyelesaikan masalah, perlu dipertimbangkan 4 hal :

1.  Mendefinisikan masalah dengan tepat

Spesifikasi yang tepat mengenai keadaan awal
Solusi yang diharapkan

2.  Menganalisis masalah serta mencari beberapa teknik penyelesaian masalah yang sesuai

3.  Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah

4.  Memilih teknik penyelesaian masalah yang terbaik

Mendefinisikan Masalah sebagai Ruang Keadaan

Untuk mendeskripsikan masalah dengan baik, kita harus :

• Mendefinisikan suatu ruang keadaan
• Menetapkan satu atau lebih keadaan awal
• Menetapkan satu atau lebih tujuan
• Menetapkan kumpulan aturan

Contoh Mendefinisikan Masalah sebagai Ruang Keadaan

Misalkan permasalahan y g an g dihada pi adalah permainan catur, maka harus ditentukan : 

• Posisi awal pada papan catur posisi awal setiap permainan ca tur sel l a u sama, yaitu semua bid ka k diletakkan di atas papan catur dalam 2 sisi, yaitu kubu putih dan kubu hitam.
• Aturan – aturan untuk melakukan gerakan aturan – aturan ini sangat berguna untuk menentukan menentukan gerakan gerakan suatu bidak , yaitu melangkah dari satu keadaan ke keadaan lain. Misalkan untuk mempermudah menunjukkan posisi bidak, setiap kotak ditunjukkan dalam huruf (a,b,c,d,e,f,g,h a,b,c,d,e,f,g,h) pada arah horisontal horisontal dan angka (1,2,3,4,5,6,7,8) pada arah vertikal. Suatu aturan untuk menggerakkan bidak dari posisi (e 2), ke (e 4), dapat ditunjukkan ditunjukkan dengan aturan : if bidak putih pada kotak(e,2), and kotak(e 3), kosong , and kotak(e,4) kosong then g (,) (,) erakkan bidak dari ( e , 2 ) ke ( e , 4 ).
• Tujuan (goal) tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya. Kemenangan ini ditandai dengan posisi raja yang sudah tidak dapat bergerak lagi. Contoh tersebut menunjukkan representasi masalah dalam Ruang Keadaan Keadaan (State Space), yaitu suatu ruang yang berisi semua keadaan yang mungkin. Kita dapat memulai bermain catur dengan menempatkan diri pada keadaan keadaan awal, kemudian kemudian bergerak dari satu keadaan ke keadaan yang lain sesuai dengan aturan yang ada, dan mengakhiri permainan jika salah satu setelah mencapai tujuan

Cara Merepresentasikan Merepresentasikan Ruang Keadaan

• Graph Keadaan
• Pohon Pelacakan
• Pohon AND/OR

Graph Keadaan

Terdiri dari node-node yang menunjukkan keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. Node dihubungkan dengan busur panah untuk menunjuk ke arah keadaan berikutnya.

Graph keadaan dengan node M menunjukkan keadaan awal, node T adalah tujuan. Ada 4 lintasan dari M ke T : 

• M-A-B-C-E-T 

• M-A-B-C-E-HT 

• M-D-C-E-T 

• M - D - C - E - H –T

Lintasan buntu atau lintasan yang tidak sampai ke tujuan : 

• M-A-B-C-E-F-G 

• M-A-B-C-E-I-J 

• M-D-C-E-F-G 

• M-D-C-E-I-J 

• M-D-I-J

Pohon Pelacakan

Struktur pohon digunakan menggambarkan keadaan secara hirarkis, node yang terletak di level-0 disebut akar.

Node akar sebagai keadaan awal/initial state, yang memiliki beberapa cabang yang disebut anak.

Node yang tidak memiliki anak disebut daun/leaf yang menunjukkan akhir dari pencarian, dapat berupa tujuan/goal atau jalan buntu/dead end.

Pohon AND/OR

Masalah M dicari solusinya dengan 4 kemungkinan yaitu A OR B OR C OR D.

Masalah M dapat diselesaikan dengan A AND B AND C AND D

Contoh : Dengan menggunakan pohon AND/OR tujuan yang dicapai pada pohon di Gambar sebelumnya bisa dipersingkat hanya sampai level-2 saja. 

Contoh 1

Seorang petani akan menyeberangkan seekor kambing,seekor serigala,sayuran dengan sebuah perahu melalui sungai. Perahu hanya bisa memuat petani & satu penumpang penumpang yg lain (kambing, serigala, atau sayuran). Jika ditinggalkan petani tersebut, maka sayuran dimakan kambing dan kambing akan dimakan serigala.

Penyelesaian

1. Identifikasi ruang keadaan 

Permasalahan ini dapat dilambangkan dengan (jumlah kambing,jumlah serigala,jumlah sayuran jumlah sayuran,jumlah perahu) .

Contoh : daerah asal (0,1,1,1) = daerah asal tidak ada kambing, ada serigala, ada sayuran, ada perahu.

2. Keadaan Keadaan awal & tujuan. 

    Keadaan awal, pada kedua daerah : 

    Daerah asal = (1 , 1 , 1 ,1) 

    Daerah seberang = (0,0,0,0) 

    Keadaan tujuan, pada kedua daerah : daerah asal = (0,0,0,0) 

    Daerah seberang = (1,1,1,1)

3. Aturan-aturan

4.  Solusi yang ditemukan

Contoh Soal 2

Ada 2 ember masing-masing berkapasitas 4 galon (ember A) dan 3 galon (ember B). Ada pompa air yg akan digunakan digunakan untuk mengisi mengisi air pada ember tersebut. Bagaimana dapat mengisi tepat 2 galon air ke dalam ember berkapasitas 4 galon? 

Penyelesaian

1.Identifikasi ruang keadaan (state space) Permasalahan ini dapat digambarkan sebagai himpunan pasangan bilangan bulat : 

x = jml air yg diisi ke ember 4 galon (ember A) 

y = jml air yg diisi ke ember 3 galon (ember B) Ruang keadaan = (x,y) sedemikian rupa sehingga  x elemen {0,1,2,3,4} dan y elemen {0,1,2,3}

2. Keadaan awal & tujuan 

Keadaan awal : kedua ember kosong = (0,0) Tujuan : ember 4 galon berisi 2 galon air=(2,n) dengan sembarang n 

3. Keadaan ember Keadaan ember bisa digambarkan sebagai berikut :

4. Aturan-aturan 

Diasumsikan kita dapat mengisi ember air itu dari pompa air, membuang air dari ember ke luar, menuangkan air dari ember yang satu ke ember yang lain. Aturan-aturan yang dapat digambarkan sebagai berikut :

5. Representasi ruang keadaan dengan pohon pelacakan. 

Pencarian suatu solusi dapat dilukiskan dengan menggunak pohon. Tiap-tiap node menunjukkan satu keadaan. Jalur dari parent ke child, menunjukkan 1 operasi. Tiap node memiliki node child yg menunjukkan keadaan yg dapat dicapai oleh parent.

Arsitektur Dan Lingkungan Sistem Kecerdasan Buatan

Arsitektur Sistem Kecerdasan Buatan

• Dalam desain arsitektur sistem pengetahuan harus melibatkan komponen-komponen berikut: Penyederhanaan representasi, Struktur pengetahuan, Mekanisme inferensi
• Perangkat keras atau arsitektur komputer yang diminta oleh sistem Kecerdasan Buatan adalah sebuah komputer yang dapat melaksanakan pemrosesan paralel. 
• Sedangkan perangkat lunaknya harus dikembangkan dengan bahasa yang mempunyai kemampuan paralel dan logika yang handal, seperti Lisp dan Prolog 
• Untuk meningkatkan kecepatan pemrosesan dan ukuran memori, dimungkinkan untuk tidak melakukan peningkatan kecepatan perangkat keras, tetapi melalui pembuatan arsitektur perangkat lunak dan perangkat keras yang berbeda secara radikal. Solusi yang ditawarkan dalam hal ini adalah:

Desain pemrograman dengan kemampuan paralel.
Keefisienan programer dalam menggunakan bahasa tersebut.
Implementasi bahasa tersebut pada arsitektur/perangkat keras yang tepat.

Sistem dan Lingkungan Pengembangan Kecerdasan Buatan

• Komputasi Kecerdasan Buatan adalah komputasi simbolik, di mana dia sangat berbeda dari komputasi konvensional (numerik). 
• Karena perbedaan komputasi tersebut, maka sistem pengembangan perangkat lunak Kecerdasan Buatan dan lingkungannya berbeda dengan sistem komputer konvensional 

Fitur-fitur yang dibutuhkan sistem pengembangan perangkat lunak Kecerdasan Buatan

• Kemungkinan untuk mengembangkan model-model dan mekanisme penyimpulan secara incremental, dengan dekomposisi penyelesaian problem ke ukuran yang lebih kecil, unit-unit penyelesaian interelated. Incremental adalah program dapat dikembangkan pada compiler / interpreter (sistem) yang berbeda tapi harus dapat dipadukan hasil akhirnya menjadi satu kesatuan.
• Struktur kendali yang fleksibel untuk: Memudahkan pengarahan pemrograman kepada tujuan akhir. Memfasilitasi pengarahan program data. Memfasilitasi rekursi. Memfasilitasi pemrograman paralel.
• Kemampuan komunikasi sistem yang interaktif.

Debugger untuk mencek program, khususnya untuk unifikasi, rekursi, dan lain-lain.

• Fasilitas representasi data simbolik yang built-in, dan cara untuk memperluas representasi tersebut menuju struktur pengetahuan yang kompleks.
• Fasilitas pattern-matching.
• Fasilitas strategi-strategi pengikatan variabel sebagaimana pendekatan penyelesaian trial and error.

Fitur-fitur lingkungan perangkat lunak Kecerdasan Buatan yang diharapkan adalah:

• Pengembangan program bersifat incremental.
• Editor yang terpadu (cerdas) sebagai bagian sistem.
• Compiler/interpreter  yang bersifat incremental.
• Debugger yang user friendly dan cerdas.
• Kemampuan layar berkecepatan dan beresolusi yang tinggi.
• Antarmuka yang khusus untuk instrumentasinya.
• Kapasitas memori yang besar.

Daftar Pustaka

Louis E. Frenzel, Jr., Crash Course in Artificial Intelligence and Expert System, Howard W. Sams & Co., Indianapolis, USA.

Rich, Elaine and Knight, Kevin. 1991.  Artificial Intelligence. Mc-Graw Hill Book Co. New York.

Michalewicz, Zbigniew. 1996. Genetic Algorithms + Data Structures = Evolution Programs. Springler Verlag.

Suparman, Mengenal Artificial Intelligence, Penerbit Andi Offset Yogyakarta, Edisi pertama, 1991.

Sandi Setiawan, Artificial Intelligence, Penerbit Andi Offset Yogyakarta, Edisi pertama, 1993.

Kusumadewi, Sri. 2003. Artificial Intelligence, Teknik dan Aplikasinya. Yogyakarta: Graha Ilmu.

Uung Ungkawa, Bahasa Pemrograman Logika Turbo Prolog, Penerbit Andi Offset Yogyakarta, Edisi pertama 1992.

Tjendry Harianto, Bahasa Turbo Prolog, Penerbit Andi Offset Yogyakarta, Edisi pertama 1992.

Tavri Deviyan, Pemrograman Deklaratif dengan Turbo Prolog 2.0, Elex-Media Komputindo, Jakarta.

Prolog Tutorial by A. Aaby, http://cs.wwc.edu/KU/PR/Prolog.html