PENGENALAN INTELLIGENT AGENT, LOGICAL AGENT & METODE PENCARIAN DAN PELACAKAN

PENGENALAN INTELLIGENT AGENT

AGENT dan Lingkungannya

•                Agents adalah segala sesuatu yang dapat melihat/ mengartikan/ mengetahui

             (perceiving) linkungannya melalui alat sensor (sensors) dan bertindak

             (acting) melalui alat aktuator (actuators)

•                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 infra merah sebagai sensors; berbagai motor pengerak 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 (percept)  menjadi tindakan (actions)

[f: P*ÆA]

•                Program agent berjalan pada arsitektur fisik untuk menghasilkan fungsi agent (f) agent = architecture + program

Vacuum-cleaner world

Environment: square A and B

Percepts: [location and content] e.g. [A, Dirty] Actions: left, right, suck, and no-op.

Konsep Rasionalitas

•                Rational agent adalah agent yang melakukan sesuatu yang benar

–          Setiap kolom pada tabel (Vacuum-cleaner world) diselesaikan/dikerjakan dengan benar

•                Apakah sesuatu yang benar ?

–          Agent yang paling sukses/ berhasil

 –           Mengukur kesuksesan/ keberhasilan ?

•                Pengukur kemampuan haruslah objektif (contoh : Vacuumcleaner world)

–          Jumlah debu yang dapat dibersihkan pada waktu tertentu

–          Seberapa bersih lantai

–          Besarnya konsumsi listrik

–          Besarnya noise yang dihasilkan

–          …

•                Rasional tergantung pada 4 hal :

–          Kemampuan yang terukur,

–          Pengetahuan lingkungan sebelumnya/ terdahulu,

–          Tindakan,

–          Urutan persepsi (sensors).

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

•                Rationalitas ≠ kemahatahuan (omniscience)

–          An omniscient agent adalah agent mengetahui akibat yang terjadi dari suatu tindakan.

•                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 Environment (PEAS)

To design a rational agent we must specify its task environment.

PEAS description of the environment:

–          Performance

–          Environment

–          Actuators    – Sensors

Contoh-Contoh

Agent: Sistem Diagnosis Medis

•                Performance measure: Kesembuhan pasien, biaya minim, sengketa

•                Environment: Pasien, pegawai rumah sakit

•                Actuators: Layar monitor (pertanyaan, test, perawatan, rujukan)

•                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

Environment types

•                Fully vs. partially observable: lingkungan sepenuhnya dapat diamati ketika sensor-sensor dapat mendeteksi semua aspek yang relevan dalam memilih tindakan.

•                Deterministic vs. stochastic: Ketika tahap lingkungan berikutnya sepenuhnya ditentukan oleh tindakan yang sudah dilakukan.

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

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

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

•                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?

	Solitaire	Backgammom	Intenet shopping	Taxi
Observable??	Full	Full	Partial	Partial
Deterministic? ?	Yes	No	Yes	No
Episodic??	No	No	No	No
Static??	Yes	Yes	Semi	No
Discrete??	Yes	Yes	Yes	No
Singleagent??	Yes	No	No	No

Tipe-Tipe Agen

1.   goal-based

2.   utility-based

3.   learning

Agent types; 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.

Agent types; 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.

Agent types; 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.

•                Learning element: introduce improvements in performance element.

–       Critic provides feedback on agents performance based on fixed performance standard.

•                Performance element: selecting actions based on percepts. 

–    Corresponds to the previous agent programs

•                Problem generator: suggests actions that will lead to new and informative experiences.

–    Exploration vs. exploitation

LOGICAL AGENTS

Basis Pengetahuan

•                Basis Pengetahuan (Knowledge base) = Sekumpulan kalimat dalam bahasa formal (formal language)

•                Pendekatan dengan menerangkan/ menjelaskan (Declarative) untuk membangun suatu agent (atau sistem lain) :

–  Katakan apa yang dibutuhkan untuk bisa mengerti

•                Kemudian dapat bertanya pada diri sendiri apa yang akan dikerjakan --- jawaban harus merujuk pada Basis Pengetahuan

•                Agents dapat dilihat dari sisi tingkat pengetahuan

–          Apa yang diketahui, terlepas dari bagaimana penerapannya

•                Atau dari sisi tingkat implementasi

