TUGAS 2 (PROBLEM SOLVING, SEARCH)

 Missionaries and Cannibals Problem

  

  Sekarang ini, sudah banyak game / permainanpermainan

menarik yang beredar di masyarakat. Ada

yang dalam bentuk console seperti PlayStation

maupun permainan pada komputer. Permainan ini

awalnya adalah suatu hiburan untuk menyegarkan

pikiran. Namun banyak juga orang yang sampai

kecanduan terhadap suatu permainan karena

permainan itu sangat menarik dan terus berlanjut.

Hal seperti ini kurang bagus. Permainan yang baik

adalah permainan yang bukan hanya menghibur,

tetapi juga mengasah otak ibarat sambil menyelam

minum air. Namun biasanya permainan seperti itu

kurang populer sehingga banyak yang tidak

mengetahuinya.

    Oleh karena itu, pada makalah ini, akan dibahas suatu

permainan logika yaitu 3 missionaries and 3

cannibals dimana tujuan akhir dari permainan ini

adalah menyebrangkan tiga missionaries dan tiga

cannibals ke sisi lainnya dengan perahu yang hanya

mampu mengangkut dua orang dan dikendalikan oleh

salah satu orang pada perahu tersebut. Pada

permainan ini, ada banyak kemungkinan yang dapat

dilakukan dan juga terdapat beberapa kemungkinan

yang menuju ke penyelesaian. Salah satu algoritma

yang cukup mangkus untuk menyelesaikan

permasalahan ini adalah dengan menggunakan

algoritma runut-balik (backtracking). Algoritma ini

mampu memangkas kemungkinan-kemungkinan yang

tidak menuju solusi sehingga waktu yang diperlukan

untuk mencari penyelesaian dari permainan ini

menjadi lebih singkat.

Problem didefinisikan dalam 4 item:

1.   Initial State, yaitu memutuskan apa yang harus dilakukan dengan mencari urutan tindakan yang mengarah pada keadaan (state) yang diinginkan

2.    Successor function / Action, yaitu kombinasi dari berbagai "tindakan nyata"

3.    Goal test, yaitu merumuskan tujuan yang ingin dicapai

4.    Path cost, yaitu menetapkan besarnya biaya untuk setiap jalur yang ada.

Penjelasan Game

Game “Missionaries and Cannibals” merupakan salah satu game bergenre puzzle yang terkenal di dunia. Game ini bercerita tentang tiga orang misionaris dan tiga kanibal yang ingin menyebarang sungai. Untuk menyebrangi sungai tersebut disediakan perahu yang dapat digunakan oleh kanibal maupun misionaris. Pemain dikatakan berhasil memainkan permainan ini jika sampai akhir permainan jumlah misionaris dan kanibal masing masing tiga. Dan aturan pokok yang menjadi ciri dari permainan ini, yaitu jumlah kanibal tidak boleh lebih dari jumlah misionari di berbagai sisi. Jika jumlah kanibal lebih banyak dari misionari, maka kanibal akan memakan misionari dan permainan berakhir.

Game ini terasa lebih sulit dimainkan oleh pemain jika diberi aturan-aturan yang harus dipatuhi. ini dia aturan-aturan tersebut:

• Ada tiga misionaris dan tiga kanibal yang harus menyebrang sungai.

• Hanya disediakan satu perahu.

• Perahu bisa berjalan jika ada minimal satu orang atau satu kanibal (satu penumpang).

• Perahu maksimaum berisi dua (1 kanibal/1 misionaris /2 kanibal /2 misionaris) 

• Jumlah kanibal tidak boleh lebih banyak dari jumlah misionaris di salah satu sisi daratan.

• Jika jumlah kanibal lebih banyak dari jumlah misionaris pada suatu sisi daratan maka kanibal akan memakan misionaris. 

• Pemain berhasil menyelesaikan permainan jika semua misionaris dan semua kanibal ada di sisi seberang yang menjadi tujuan. 

Salah satu metode yang dipakai dalam pemecahan masalah pada game missionaries and cannibals ini adalah dengan Breadth First Search (BFS). Secara umum, prinsip pencarian solusi dengan algoritma Breadth First Search (BFS) dimulai dengan simpul akar (simpul akar terlebih dahulu dimasukkan dalam antrian, lalu di pop()), lalu mengekspansi simpul-simpul anak dari dari simpul akar, dan memasukkan simpul anak dalam sebuah antrian. Antrian tadi digunakan untuk memberikan tanda pada simpul – simpul tetangga yang nantinya akan dikunjungi berdasarkan urutan yang ada pada antrian. 

Penjabaran langkah-langkahnya sebagai berikut:

1.    Akar dimasukkan dalam antrian (Simpul paling awal yang akan dikunjungi). 

2.    Simpul yang ada pada awal antrian diambil dan dilakukan pengecekan untuk mengetahui status simpul tersebut sebagai solusi permasalahan atau tidak, dan mengekspansi anak-anaknya jika ada. 

