Metode Pencarian dan Pelacakan 1

• Hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian.
• Pencarian =  suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space).
• Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.
• Untuk mengukur performasi metode pencarian, terdapat 4 kriteria yang dapat digunakan :

           - Completeness: apakah metode tsb menjamin penemuan solusi jika solusinya memang ada?
           - Time complexity: berapa lama waktu yang diperlukan? (semakin cepat, semakin baik)
           - Space complexity: berapa banyak memori yang diperlukan?
           - Optimality: apakah metode tsb menjamin menemukan solusi yg terbaik jika ada beberapa             solusi berbeda?

A. Metode Pencarian Buta (Blind Search)

Pencarian Melebar Pertama (Breadth - First Seacrh)

• Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1
• Mulai dari akar lalu ke level 1 dari kiri ke kanan
• Kemudian ke level selanjutnya hingga solusi ditemukan

Keuntungan :

• Tidak akan menemui jalan buntu
• Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik
• Jika ada satu solusi maka bread-first search akan menemukannya

Kelemahan :

• Membuthkan memori yang cukup banyak
• Membutuhkan waktu yang cukup lama

Pencarian Mendalam Pertama (Depth - First Search)

Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel.
Keuntungannya :

• Memori yang relatif kecil
• Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi

B. Metode Pencarian Heuristik

Pencarian buta tidak selalu dapat diterapkan dengan baik

   - Waktu aksesnya cukup lama

   - Besarnya memoru yang diperlukan

Metode heuristik search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut fungsi heuristic. Aplikasi yang menggunakan fungsi heurustic : Google, Deep Blue Chess Machine. 

Contoh : puzzle

Keadaan awal

Tujuan

Keadaan awal tujuan pencarian heuristik :
   a. Operator
        - Ubin kosong geser ke kanan
        - Ubin kosong geser ke kiri
        - Ubin kosong geser ke atas
        - Ubin kosong geser ke bawah
  b. Langkah awal hanya ada 3 operator yang bisa digunakan
        - Ubin kosong digeser ke kiri, ke kanan, dan ke atas
   c. Jika menggunakan blind search, tidak perlu mengetahui operasi apa yg akan dikerjakan (sembarang)
   d. Pada pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut
   e. Untuk jumlah ubin yang menempati posisi yang benar, jumlah yang lebih tinggi adalah yang lebih diharapkan
   f. Untuk jumlah ubin yang menempati posisi yang salah, jumlah yang lebih kecil adalah yang lebih diharapkan
   g. Mnegitung total gerakan yang diperlukan untuk mencapai tujuan jumlah yang lebih kecil adalah yang diharapkan

Ada metode pencarian heuristik :
   - Pembangkit & Pengujian (Generate & Test)
   - Pendakian Bukit (Hill Climbing)

Pembangkt & Pengujian (Generate & Test)
Pada prinsip ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal

Algoritma :
 - Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal)
 - Uji untuk melihat apakah node tsb benar-benar merupakan solusinya dengan cara membandingkan node tsb atau node akhir dari lintasan yang dipilih dengan kumpulan tujuan yang diharapkan
 - Jika solusi ditemukan, keluar. Jika tidak, ulangi lagi langkah pertama

Contoh. Travelling Salesman Problem (TSP)
Seorang salesman ingin mengunjungi n kota. Jarak antar tiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya noleh dikunjungi 1 kali.
Generate & Test akan membangkitkan semua solusi yang mungkin :
   - A - B - C - D
   - A - B - D - C
   - A - C - B - D
   - A - C - D - B, dll
Kelemahan dari Generate & Test, yaitu :
   - Perlu membangkitkan semua kemungkina sebelum dilakukan pengujian
   - Membutuhkan wajtu yang cukup lama dalam pencariannya

Pemdakian Bukit Hill (Hill Climbing)
Metode ini hampir sama dengan Generate & Testm hanya saja proses pengujian dilakukan dengan menggunakan fungsi heurisitk. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengertasam. Tes yang berupa fungsi heuristik akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap kadaan lainnya yang mungkin

