- Kecerdasan Buatan adalah cabang ilmu komputer yang berfokus pada simulasi perilaku cerdas di dalam komputer.
- Mengacu pada kemampuan mesin untuk meniru perilaku cerdas manusia.
- Natural Language Processing (NLP): Memungkinkan AI untuk berkomunikasi dalam bahasa seperti Inggris atau bahasa lainnya.
- Knowledge Representation: Memungkinkan AI untuk menyimpan apa yang diketahui atau didengarnya.
- Automated Reasoning: Menggunakan informasi yang disimpan untuk menjawab pertanyaan dan menarik kesimpulan baru.
- Machine Learning: Beradaptasi dengan keadaan baru dan mendeteksi pola-pola untuk diekstrapolasi.
- Agen adalah entitas yang bertindak secara mandiri atau di bawah bimbingan untuk mencapai tujuan tertentu atau melakukan tugas tertentu.
- Agen mempersepsi lingkungannya dan mengambil tindakan untuk mempengaruhi lingkungan guna mencapai tujuan.
- Sprinkler A: Menyala saat dibutuhkan berdasarkan kondisi cuaca → Agen
- Sprinkler B: Selalu menyala pada jam 2 siang → Bukan Agen
- An intelligent agent is capable of:
- Perceiving its environment.
- Reasoning to make decisions.
- Taking actions autonomously to achieve goals.
- Autonomy: Bertindak tanpa campur tangan langsung.
- Perception: Mampu mengamati dan memantau lingkungan sekitarnya.
- Reasoning and Decision Making: Memilih tindakan terbaik.
- Action: Melakukan aksi untuk mencapai tujuan.
- Adaptation and Learning: Menyesuaikan perilaku berdasarkan pengalaman.
- Agen rasional adalah agen yang selalu melakukan tindakan yang benar—setiap entri dalam tabel fungsi agen diisi dengan benar.
- Saat agen ditempatkan di lingkungan, ia menghasilkan urutan tindakan berdasarkan urutan keadaan lingkungan.
- Ukuran kinerja mengevaluasi setiap urutan keadaan lingkungan.
Rasionalitas pada suatu waktu tergantung pada 4 hal:
- Ukuran kinerja yang menentukan kriteria keberhasilan.
- Pengetahuan awal agen tentang lingkungan.
- Tindakan yang dapat dilakukan oleh agen.
- Urutan persepsi agen hingga saat ini.
Agen rasional akan memilih tindakan yang memaksimalkan ukuran kinerjanya berdasarkan urutan persepsi dan pengetahuan yang dimiliki.
Untuk mendefinisikan lingkungan tugas agen, gunakan P.E.A.S. Contoh:
-
Vacuum Robot:
- Performance: Kecepatan, kebersihan, konsumsi energi.
- Environment: Lantai, tata ruang, furnitur.
- Actuators: Layar, roda, penyapu, baterai, saklar.
- Sensors: Sensor ultrasonik, kamera.
-
Amazon Alexa:
- Performance: Kecepatan, akurasi informasi.
- Environment: Pelanggan.
- Actuators: Lampu, motor, pengontrol Wi-Fi.
- Sensors: Sensor suara.
- Fully Observable: Agen memiliki akses penuh ke keadaan lingkungan di setiap saat. Contoh: Game tic tac toe.
- Partially Observable: Agen hanya memiliki informasi parsial tentang lingkungan. Contoh: Robot vacuum hanya bisa mendeteksi kotoran di satu area, tetapi tidak tahu kondisi di area lain.
- Single Agent: Hanya ada satu agen, contohnya agen yang menyelesaikan teka-teki silang.
- Multi Agent: Lebih dari satu agen, bisa kompetitif (seperti catur) atau kooperatif.
- Deterministic: Setiap tindakan agen menghasilkan hasil yang spesifik dan dapat diprediksi.
- Stochastic: Tindakan agen dapat menghasilkan hasil yang berbeda setiap kali.
- Nondeterministic: Tidak ada probabilitas yang terkait dengan hasil dari suatu tindakan.
- Episodic: Pengalaman agen terbagi dalam episode-episode terpisah, dan tindakan sebelumnya tidak mempengaruhi episode berikutnya.
- Sequential: Keputusan saat ini bisa mempengaruhi keputusan di masa depan.
- Static: Lingkungan tidak berubah saat agen mempertimbangkan tindakan.
- Dynamic: Lingkungan bisa berubah saat agen berpikir, sehingga agen harus terus memantau.
- Continuous: Keadaan agen berubah secara bertahap dan berkelanjutan, contohnya mengemudi taksi.
- Discrete: Keadaan agen berubah dalam langkah-langkah diskrit, seperti permainan catur.
- Tugas AI adalah mendesain program agen yang mengimplementasikan fungsi agen—memetakan dari persepsi ke tindakan.
Urutan Persepsi | Tindakan |
---|---|
[A, Bersih] | Pindah ke kanan |
[A, Kotor] | Sapu debu |
[B, Bersih] | Pindah ke kiri |
[B, Kotor] | Sapu debu |
- Agen yang memilih tindakan hanya berdasarkan persepsi saat ini, tanpa memperhatikan sejarah persepsi.
- Tujuan dari agen ini adalah untuk belajar dari lingkungan yang belum diketahui sebelumnya dan menjadi lebih kompeten seiring waktu.
- Goal Formulation adalah langkah pertama dalam pemecahan masalah. Tujuan membantu mengorganisir perilaku agen dengan membatasi objektif yang ingin dicapai, sehingga agen hanya mempertimbangkan tindakan yang relevan.
- Contoh:
-
Goal: Menikmati liburan di Denpasar
-
Performance Measure:
- Menikmati pemandangan
- Menikmati kuliner
- Menghindari mabuk
-
Goal: Pergi ke Lombok
- Performance Measure:
- Sampai di Lombok tepat waktu
- Biaya yang efisien
- Performance Measure:
-
- Problem Formulation adalah proses memutuskan tindakan dan keadaan yang harus dipertimbangkan untuk mencapai goal.
- Agen harus menentukan bagaimana bertindak sekarang dan di masa depan agar mencapai goal state.
- Contoh: Mengemudi ke Padangbai dengan pertimbangan waktu yang efisien dan biaya yang rendah.
- Menentukan Tindakan Selanjutnya:
- Agen bisa menelusuri tindakan di masa depan yang akan membawa pada keadaan yang diketahui.
- Contoh: Memilih jalan dari Padangbai ke Mengwi, Ngerebong, atau Kuta.
- Search: Proses mencari urutan tindakan yang membawa agen ke goal state.
- Search Algorithm: Algoritma pencarian menerima problem sebagai input dan mengembalikan solusi berupa urutan tindakan.
- Setelah solusi ditemukan, tindakan dapat dieksekusi dalam fase eksekusi.
-
Initial State: Keadaan awal tempat agen memulai.
- Contoh:
in(Denpasar)
- Contoh:
-
Possible Actions: Deskripsi dari tindakan yang bisa dilakukan agen di setiap keadaan.
- Contoh:
{go(Mengwi), go(Ngerebong), go(Kuta)}
- Contoh:
-
Transition Model: Deskripsi dari efek setiap tindakan, ditentukan oleh fungsi
RESULT(s, a)
, di manas
adalah keadaan dana
adalah tindakan.- Contoh:
RESULT(in(Denpasar), Go(Ngerebong)) = in(Ngerebong)
- Contoh:
-
State Space: Kombinasi dari initial state, actions, dan transition model membentuk state space, yang direpresentasikan sebagai jaringan atau graf dengan simpul sebagai state dan link antar simpul sebagai tindakan.
-
Goal Test: Uji untuk menentukan apakah state saat ini adalah goal state.
- Contoh:
{in(Padangbai)}
- Contoh:
-
Path Cost: Fungsi yang memberikan nilai numerik untuk setiap jalur. Agen memilih fungsi biaya yang mencerminkan performance measure.
- Abstraction: Proses menghilangkan detail dari representasi. Formulasi problem sering kali fokus pada aspek-aspek tertentu sambil mengabaikan detail lainnya.
- Contoh:
- in(Denpasar): Formulasi bisa mencakup perubahan lokasi, waktu, dan konsumsi bahan bakar, tetapi abstraksi hanya fokus pada perubahan lokasi.
- States: Ditentukan oleh lokasi agen dan lokasi kotoran, terdapat 8 possible states.
- Initial State: Bisa ditentukan oleh lokasi agen (misalnya di kiri, kiri kotor, kanan kotor).
- Actions: Kiri, kanan, hisap.
- Transition Model: Setiap tindakan mempengaruhi keadaan.
- Goal Test: Semua kotak harus bersih.
- Path Cost: Setiap langkah berbiaya 1, sehingga path cost adalah jumlah langkah dalam jalur.
- Contoh-contoh:
- Pencarian Rute
- Travelling Salesman
- Navigasi Robot
- Solusi: urutan aksi yang mencapai goal.
- Algoritma Pencarian:
- Mempertimbangkan urutan aksi yang mungkin.
- Membentuk search tree dari initial state sebagai akar.
- Nodes: status dalam ruang masalah.
- Frontier: semua node yang mungkin untuk dikembangkan.
- Proses: ekspansi node pada frontier sampai solusi ditemukan atau tidak ada status lagi yang bisa diekspansi.
- Komponen:
- Frontier Operations:
EMPTY?(queue)
→ mengembalikantrue
jika tidak ada elemen di dalam queue.POP(queue)
→ menghapus dan mengembalikan elemen pertama dari queue.INSERT(element, queue)
→ menambahkan elemen ke queue.
- Hash Table untuk mengecek status yang sudah dieksplorasi, menghindari pengulangan status.
- Frontier Operations:
- Explored Set: digunakan untuk menyimpan status yang sudah dieksplorasi, memastikan status tidak diulang.
- Completeness: Apakah algoritma menjamin menemukan solusi jika ada?
- Optimality: Apakah algoritma menemukan solusi optimal?
- Time Complexity: Berapa lama waktu yang dibutuhkan untuk menemukan solusi?
- Space Complexity: Berapa banyak memori yang dibutuhkan untuk pencarian?
- Struktur Data: Algoritma pencarian memerlukan struktur data untuk melacak search tree yang sedang dibentuk.
- Komponen setiap node (n) pada pohon pencarian:
- State: status yang direpresentasikan oleh node.
- Parent Node: node sebelumnya yang menghasilkan node ini.
- Action: tindakan yang menyebabkan transisi dari parent ke state ini.
- Path Cost: biaya jalur dari node awal hingga node saat ini.
- Depth: kedalaman node dalam pohon pencarian.
- Memastikan bahwa algoritma dapat melacak node mana yang sudah dieksplorasi (via explored set).
- Memungkinkan ekspansi frontier secara sistematis dengan mengikuti strategi pencarian (misalnya, breadth-first atau depth-first)
- Digunakan untuk mendeskripsikan efisiensi algoritma, termasuk faktor waktu dan kompleksitas ruang.
- O(n): jumlah operasi yang diperlukan oleh algoritma
- O(1): operasi konstan.
- Contoh: algoritma yang mencetak nama mahasiswa pertama yang terdaftar setiap tahun.
- O(n): operasi linear.
- Contoh: algoritma yang mencetak semua nama mahasiswa yang terdaftar.
- O(n²): operasi kuadratik.
- Contoh: mengecek input yang redundan di daftar mahasiswa.
- O(n!): operasi faktorial.
- Contoh: mencari rute umum yang diambil mahasiswa untuk ke kampus.
- Contoh masalah: Traveling Salesman Problem, Navigasi Robot, dll.
- Definisi: Tidak memiliki informasi tambahan tentang status, hanya berdasarkan definisi masalah.
- Tugas: Menghasilkan successors dan membedakan goal state dari non-goal state.
- Pembeda Utama: Urutan ekspansi node.
- Strategi: Selalu mengembangkan node terdalam pada frontier (menggunakan LIFO queue).
- Node terbaru yang dihasilkan dipilih untuk ekspansi.
- Keuntungan: Bisa menjadi algoritma tercepat.
- Kekurangan: Bisa menemukan solusi yang tidak optimal.
- Catatan: Cocok untuk pencarian dengan ruang status yang besar dan dalam.
- Strategi: Memilih node paling dangkal yang belum dikembangkan (menggunakan FIFO queue).
- Node baru masuk ke belakang antrian; node lama diperluas lebih dulu.
- Keuntungan: Selalu menemukan solusi (jika ada) karena pencarian menyeluruh.
- Kekurangan: Membutuhkan lebih banyak waktu dan memori dibanding DFS.
Poin | Breadth First Search | Depth First Search |
---|---|---|
Keuntungan | Selalu ada solusi mungkin | Bisa menjadi algoritma tercepat |
Kekurangan | Memakan waktu lebih lama | Bisa mendapatkan solusi non-optimal. |
- Definisi: Menggunakan pengetahuan spesifik masalah (heuristik) untuk menemukan solusi lebih efisien dibanding uninformed search.
- Pendekatan Umum: Best-First Search.
- Algoritma ini memilih node berdasarkan evaluation function,
f(n)
. - Heuristic Function (h(n)): Estimasi biaya dari node
n
ke goal state.
- Algoritma ini memilih node berdasarkan evaluation function,
- Strategi: Memperluas node yang paling dekat dengan goal berdasarkan heuristik (f(n) = h(n)).
- Keuntungan: Cepat dalam menemukan solusi, tapi mungkin tidak optimal.
- Strategi: Menggabungkan biaya untuk mencapai node
g(n)
dan estimasi biaya dari node ke goalh(n)
oai_citation:5,AI Search Method.pdf.- Evaluation Function:
f(n) = g(n) + h(n)
. - Keuntungan: Menemukan solusi optimal jika
h(n)
tidak melebihi biaya sebenarnya dari goal.
- Evaluation Function:
- Sifat Optimalitas:
- Estimasi biaya (h(n)) tidak boleh melebihi biaya sebenarnya (harus konsisten).
h(n) ≤ h(n’) + c
, di manac
adalah biaya dari noden
ke successorn'
- Definisi: Mengatasi kondisi kompetitif di mana agen-agen memiliki tujuan yang saling bertentangan, seperti pada permainan.
- Properti:
- Deterministik, sepenuhnya dapat diamati.
- Nilai utilitas di akhir permainan selalu sama atau berlawanan (satu menang, satu kalah).
- Tujuan: Menghitung keputusan minimax dari status saat ini.
- Minimizer berusaha mendapatkan skor terendah, sementara maximizer berusaha mendapatkan skor tertinggi.
- Digunakan dalam permainan dengan dua pemain seperti catur atau tic-tac-toe.
- Strategi: Memangkas bagian pohon yang tidak perlu dijelajahi karena sudah pasti tidak akan mengubah keputusan akhir.
- Keuntungan: Mempercepat proses pencarian tanpa mengorbankan hasil optimal.