The Missionaries and Cannibals Problem

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 menyebrang 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-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.

Problem Solving dari Game “Missionaries and Cannibals” dapat dideskripsikan dengan :

• ·     Initial state (status awal), 3 missionaries dan 3 Cannibals ada disisi kiri sungai.     
•       operator/fungsi successor, suatu perpindahan yang diwakili oleh jumlah missionaries dan jumlah cannibal pada satu waktu.
•       Path cost (biaya jalur), jumlah penyebrangan.
•       Goal test (uji tujuan), 3 missionaries dan 3 cannibals ada disisi kanan sungai.

Salah satu metode yang dipakai dalam pemecahan masalah pada game missionaries and cannibals ini adalah dengan Breadth First Search(BFS). Breadth First Search(BFS) adalah algoritma pencarian solusi yang melakukan pencarian pada graf atau pohon berakar secara melebar dengan cara mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Simpul yang belum dikunjungi dan bertetangga dengan simpul – simpul yang tadi dikunjungi, demikian seterusnya.

Pada puzzle ini tiap-tiap state dijadikan sebuah simpul pada pohon. Pada Missionaries and Cannibals, state awal adalah sisi daratan kiri masih kosong, dan sisi daratan kanan berisi 3 Misionaris dan 3 Kanibal. 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 kanan ada 3 Misionaris, 3 Kanibal dan perahu. State akhir notasinya adalah `K(3,3)|(0,0)`. Jika perahu ada di sisi kanan, maka yang dapat dipindahkan adalah Misionaris atau Kanibal yang berada di sisi kanan, dan sebaliknya.

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

Warna merah berarti state tersebut salah, merah + garis bawah

berarti state tersebut telah dikunjungi.

State Awal dari Missionaries and Cannibals

State Akhir dari Missionaries and Cannibals

Langkah-langkah Penyelesaian Game “Missionaries and Cannibals” : 

M1 = Misionaris 1

M2 = Misionaris 2

M3 = Misionaris 3

K1 = kanibal 1

K2 = kanibal 2

K3 = kanibal 3

1. Sebrangkan K1 dan K2 terlebih dahulu

2. Setelah sampai disebrangkan, keluarkan satu K1

3. lalu sebrangkan K2 dan masukan K3 lalu sebrangkan mereka.

4. keluarkan k2 dan sebrangkan k3

5. keluarkan k3 dan sebrangkan M1 dan M2

6. keluarkan M1 dan masukan K1, lalu sebrangkan mereka

7. keluarkan k1 dan masukan M3, lalu sebrangkan mereka

8. keluarkan M2 dan M3, lalu sebrangkan K2

9. Masukan K1, lalu sebrangkan mereka

10. Keluarkan K1 dan sebrangkan K2

11. Masukan K3 lalu sebrangkan mereka

Selesai

Analisis

Penggunaan algoritma BFS pada pencarian solusi puzzle Missionaries and Cannibals menghasilkan langkah-langkah menuju solusi yang optimal (terpendek), ini dikarenakan pencarian dilakukan secara melebar dari simpul akar hingga simpul akhir. Kekurangan penggunaan BFS disini, langkah proses pencarian lebih banyak dibandingkan dengan DFS, penggunaan ruang (memori) juga lebih banyak, karena tiap simpul anak-anak hasil ekspansi suatu simpul dimasukkan ke dalam antrian.

Referensi :

http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-007.pdf

https://komputasi.files.wordpress.com/2012/09/kecerdasan-buatan-02.pdf

Read More

Intelligent Agent

Pada kesempatan kali ini, dan untuk menuaikan tugas yang diberikan saya akan membahas sedikit mengenai Intelligent agent, topik yang dibahas kali mengenai, apasih sebenernya agent itu? Serta apa sih PEAS itu? dan ada apa aja sih  tipe-tipe agent itu. Semoga pada bahasan kali ini bisa bermanfaat bagi kita semua.........Selamat membaca......^_^

Apa itu Agent?

    Agent merupakan robot ataupun program komputer yang menerima input dari lingkungannya (persepsi) dan bertindak (aksi) sesuai dengan pengetahuan yang telah diberikan. Agent harus dijalankan pada suatu lingkungan fisik untuk memproduksi tujuan tertentu sesuai dengan yang ditugaskan padanya. Agent disini bersifat Autonomous, yaitu dapat mengembangkan dirinya sesuai dengan pengalaman yang telah diberikan penciptanya. Perlu Anda ketahui bahwa Agent yang dibuat tidak bisa lebih baik dari penciptanya, hanya bisa sama baik atau hampir sama baik.

Agent disini memiliki anatomi seperti dibawah ini :