Simple Hill Climbing
Algoritma :
  - Mulai dari keaadaan awal, lakukan pengujian. Jika merupakan tujuan, maka berhenti, jika tidak maka lanjutkan dengan keadaan sekarang sebagai keadaan awal
  - Kerjakan langkat berikut sampai solusinya ditemuka, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang
  - Cari operator yang belum pernah digunakan, gunakan operator ini untuk mendapatkan keadaan baru.
  - Evaluasi keadaan baru merupakan tujuan, keluar
  - Jika keadaan baru merupakan tujuan, keluar
  - Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang
  - Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi

Contoh. TSP
  a. Operator : tukar kota ke-i dengan kota ke-j (Tk i,j)
  b. Untuk 4 kota :
        - Tk 1,2 : tukar kota ke-1 dengan kota ke-2
        - Tk 1,3 : tukar kota ke-1 dengan kota ke-3
        - Tk 1,4 : tukar kota ke-1 dengan kota ke-4
        - Tk 2,3 : tukar kota ke-2 dengan kota ke-3
        - Tk 2,3 : tukar kota ke-2 dengan kota ke-4
        - Tk 3,4 : tukar kota ke-3 dengan kota ke-4
     Untuk n kota, akan ada operator sebanyak n

Pengenalan Logical Agents

Pentingnya Pengetahuan

• Problem Solving Agent : Memilih solusi di antara kemungkinan yang ada. Apa yang ia “ketahui” tentang dunia tidak berkembang ! problem solution (initial state, successor function, goal test)
• Knowledge-based Agent : Lebih “pintar”. Ia “mengetahui” hal-hal tentang dunia dan dapat melakukan reasoning (berpikir, bernalar) mengenai : Hal-hal yang tidak diketahui sebelumnya (imperfect/partial information), dan Tindakan yang paling baik untuk diambil

Knowledge-based Agent

Knowledge Base: apa yang “diketahui” oleh si agent. Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB => (TELL). Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB => (ASK). Sebuah knowledge-based agent harus bisa :

   - Merepresentasikan world, state, action, dst.

   - Menerima informasi baru (dan meng-update representasinya)

   - Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property)

   - Menyimpulkan action apa yang perlu diambil

Knowledge Base :

   - Himpunan representasi fakta yang diketahui tentang lingkungannya

   - Tiap fakta disebut sentence.

   - Dinyatakan dalam bahasa formal ! bisa diolah

   - TELL: menambahkan sentence baru ke KB.

Inference Engine :

   - Menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB.

   - Menjawab pertanyaan (ASK) berdasarkan KB yang sudah.

Representasi

Agent dapat dipandang dari knowledge level: informasi apa yang diketahuinya? Mis: sebuah robot “mengetahui” bahwa gedung B ada di antara gedung A dan gedung C. Agent dapat dipandang dari implementation level : Bagaimana representasi informasi yang diketahuinya?

   - Logical sentence: di_antara(gdB,gdA,gdC)

   - Natural language: “Gedung B ada di antara gedung A dan gedung C”

   - Tabel posisi koordinat gedung-gedung

   - Gambar diagram peta Fasilkom (bitmap? vector?)

Pilihan representasi berpengaruh thd. apa yang bisa dilakukan oleh inference engine.

Pendekatan Deklaratif vs Pendekatan Prosedural

Programmer memberitahu (TELL) agent informasi tentang environment. Kalau informasi kurang, agent bisa melengkapinya sendiri. Bandingkan dengan pendekatan prosedural: Programmer secara eksplisit memrogram agent untuk bertindak. Kalau program tidak benar ... ? (error?) Ini adalah masalah knowledge representation: Bagaimana representasi yang tepat?

   - Expressive: bisa menyatakan fakta tentang environment

   - Tractable: bisa diolah/diproses inference engine (dg. cepat?)

Wumpus World

- Performance measure: emas +1000, mati -1000, gerak -1, panah -10

- Environment: Matriks 4x4 kamar. Initial state [1,1]. Ada gold, wumpus dan pit yang lokasinya dipilih secara acak.

- Percept

     * Breeze: kamar di samping lubang jebakan ada hembusan angin

     * Glitter: kamar di mana ada emas ada kilauan/sinar

     * Smell: kamar di samping Wumpus berbau busuk