–       Struktur data pada Basis Pengetahuan dan algoritma yang memanipulasinya

Contoh :

•                Agent harus memiliki kemampuan :

–          Mewakili suatu kondisi, tindakan dll Represent states, actions, etc.

–          Menerima masukan persepsi-persepsi baru

–          Update representasi internal dunia

–          Mengambil kesimpulan dari properti dunia yang tersembunyi

–          Mengambil kesimpulan tindakan-tindakan yang tepat

PENGENALAN LOGICAL AGENTS

•            Logic merupakan jantung dari program, para pemrogram mempunyai keyakinan bahwa sebuah komputer dapat dibuat mengerti logika, maka computer dapat dibuat untuk berfikir, karena logika kelihatannya menjadi inti dari kecerdasan.

•            1  Problem solving agent hanya bisa menyelesaikan masalah yang lingkungannya accessible.

•            2  Kita membutuhkan agen yang dapat menambah pengetahuan dan menyimpulkan keadaan.

•            3  Agent yang akan membantu seperti ini kita beri nama knowledge based agent.

•             

•            3.1 Knowledge Based Agents

•            Komponen utama dari knowledge based agent adalah knowledge basenya. Knowledge base (KB) adalah kumpulan representasi fakta tentang lingkungan atau dunia yang berhubungan atau menjadi daerah bekerjanya agen. Setiap representasi dalam KB disebut sebagai sebuah kalimat yang diekspresikan dalam sebuah bahasa yakni knowledge representation language.

•            Ø  Representasi Pengetahuan yang bersifat general.

•            Ø  Kemampuan beradaptasi sesuai temuan fakta.

•            Ø  Kemampuan menyimpulkan sesuatu dari pengetahuan yang sudah ada.

•            Syarat Representasi KB:

•            1.       Representational Adequacy
Kemampuan merepresentasikan semua pengetahuan yang dibutuhkan dalam domainnya

•            2.       Inferential Adequacy
Kemampuan memanipulasi struktur pengetahuan untuk membentuk struktur baru dalam menampung pengetahuan baru hasil inferens.

•            3.        Inferential Efficiency
Kemampuan untuk manambahkan informasi untuk mempercepat pencarian dalam inferensi.

•            4.       Acquisitional Efficiency
Kemampuan untuk menambah informasi baru secara mudah.

•            Pengetahuan yang dimiliki agent tidak berguna jika ia tidak melakukan apapun karenanya kita perlu menambahkan aturan agar dia dapat bergerak (complete the knowledge base). Beberapa tahapan yang dilakukan dalam menyusun knowledge based agent:

•            Ø  Untuk dapat menyusun sebuah knowledge based agent maka kita harus terlebih dulu bisa menyusun knowledge basenya itu sendiri.

•            Ø  Untuk menyusun knowledge base kita perlu menentukan bagaimana cara kita merepresentasikan pengetahuan kita (knowledge representation).

•            Ø  Knowledge representation kita harus merupakan bentuk yang mudah disimpan dan digunakan pada komputer. Dalam perkuliahan ini kita menggunakan beberapa macam knowledge representation language.

•             

•            3.2 Wumpus World

•            Ø  Environment sederhana, berguna untuk menguji dan menjelaskan logical agent.

•            Ø  Gua gelap dengan banyak ruangan yang dihubungkan dengan lorong-lorong.

•            Ø  Agent masuk ke gua untuk mengambil emas yang ada di salah satu ruangan.

•            Ø  Wumpus (monster) bersembunyi di salah satu ruangan. Jika agent bertemu, ia akan menjadi santapannya.

•            Ø  Terdapat ruang-ruang yang memiliki lubang jebakan yang dapat membunuh agent.

•            Ø  Agent hanya punya 1 panah yang bisa membunuh wumpus dari jarak jauh.

•            Sifat dari Wumpus World:

•            Ø  Fully observable? Tidak, hanya bisa berpresepsi lokal.

•            Ø  Deterministic? Ya, hasil tindakan jelas dan pasti.

•            Ø  Episodic? Tidak, tergantung action sequence.

•            Ø  Static? Ya, gold, wumpus, pit tidak bergerak.

•            Ø  Discrete? Ya.

•            Ø  Single agent? Ya.

•             