• Sensors : merupakan panca indera untuk Agent itu sendiri layaknya manusia. Sebagai contoh untuk mendengar robot membutuhkan microphone dan speech recognition layaknya telinga pada manusia.
• Effector : merupakan anggota atau bagian dari tubuh yang bisa memberikan efek kepada lingkungan (environment). Disini digambarkan sebagai tangan atau kaki.
• Percepts : seringkali percept dikatakan sebagai sensor karena dilihat dari fungsi yang hampir sama. Percept disini memiliki fungsi yang sama, hanya untuk percept tidak harus selalu menjadi panca indera. Percept menerima tindakan dari lingkungan, sebagai contoh keyboard, keyboard menerima inputan sesuai dengan yang user ketik.
• Action : merupakan aksi atau tindakan terhadap lingkungan berdasarkan dengan kemampuan yang telah diberikan.

        Setelah mengetahui Agent itu apa, selanjutnya apa yang harus diperhatikan dalam merancang agent itu. Bagi Anda yang masih bingung mengenai hal tersebut mari kita bahas sedikit dibawah.

PEAS

         Ketika merancang sebuah agent, kita harus mendefinisikan lingkungan masalah (task environment), yakni : PEAS. PEAS adalah singkatan dari Performance Measure, Environment, Actuators, dan Sensor. Dimana harus dispesifikasikan terlebih dahulu mengenai rancangan intelligent agent.

• Performance measure: apa saja yang menjadi ukuran kinerja agent?
• Environment: di manakah agent berperan?
• Actuators: apa saja yang bisa dilakukan si agent?
• Sensors: apa saja yang menjadi perantara input untuk agent?

Misalkan untuk task yang didesain untuk agent pengemudi taksi otomatis:

Performance Measure: Aman, Cepat, Legal, Perjalanan yang nyaman, Keuntungan Maksimal

Environment : Jalan, Lalu lintas kendaraan lain, Pejalan kaki, Pelanggan

Actuators: Setir, Akselerator, Rem, Lampu Sinyal, Klakson

Sensors: Kamera, Sonar, Spedometer, GPS, odometer, sensor mesin, keyboard

Misalkan untuk task yang disusun untuk agent sistem diagnosis medis:

Performance Measure : Kesehatan Pasien, Biaya minimal, Hukum

Environment: Pasien, Rumah Sakit, Staf

Actuator : Tampilan Layar (Pertanyaan, Tes, Diagnosa, Perawatan, Rujukan)

Sensors : Keyboars(Entri gejala, pencarian penyakit, jawaban untuk pasien)

Tipe-tipe Agent

Simple Reflex Agents

       Simple reflex agent hanya beraksi pada percept yang saat ini berlangsung, fungsi agent ini  didasarkan pada aturan kondisi-aksi : jika ada kondisi maka ada tindakan. Fungsi agent ini hanya berhasil bila lingkungan (Environment) sepenuhnya diamati. Beberapa reflex agent juga dapat berisi informasi tentang keadaan saat ini berlangsung yang memungkinkan untuk mengabaikan kondisi yang actuators yang sudah dipicu. Pada agent ini juga sering terjadi loop yang tidak terbatas dikarenakan beroperasi di lingkungan (Environment) yang baru sebagian diamati.

Model Based Reflex Agent

     Model agent ini dapat menangani lingkungan (Environment) yang baru sebagian diamati dikarenakan agent ini dapat menyimpan keadaan dan beberapa jenis struktur yang menggambarkan bagian dari perubahan dunia. Agent ini menjaga semacam model internal yang tergantung pada percepts history dan dengan demikian mencerminkan setidaknya beberapa aspek yang tidak diamati dari keadaan yang saat ini berlangsung, percepts history dan dampak lingkungan (Environment) dapat ditentukan dengan menggunakan model internal. Kemudian memilih tindakan dengan cara yang sama dengan Simple reflex agent.

Goal-Based Agents

   Goal-Based Agent memperluas pada kemampuan dari model-based agent menggunakan informasi tujuan. Informasi tujuan menggambarkan situasi yang diinginkan. Agent ini menyimpan keadaan dan beberapa jenis struktur yang menggambarkan bagian dari perubahan yang terjadi pada dunia, dan melakukan beberapa tindakan dengan melihat apakah tindakan itu sesuai dan bisa mencapai “Goal” atau tidak dan memilih tidakan lain jika tindakan yang dilakukan tidak berhasil mencapai tujuan agent tersebut. Dalam beberapa kasus goal-based agent kurang efektif dalam prosesnya, dikarenakan pengetahuan yang ada harus mendukung keputusan yang tidak terbelit-belit dan bisa dimodifikasi.

Utility-Based Agents

      Utility-Based Agent hanya membedakan antara keputusan-keputusan tujuan dan keputusan-keputusan bukan tujuan. Hal ini dimungkinkan untuk menentukan seberapa diinginkannya keputusan tersebut. Penentuan ini dapat diperoleh dengan menggunakan fungsi Utility yang memetakan ukuran kinerja keputusan tersebut. Ukuran kinerja yang didapat memungkinkan perbandingan antara keputusan yg diambil dari penggambaran perubahan dunia dengan apakah keputusan ini berdampak bahagia atau tidak bahagia bagi tujuan Agent ini.