3.    Jika simpul yang sudah dicek tadi merupakan solusi permasalahan, pencarian selesai dan hasil dikembalikan. 

4.    Jika simpul yang sudah dicek sebelumnya bukan merupakan solusi permasalahan, semua simpul yang bertetanggan dengan simpul tadi (simpul anak) dimasukkan kedalam antrian.

5.    Jika antrian ternyata telah kosong dan semua simpul sudah dicek maka status pencarian selesai dan berarti solusi tidak ditemukan. 

6.    Hal ini dilakukan secara berulang (simpul berisi solusi ditemukan/sampai antrian kosong).

Agar mempermudah penggambaran, maka dibuat notasi untuk tiap-tiap simpul/state. Untuk state awal, notasinya adalah `(0,0)|(3,3)K` yang artinya, di sisi kiri ada 0 Misionaris 0 Kanibal, dan disisi kana nada 3 Misionaris, 3 Kanibal dan perahu. State akhir notasinya adalah `K(3,3)|(0,0)`.

Gambar Puzzle:

Runtutan langkah-langkah dari state awal hingga solusi dapat diperolah dengan melakukan backtrack tiap parent dari simpul solusi ke simpul state awal.

Berikut pohon state yang dibuat, dari simpul state awal hingga simpul solusi: 

Kesimpulan

Algoritma Breadth-First Search (BFS) dapat diterapkan dalam berbagai macam masalah untuk melakukan pencarian solusi, salah satunya pada puzzle Missionaries and Cannibals. Algoritma BFS melakukan pencarian pada graf atau pohon dengan cara melebar, yang tentu memerlukan memori dan langkah pencarian yang lebih banyak dibandingkan dengan Depth-First Search (DFS). Keuntungan menggunakan BFS adalah langkah dari state awal ke state akhir optimal (terpendek). 

Tulisan ini dibuat untuk memenuhi tugas  mata kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT . Prodi Teknik Informatika Fakultas Teknik UHAMKA.


Refrensi

https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

https://id.wikipedia.org/wiki/Masalah*http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-007.pdf

TUGAS I

 Pengertian Agent Pada AI (Artificial Intelligent)

Setelah sebelumnya saya membuat postingan artikel mengenai Aplikasi Artifical Intelligent Pada Lingkungan Ilmu Kesehatan dan Kedokteran, kali ini saya akan memberi sedikit pengertian mengenai Agent. Apa itu agent?

Pengertian sebuah AGENT adalah segala sesuatu yang dapat dipandang sebagaimana mengamati lingkungannya melalui sensor dan bertindak atas lingkungan yang melalui efektor. Agen manusia memiliki mata, telinga, dan organ lain untuk sensor, dan tangan, kaki, mulut, dan bagian tubuh lainnya untuk efektor. Sebuah pengganti agen robot kamera dan berbagai pencari inframerah untuk sensor dan berbagai motor untuk efektor. Dapat digambarkan secara sederhana sebagai berikut:

Dalam kecerdasan buatan, intelligent agent (IA) adalah sebuah entitas otonom yang mengamati dan bertindak atas lingkungan (yaitu membutuhkan agen) dan mengarahkan aktivitasnya untuk mencapai tujuan  yaitu rasional. Intelligent agen juga dapat belajar atau menggunakan pengetahuan untuk mencapai tujuan mereka. Russell & Norvig (2003) mengartikan Rational Agent  yang mengerjakan segala sesuatu hal dengan benar. Agen Intelligent menurut Nikola Kasabov adalah bahwa Agent harus menunjukkan karakteristik berikut.:

·         mengakomodasi pemecahan masalah baru aturan bertahap

·         beradaptasi online dan real time

·         mampu menganalisis sendiri dalam hal perilaku, kesalahan dan kesuksesan.

·         belajar dan meningkatkan melalui interaksi dengan lingkungan (perwujudan)

·         belajar dengan cepat dari sejumlah besar data

·         memiliki penyimpanan memori berbasis contoh dan kapasitas pengambilan

·         memiliki parameter untuk mewakili umur pendek dan jangka panjang memori,,

How Agents Should Act: Right things

Pengukuran Kinerja: mengukur seberapa kesuksesan sebuah agent. Tidak ada satu ukuran yang tetap dan sama untuk semua agen. Kita dapat menanyakan kepada agen secara subyektif tentang kenyamanan dengan kinerja agen itu sendiri. Sehingga harus ada pengukuran kinerja obyektif yang diberlakukan dengan standart otoritas tentang apa artinya sukses dalam lingkungan dan menggunakannya untuk mengukur kinerja sebuah agen.

How to evaluate agent’s success?

Mengevaluasi kinerja sangat penting. Kita harus berhati-hati untuk membedakan antara rasionalitas dan omniscience (kemahatahuan). Rasionalitas bahwa agen tahu  hasil dari sebuah tindakan yang dilakukan secara rasional. Sedangkan omniscience adalah sebuah kemustahilan dari kenyataan yang sebenarnya telah terjadi. Faktor yang mempengaruhi rasionalitas  :