- Action: maju, belok kiri 90
, kanan 90
, tembak panah (hanya 1!), ambil benda

Sifat Wumpus World :

   - (Fully) observable? Tidak, hanya bisa persepsi lokal

   - Deterministic? Ya, hasil tindakan jelas & pasti

   - Episodic? Tidak, tergantung action sequence

   - Static? Ya, gold, wumpus, pit tidak bergerak

   - Discrete? Ya

   - Single agent? Tidak

Menjelajahi Wumpus World

Logic in General

Knowledge representation language (KRL): bahasa yang digunakan untuk menyatakan fakta tentang

“dunia”.

Syntax: aturan yang mendefinisikan sentence yang sah dalam bahasa.

Semantics: aturan yang mendefinisikan “arti” sebuah sentence, mis: kebenaran sentence di dalam dunia

Contoh KRL bahasa aritmatika :
Syntax:
   x + 2 > y adalah kalimat sah.
   x2 + y bukan kalimat sah.

Semantics: x + 2 > y benar jika bilangan x + 2 tidak lebih kecil dari bilangan y:
   x + 2 > y benar dalam “dunia” di mana x = 7, y = 1
   x + 2 > y salah dalam “dunia” di mana x = 0, y = 6

Contoh KRL bahasa Indonesia :
Syntax:
   “Jakarta adalah ibukota Indonesia” adalah kalimat sah.
   “Ibu Indonesia kota Jakarta adalah” bukan kalimat sah.

Semantics: “X adalah ibukota Y” benar jika X adalah pusat pemerintahan negara Y.
   “Jakarta adalah ibukota Indonesia” benar dalam “dunia” kita sekarang.
   “Jakarta adalah ibukota Indonesia” salah dalam “dunia” th. 1948 (Yogya? Bukittinggi?).

Logic sebagai KRL
Logics: bahasa formal untuk merepresentasikan fakta sedemikian shg. kesimpulan (fakta baru, jawaban) dapat ditarik. Ada banyak metode inference yang diketahui. Kita bisa membangun agent Wumpus World dengan logika: memanfaatkan perkembangan logika oleh ahli matematika, filsafat selama ratusan tahun!

Entailment
Entailment berarti sesuatu fakta bisa disimpulkan dari (kumpulan) fakta lain.
KB |= : KB entails sentence jhj true dalam semua “dunia” di mana KB true.
Contoh:
   - KB mengandung sentence “Anto ganteng” dan “Ani cantik”.
   - KB |= 1: “Anto ganteng dan Ani cantik”
   - KB 2 2: “Anto pintar”
   - x + y = 4 |= 4 = x + y

Inference/Reasoning

• Inference, atau reasoning: pembentukan fakta (sentence) baru yang meng-entail fakta-fakta lama.
• Reasoning bukan dilakukan pada fakta di dunia (semantics), melainkan representasi fakta dalam KRL si agent (syntax).
• Otak manusia melakukan proses reasoning dalam suatu bentuk syntax!

Pengenalan Intelligent Agent

Agent dan Lingkungannya

Agent adalah segala sesuatu yang dapat melihat/mengartikan/mengetahui lingkungannya melalui alat sensor dan bertindak melalui alat aktuator. Manusia sebagai agent : mata, telinga, dan organ lainnya sebagai sensors; tangan, kaki, mulut dan bagian tubuh lainnya sebagai actuators. Robot sebagai agent : kamera dan pejejak inframerah sebagai sensors; berbagai motor penggerak sebagai actuators. Software sebagai agent : tekanan pada keyboard, isi file dan paket-paket pada jaringan sebagai masukan sensors; tampilan pada layar, penulisan file dan pengiriman paket jaringan sebagai keluaran actuators. Fungsi agent(f) adalah pemetaan dari urutan persepsi menjadi tindakan.

Konsep Rasionalitas

Rational agent adalah agent yang melakukan sesuatu yang benar. Setiap kolom pada tabel (Vacuum-cleaner world) diselesaikan/dikerjakan dengan benar.

Rasional tergantung pada 4 hal :

• Kemampuan yang terukur
• Pengetahuan lingkungan sebelumnya/terdahulu
• Tindakan
• Urutan persepsi