Learning Agent

        Learning memiliki keuntungan yang memungkinkan agent ini untuk memulai beroperasi di lingkungan (Environment) yang tidak di ketahui dan menjadi lebih kompeten daripada pengetahuan yang didapat pada saat awal. Perbedaan paling penting adalah antara “learning element dan “performance element”, yang keduanya bertanggung jawab memilih tindakan eksternal. Learning element menggunaka umpan balik dari “Critic” tentang bagaimana cara agrnt ini melakukan dan menentukan bagaimana unsur kinerja harus diubah kearah yang lebih baik di masa depan. Komponen terakhir dari Learning agent adalah “Problem generator” komponen ini bertanggung jawab utuk menunjukan tindakan yang akan menyebabkan pengalaman baru dan informatif dalam pembelajari tujuan yang akan dicapai.

Referensi :

Artificial Intelligence A Modern Approach (3rd Edition).pdf

http://tiindonesia.blogspot.co.id/2013/01/peas.html

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

https://en.m.wikipedia.org/wiki/intelligent_agent

Read More

Ringkasan Skripsi yang berhubungan dengan Artificial Intelligence

Judul : Rancangan Sistem Pakar pada kerusakan

HARDWARE komputer

Penulis : Siti Mutia Aulia

Fakultas Teknik Jurusan Informatika 

Universitas Muhammadiyah Prof. DR. Hamka 

Jakarta 2011

Latar Belakang

Dalam pengoprasian komputer tentu sering mengalami masalah kerusakan hardware komputer. Permasalahan kerusakan hardware komputer tersebut menjadi masalah yang cukup pelik sehingga mengakibatkan segala aktifitas yang dilakukan oleh user yang bekerja begitu intuisi, mahasiswa/i ataupun pelajar yang menggunakan teknologi komputer menjadi terhambat. Banyak sekalii para pengguna mengeluarkan biaya yang tidak sedikit hanya untuk memperbaiki kerusakan pada hardware komputer, padahal kerusakan pada hardware yang terjadi belum tentu rumit dan dapat diperbaiki sendiri. Untuk itulah perlu adanya suatu aplikasi yang dapat membantu memecahkan permasalahan kerusakan komputer.

Tentunya aplikasi yang dibuat harus dapat menyajikan solusi yang tepat dan efisien, sehingga para pengguna dapat menghemat biaya yang seharusnya dikeluarkan untuk jasa konsultasi. Aplikasi yang dimaksud ialah suatu aplikasi sistem pakar, dimana sistem pakar ini menggunakan informasi-informasi yang diberikan oleh user untuk menarik kesimpulan dari suatu permasalahan.

Tujuan  dari Penulisan

Adapun tujuan yang ingin dicapai dari perancangan aplikasi sistem pakar ini adalah untuk memberikan kemudahan informasi kepada user komputer dalam menemukan letak permasalahan yang terjadi pada hardware komputernya tanpa harus menyewa tenaga ahli, sehingga diharapkan dapat menekan biaya perbaikan jika terjadi kerusakan.

Metode yang digunakan

      Metode yang digunakan dalam perancangan sistem ini dengan menggunakan sistem orientasi objek. Perancangan sistem pakar ini terbagi menjadi perancangan fungsional dan perancangan interface.

• Perangcangan fungsional

Perancangan fungsional atau sistem terkait dengan pengaturan yang dilakukan pada tahap awal dalam menentukan kerusakan pada hardware komputer dengan menggunakan metode Forward Chaining.

• Use Case Diagram

Fungsional use care diagram ini menjelaskan apa yang dilakukan oleh sistem yang akan dibangun pada sistem pakar.

Hasil

     Sebuah aplikasi yang memberikan konsultasi tentang macam macam kerusakan pada sebuah hardware komputer. Aplikasi ini juga memiliki fitur konsultasi tentang pendeteksian kerusakan hardware komputer menggunakan metode Forward Chaining yang kemudian proses pendeteksian dilakukan oleh sistem secara otomatis setelah pengolahan gejala yang diberitahukan oleh user, pada proses ini sistem akan menjalankan sebuah algoritma dan memberikan solusi yang tepat dan mengikuti rule yang sesuai dengan database yang ada pada aplikasi tersebut. Selain fitur diatas aplikasi ini juga memiliki fitur lain, dimana user dapat menambah data kerusakan, data gejala kerusakan, data relasi kerusakan dan berbagai solusi yang belum ada pada aplikasi ini, dengan user terlebih dahulu login ke aplikasi ini menggunakan username dan password.

Kesimpulan

        Berdasarkan penelitian yang telah dilakukan oleh peneliti, diperoleh poin-poin kesimpulan yaitu:

• Dengan melakukan kuisoner yang terdiri dari beberapa responden, peneliti mendapatkan suatu nama gejala dari kerusakan hardware komputer yang selanjutnya akan diproses dengan menggunakan metode forward Chaining. Metode Forward Chaining digunakan karena sesuai dengan aplikasi yang tidak mengetahui letak kerusakan yang terjadi.
• Penggunaan sitem pakar kerusakan harware komputer dapat membantu user dalam menentukan kerusakan yang terjadi dalam komputernya.

Read More