tugas kuliah: September 2016

Pada kesempatan kali ini saya akan membahas tentang problem 8-puzzlemenggunakan metode BFS (Breadth First Search). Sebelum ke topik utama, saya ingin membahas secara singkat apa itu BFS. Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara pre-order yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pada aras d+1.

Bagaimana? setelah kalian mengenal apa itu BFS, sekarang kita akan ke topik utama. Cekidottt….

Pertama-tama saya akan membahas 4 problem pada 8-puzzle :

1. Initial State (status awal masalah)

1	0	3
4	2	6
7	5	8

2. Operator Succesor

Ruang kosong yang bergerak ke arah kiri, atas, kanan, bawah.

3. Path Cost

Ruang kosong yang bergerak ke arah kiri, atas, kanan, bawah.

Kemungkinan yang terjadi :
1. Langkah 0 (situasi awal) 103426758

2. Langkah 1 013426758 (0 ke kiri)

3. Langkah 2 123406758 (0 ke bawah) dipilih ke-1

4. Langkah 3 130426758 (0 ke kanan)

5. Langkah 1.1 413026758 (0 ke bawah)

6. Langkah 2.1 123046758 (0 ke kiri)

7. Langkah 2.2 123456708 (0 ke bawah) dipilih ke-2

8. Langkah 2.3 123460758 (0 ke kanan)
9. Langkah 3.1 136420758 (0 ke bawah)

10. Langkah 1.1.1 413206758 (0 ke kanan)

11. Langkah 1.1.2 413726058 (0 ke bawah)

12. Langkah 2.1.1 023146758 (0 ke atas)

13. Langkah 2.1.2 123746058 (0 ke bawah)

14. Langkah 2.2.1 123456078 (0 ke kiri)

15. Langkah 2.2.2 123456780 (0 ke kanan) dipilih ke-3

16. Langkah 2.3.1 120463758 (0 ke atas)

17. Langkah 2.3.2 123468750 (0 ke bawah)

18. Langkah 3.1.1 136402758 (0 ke kiri)

19. Langkah 3.1.2 136428750 (0 ke bawah)

4. Goal Test

1. 103426758

2. 123406758 (0 ke bawah)

3. 123456708 (0 ke bawah)

4. 123456780 (0 ke kanan)

1	2	3
4	5	6
7	8	0

Selanjutnya kita akan menelusuri pohon pencarian dengan BFS

Selanjutnya kita masuk ke tahap sekuen aksi BFS dari pohon diatas

Untuk lebih jelasnya kalian bisa menyimak video berikut :

Sumber referensi :

http://andiktaufiq.wordpress.com/2010/04/16/8-puzzle-problem-bagian-1/
http://artificialintelligence-notes.blogspot.co.id/2010/07/8-puzzle-problem.html
http://onbuble.wordpress.com/2011/05/26/6/
http://mypuzzle.org/sliding

ARTIFICIAL INTELLIGENCE (AI)

Artificial Intelligence atau AI adalah kemampuan dari sebuah komputer untuk berfikir seperti manusia bahkan lebih baik dibandingkan manusia . Dalam bahasa Indonesia Artificial Inteligence atau AI artinya Kecerdasan Buatan , biasanya sebuah sistem AI memiliki kemampuan untuk memperoleh informasi baru yang akan dikumpulkan agar sistem AI menjadi lebih cerdas lagi .

Artificial Intelligence biasanya berbentuk mesin atau software , tujuan dari AI ini adalah untuk menggantikan peran manusia agar sebuah pekerjaan atau pemecahan suatu masalah dapat lebih mudah dan efisien .

Kecerdasan Buatan dipastikan akan merubah masa depan kehidupan manusia dimuka bumi , oleh karena itu kalian wajib tahu “Apa itu Artificial Intelligence atau AI ?”

Sejarah Artificial Intelligence Dunia

Sebelum memulai pembahasan mendalam tentang Kecerdasan Buatan ini , mari kita kenali dulu sejarahnya . AI sebenarnya muncul dan mulai diyakini keberadaannya pertama kali pada kisah mitologi Yunani dan peradaban Mesir Kuno .

Namun sistem kecerdasan buatan ini mulai efektif di era 1950 an , dengan dimulainya pengembangan komputer elektronik pada tahun 1941 dan pengembangan stored program pada tahun 1949 maka muncul dorongan untuk mempelajari AI lebih jauh .