DEF : untuk setiap urutan persepsi yang mungkin, rational agent harus memilih tindakan yang diharapkan dapat memaksimalkan kemampuan dengan memberikan bukti yang dihasilkan dari urutan persepsi dan pengetahuan yang dimiliki oleh agent.

Agent dapat bertindak sesuai dengan yang diharapkan untuk memodifikasi persepsi akan datang dengan mendapatkan informasi yang berguna (pengumpulan informasi dan eksplorasi). Agent dikatakan autonomous, jika perilakunya ditentukan oleh pengalamannya sendiri (dengan kemampuan untuk belajar dan beradaptasi)

Task Environtment (PEAS)

To design a rational agent we must specify its task environment. PEAS description of the environtment :

• Performance
• Environment
• Actuators
• Sensors

Contoh-contoh.

Agent : Sistem Diagnosis Medis

   - Perfomance measure: kesembuhan pasien, biaya minim, sengketa

   - Environment: pasien, pegawai rumah sakit

   - Actuators: layar monitor (pertanyaan, test, perawatan)

   - Sensors: keyboard (gejala, temuan, pertanyaan pasien)

Agent : Part-picking robot

   - Performance measure: % komponen pada tempat penampungan yang sesuai

   - Environment: Conveyor belt with parts, bins

   - Actuators: Joined arm and hand

   - Sensors: Kamera, joint angle sensors

Agent : Interactive English tutor

   - Performance measure: Maximize student's score on test

   - Environment: Set of students

   - Actuators: Screen display (exercises, suggestions, corrections)

   - Sensors: Keyboard

Tipe-Tipe Lingkungan Agents

1. Fully vs. partially observable : Lingkungan sepenuhnya dapat diamati ketika sensor-sensor dapat mendeteksi semua aspek yang relevan dalam memilih tindakan.
2. Deterministic vs. stochastic : Ketika tahap lingkungan berikutnya sepenuhnya ditentukan oleh tindakan yang sudah dilakukan.
3. Episodic vs. sequential : Pengalaman agent dapat dibagi menjadi tahapan-tahapan yang kecil dimana agent akan menerima dan melakukan satu tindakan. Pilihan tindakan tergantung hanya pada episode itu sendiri.
4. Static vs. dynamic : Jika lingkungan dapat berubah ketika agent sedang memilih tindakan, lingkungan dikatakan dynamic. Semi-dynamic, jika perfoma agent berubah ketika lingkungan tetap sama.
5. Discrete vs. continuous : This distinction can be applied to the state of the environment, the way time is handled and to the percepts/actions of the agent.
6. Single vs. multi-agent : Does the environment contain other agents who are also maximizing some performance measure that depends on the current agent’s actions?

Agent types

1. Goal-based
2. Utility-based
3. Learning

1. Goal-based

Tujuan-tujuan tertentu dapat dicapai dengan cara-cara berbeda. Beberapa lebih baik, memiliki manfaat yang lebih tinggi. Fungsi utililas memetakan urutan kedudukan (a sequence of states) dengan

angka real.

Meningkatkan tujuan-tujuan :

   - Memilih tujuan dari tujuan-tujuan yang berbenturan

   - Memilih dengan tepat beberapa tujuan memiliki kemungkinan berhasil.

2. Utility-based

Agent membutuhkan tujuan untuk mengetahui situasi mana yang diharapkan. Akan menjadi sulit ketika urutan yang panjang dari tindakan-tindakan (actions) dibutuhkan untuk mencari tujuan. Typically investigated in search and planning research. Major difference: future is taken into account. Is more flexible since knowledge is represented explicitly and can be manipulated.

3. Learning

Semua program-program agent terdahulu mendeskripsikan metode untuk memilih tindakan-tindakan (actions).

   – Yet it does not explain the origin of these programs.

   – Learning mechanisms can be used to perform this task.

   – Teach them instead of instructing them.

   – Advantage is the robustness of the program toward initially unknown environments.

Pengenalan Intelegensi Buatan (KB)

Pengertian