•            3.3 Logic in general-Models and Entailment

•            Logics adalah 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 artinya bahwa sesuatu mengikuti dari yang lain.

•            KB ╞

•            ·         Knowledge base KB entails kalimat α jika dan hanya jika α adalah true pada semua dunia dimana KB bernilai true.

•            ·         Misal, KB “the Giants won” dan “the Reds won”  entails “Either the Giants won or the Reds won”

•            ·         Misal, x+y = 4 entails 4 = x+y

•            Entailment adalah sebuah hubungan antar kalimat (syntax) yang didasarkan pada semantik.

•            Models à m adalah sebuah  model pada sebuah kalimat α jika α bernilai true pada m

•            ·         M(α) adalah kumpulan semua model pada α.

•            ·         KB ╞ α iff M(KB) Í M(α).

•            ·         Misal: KB = Giants won and Reds won , α = Giants won

METODE PENCARIAN DAN PELACAKAN

• 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 perfomansi metode pencarian, terdapat 4 kriteria yang dapat digunakan :

1.     Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

2.     Time complexity : berapa lama waktu yang diperlukan? [semakin cepat, semakin baik]

3.     Space complexity : berapa banyak memori yang diperlukan

4.     Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

• Dua teknik pencarian dan pelacakan

– Pencarian buta (blind search)

• Pencarian melebar pertama (Breadth – First Search)

• Pencarian mendalam pertama (Depth – First Search)

– Pencarian terbimbing (heuristic search)

• Pendakian Bukit (Hill Climbing)

• Pencarian Terbaik Pertama (Best First Search)

Pencarian Melebar Pertama (Breadth-First Search)

• Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1

• Mulai dari akar terus 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

·       Kelemahannya

– Membutuhkan 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

• Keuntungan

– Memori yang relatif kecil

– Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi

Pencarian Heuristik

• Pencarian buta tidak selalu dapat diterapkan dengan baik

– Waktu aksesnya yang cukup lama

– Besarnya memori yang diperlukan

• Metode heuristic 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 heuristic : Google, Deep Blue Chess Machine

• Contoh pada masalah 8 puzzle

keadaan awal                                                                             Tujuan

Keadaan Awal Tujuan Pencarian Heuristik

• Operator

– Ubin kosong geser ke kanan

– Ubin kosong geser ke kiri

– Ubin kosong geser ke atas

– Ubin kosong geser ke bawah

• Langkah Awal

Gambar

• Langkah Awal hanya 3 operator yang bisa digunakan

– Ubin kosong digeser ke kiri, ke kanan dan ke atas.

• Jika menggunakan pencarian buta, tidak perlu mengetahui operasi apa yang akan dikerjakan (sembarang)

• Pada pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut

• Untuk jumlah ubin yang menempati posisi yang benar jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik)

• Untuk jumlah ubin yang menempati posisi yang salah jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

• Menghitung total gerakan yang diperlukan untuk mencapai tujuan jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Pencarian Heuristik

• Ada 4 metode pencarian heuristik

– Pembangkit & Pengujian (Generate and Test)

– Pendakian Bukit (Hill Climbing)

– Pencarian Terbaik Pertama (Best First Search)

– Simulated Annealing

Pembangkit & Pengujian (Generate and Test)

• Pada prinsipnya metode 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 tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

– Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.

Contoh : Traveling Salesman Problem (TSP)

Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali.

Contoh : Traveling Salesman Problem (TSP)

• 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 Pembangkit & Pengujian (Generate and Test) yaitu ;

– Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian

– Membutuhkan waktu yang cukup lama dalam pencariannya

Pendakian Bukit (Hill Climbing)

• Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik.

• Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.

• Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

Simple Hill Climbing

Algoritma

– Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

– Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:

• Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

• Evaluasi keadaan baru tersebut.

• 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

• Operator : Tukar kota ke-i dengan kota ke-j (Tk i,j)

• 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,4 : 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:

Steepest Ascent Hill Climbing

• Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri.

• Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.

• Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.

• Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri.

• Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.

• Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.

Algoritma

• Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

• Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang.

• Tentukan SUCC sebagai nilai heuristic terbaik dari successorsuccessor.

• Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:

• Gunakan operator tersebut dan bentuk keadaan baru.

• Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah.

• Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang, ubah node SUCC menjadi keadaan sekarang.