Pada tahun 1951 , untuk pertama kalinya terciptalah sebuah sistem kecerdasan buatan yang benar-benar bekerja , dengan menggunakan komputer Ferranti Mark 1 , Christopher Strachey dan Dietrich Prinz berhasil membuat sebuah permainan catur melawan komputer .

Jika kalian bertanya , siapakah pencetus Artificial Intelligence , maka jawabannya adalah John McCarthy yang disebut sebagai bapak artificial intelligence dunia karena pada tahun 1956 untuk pertama kalinya kata ” artificial intelligence ” dikenalkan pada Dartmouth Conference .

P.E.A.S

PEAS: Performance measure, Environment, Actuators, Sensors.
Pertama-tama harus menentukan pengaturan untuk desain agen cerdas.
Pertimbangkan, misalkan tugas merancang supir taksi otomatis:

-          Performance measure: aman, cepat, legal, perjalanan menyenangkan, maksimumkan keuntungan.

-          Environment: jalan, trafik lain, perjalanan kaki, pelanggan.

-          Actuators: kemudi, gas, rem, lampu sign, horn.

-          Sensors: kamera, sonar, speedometer, GPS, odometer, engine sensors, keyboard.

Agen: Sistem pendiagnosa medis
Performance measure: pasien sehat, biaya minimal, sesuai aturan/hukum (lawusuits)
Environment: patient, hospital, staff
Actuators: screen display (quenstions, tests, diagnoses, treatments, referals)
Sensors: keyboard (entry of symptoms, findings, patient’s answers)
Agent: robot pengutip-sukucadang
Performance measure: persentase sukucadang dalam kotak yang benar
Environment: ban berjalan dengan sukucadang, kotak.
Actuators: pergelangan dan tangan tersambung
Sensors: kamera, joint angel sensors.
Agen: tutor Bahasa Inggris interaktif
Performance measure: memaksimalkan nilai mahasiswa pada waktu ujian
Environment: sekumpulan mahasiswa
Actuators: layar display (exercises, suggestions, corrections)
Sensors: keyboard

AGENT

Agent adalah sesuatu yang dapat mengesan (perceiving) lingkungan (environment) nya melalui sensors dan bertindak (acting) terhadap lingkungan tersebut melalui actuators.

Agent manusia:

Sensor: mata, telinga, dan organ tubuh lainnya.
Actuator: tangan, kaki, mulut, dan bagian tubuh lainnya.

Agen robotik:

Sensor: kamera dan infraref range finders.
Actuator: berbagai macam motor.

AGENT DAN LINGKUNGAN

Fungsi agen memetakan dari sejarah persepsi ke dalam tindakan (actions):

Program agen berjalan pada arsitektur fisik untuk menghasilkan f
agen = arsitektur + program

VACUUM-CLEANER WORLD

Percepts: location and contents, e. [A,Dirty]
Actions: Left, Right, Suck, NoOp

A VACUUM-CLEANER AGENT

AGEN RASIONAL

Sebuah agen haruslah mengarah kepada “lakukan hal yang benar”. Berdasarkan kepada apa yang dapat dipahaminya dan tindakan yang dapat dilakukannya. Tindakan yang benar adalah tindakan yang akan menyebabkan agen tersebut paling berhasil.
Pengukuran performance: sebuah kriteria objektif untuk keberhasilan sebuah perilaku agen.
Misalnya, ukuran performance dari sebuah agen vacuum-cleaner dapat berupa besarnya jumlah debu yang dibersihkan, jumlah waktu yang dihabiskan, jumlah listrik yang dikonsumsi, jumlah kebisingan yang dihasilkan, dan lain-lain.
Agen rasional: untuk setiap deretan persepsi yang mungkin, sebuah agen rasional hendaklah memilih satu tindakan ang diharapkan memaksimalkan ukuran performance-nya, dengan adanya bukti yang diberikan oleh deretan persepsi dan apapunpengetahuan terpasang yang dimiliki agen itu.
Rasionalitas berbeda dari omniscience (tahu segala/all-knowing dengan pengetahuan tak berhingga).
Agen dapat melakukan tindakan untuk memodifikasi persepsi masa depan sedemikianhingga dapat memeroleh infoemasi yang berguna (pengumpulan infoemasi, eksplorasi)
Sebuah agen adalah otonom (autonomous) apabila perilakunya ditentukan oleh pengalamannya sendiri (dengan kemampuan belajar dan beradaptasi)
SIMPLE REFLEX AGENTS
contoh
MODEL-BASED REFLEX AGENTS

GOAL-BASED AGENTS

UTILITY-BASED AGENTS

LEARNING AGENTS