Awalnya komputer difungsikan sebagai alat hitung. Seiring dengan perkembangan jaman, komputer diharapkan dapat diberdayakan untuk mengerjakan segala sesuatu yang dikerjakan oleh manusia. Manusia bisa pandai menyelesaikan masalah karena mempunyai pengetahuan, penalaran dan pengalaman. Agar komputer bisa bertindak seperti dan sebaik manusia, maka komputer harus diberi bekal pengetahuan dan mempunyai kemampuan menalar. AI merupakan salah satu bagian ilmu komputer yang membuat agar mesin (komputer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan manusia. 

Kecerdasan Buatan dilihat dari berbagai sudut pandang :

1. Sudut pandang kecerdasan : Mesin menjadi 'cerdas' (mampu berbuat apa yang dilakukan manusia)
2. Sudut pandang penelitian : Studi bagaimana membuat agar komputer dapat melakukan sesuatu sebaik yang dilakukan manusia
3. Sudut pandang bisnis : Kumpulan peralatan yang sangat powerfull dan metodelogis dalam menyelesaikan masalah bisnis
4. Sudut pandang pemrograman : Studi tentang pemrograman simbolik, penyelasian masalah dan percarian

Aplikasi KB memiliki 2 bagian utama, yaitu : 

• Basis pengetahuan (Knowlegde Base) : berisi fakta, teori, pemikiran, dan hubungan antara satu dengan lainnya
• Motor Inferensi (Interface Engine) : kemampuan menarik kesimpulan berdasarkan pengalaman

Komputasi KB vs Komputasi Konvensional

Sejarah KB
Tahun 1950-an, Alan Turing mengusulkan tes melihat untuk melihat bisa/tidaknya mesin memberikan respon terhadap serangkaian pertanyaan (agar mesin dapat dikatakan cerdas). Istilah "Artificial Intellegence" dimunculkan oleh John McCarthy (MIT), tahun 1956 pada Dartmouth Conference. Dalam konferensi itu juga didefinisikan tujuan AI, yaitu mengetahui dan memodelkan proses berpikir manusia dan mendesain mesin agar dapat menirukan kelakuan manusia tersebut.

Beberapa program AI peroide 1956-1966 :

• Logic Theorist, untuk membuktikan teorema matematik
• Sad San (oleh Robert K.Lindsay, 1960), program yang dapat mengetahui kalimat sederhana dalam bahasa Inggris dan memberikan jawaban dari fakta yang didengar dalam sebuah percakapan.
• ELIZA (Joseph Weizenbaum, 1967), program untuk terapi pasien dengan memberikan jawaban

Lingkup Kecerdasan Buatan

1.  Sistem Pakar  : komputer memiliki keahlian untuk menyelesaikan masalah dengan meniru keahlian yang dimiliki oleh pakar
2. Pengolahan Bahasa Alami : diharapkan user dapat berkomunikasi dengan komputer menggunakan bahasa sehari-hari
3. Pengenalan Ucapan : melalui pengenalan ucapan, diharapkan manusi dapat berkomunikasi dengan komputer menggunakan suara
4. Robotika dan Sistem Sensor 
5. Computer Vision : menginterprestasikan gambar atau obyek-obyek tampak melalui komputer
6. Intelligence Computer - Aided Instruction : komputer digunakan sebagai tutor yang dapat melatif dan mengajar
7. Game Playing

Soft Computing

Soft Computing adalah koleksi dari beberapa metodelogi yang bertujuan untuk mengeksploitasi adanya toleransi terhadap ketidaktepatan, ketidakpastian dan kebenaran parsial untuk dapat diselesaikan dengan mudah, dengam biaya penyelesaian yang murah.

Soft Computing merupakan inovasi baru dalam membangun IB yang memiliki keahlian seperti manusia pada domain tertentu, mampu beradaptasi dan belajar agar dapat bekerja lebih baik jika terjadi perubahan lingkungan,

Unsur-unsur pokok Soft Computing :

• Sistem Fuzzy Logic (mengakomodasi ketidaktepatan)
• Jaringan Syaraf (menggunakan pembelajaran)
• Probabilistic Reasoning (mengakomodasi ketidakpastian)
• Evolutionary Computing (optimasi)