·                     Pengukuran kinarja (Performance Measure)

·                     Percept Sequence (persepsi urutan)

·                     Knowledge from Environment

·                     Possible Actions

When to evaluate agent’s success?

Ini mengarah ke definisi agen rasional yang ideal: Untuk setiap urutan persepsi yang memungkinkan, agen rasional yang ideal harus melakukan tindakan apapun yang diharapkan dapat memaksimalkan pengukuran kinerjanya, berdasarkan bukti yang diberikan oleh urutan persepsi dan apa pun yang yang merupakan pengetahuan built-in yang dimiliki agen.

STRUKTUR AGENT INTELLIGENCE

Tugas AI adalah untuk merancang sebuah agent yaitu sebuah fungsi yang mengimplementasikan pemetaan agen dari persepsi terhadap tindakan. Program ini akan berjalan pada beberapa jenis perangkat komputasi, yang disebut arsitektur. Secara umum, arsitektur membuat persepsi dari sensor yang tersedia untuk program, menjalankan program, dan umpan pilihan program aksi terhadap efektor seperti yang dihasilkan.

Hubungan antara agen, arsitektur, dan program dapat disimpulkan :

-      Mapping : Hubungan antara Percepts and Action.

- Tugas dari AI adalah men-design Agent Program : merupakan sebuah function yang mengimplementasikan agent mapping dari percepts to action.

-       Architecture menerima percepts dari sensor, menjalankan program, melakukan aksi yang dipilih action ke effectors.

-       Agent = Architecture + Program

-       PAGE = Percepts, Actions, Goal(s) and Environment.

Tipe Agent

Simple Reflex Agents

Gambar diatas menunjukkan struktur Simple reflex agent, struktur yang paling sederhana dalam bentuk skema, menunjukkan bagaimana aturan condition action memungkinkan agen untuk membuat sambungan dari persepsi untuk bertindak. Persegi panjang untuk menunjukkan keadaan internal saat proses keputusan agen, dan oval untuk mewakili latar belakang informasi yang digunakan dalam proses. Secara ringkat dapat disampaikan sebagai berikut:

·         Memiliki rule base dalam bentuk "aksi-kondisi"

·         Memiliki komponen untuk mengekstrak Fitur

·         Tidak ada akses untuk menyelesaikan keadaan dunia

·         Pekerjaan hanya jika keputusan yang tepat dapat dilakukan atas dasar persepsi saat ini

Model Based Reflex Agent

Pengetahuan tentang "bagaimana dunia bekerja" disebut model dari dunia, maka bentuk ini dinamakan "model based reflex agent". Sebuah model based reflex agent harus menjaga semacam internal model yang tergantung pada sejarah persepsi dan dengan demikian mencerminkan setidaknya beberapa aspek yang tidak teramati negara saat ini. Kemudian memilih tindakan dengan cara yang sama sebagai agen refleks. Model ini lebih kuat daripada simple reflex agent

Goal-Based Agents

Goal based agents memperluas pada kemampuan model-based agents, dengan menggunakan "goal" informasi. Tujuan informasi menggambarkan kondisi yang diinginkan. Hal ini memungkinkan agen cara untuk memilih di antara beberapa kemungkinan, memilih satu yang mencapai negara tujuan. Search dan planing adalah sub bidang kecerdasan buatan yang ditujukan untuk urutan tindakan menemukan bahwa mencapai tujuan agen. Dalam beberapa kasus goal-based agent tampaknya kurang efisien; itu lebih fleksibel karena pengetahuan yang mendukung keputusan diwakili secara eksplisit dan dapat dimodifikasi.

Utility-Based Agents

“Goal” tidak cukup untuk menghasilkan perilaku berkualitas tinggi. Ada banyak urutan tindakan  untuk mencapai tujuan, tetapi beberapa yang lebih cepat, lebih aman, lebih dapat diandalkan, atau lebih murah daripada yang lain. Tujuan hanya memberikan perbedaan antara kondisi "bahagia" dan "tidak bahagia", sedangkan ukuran kinerja yang lebih umum harus memungkinkan perbandingan beberapa urutan kondisi yang berbeda jika agen ingin mencapai tujuan. Terminologi yang dipergunakan untuk mengatakan bahwa jika satu kondisi lebih disukai daripada kondisi yang lain, itu mempunyai utilitas yang lebih tinggi untuk agent.

ENVIRONMENTS

Kita akan melihat bagaimana pasangan agen untuk lingkungan. Dalam semua kasus, sifat hubungan antara mereka adalah sama: tindakan yang dilakukan oleh agen pada lingkungan, yang pada gilirannya memberikan persepsi kepada agen. Pertama, kita akan menjelaskan berbagai jenis lingkungan dan bagaimana mereka mempengaruhi desain agen. Kemudian kita akan menjelaskan program-program lingkungan yang dapat digunakan sebagai testbeds untuk program agen.

REFRENSI

 http://artikel-teknologi-informasi.blogspot.co.id/2012/11/pengertian-agent-pada-ai-artificial.html