Skip to content

Instantly share code, notes, and snippets.

@alizaenazet

alizaenazet/AI AFL 1 Cheat sheet.md

Last active October 9, 2024 18:55
Show Gist options
  • Save alizaenazet/d366b879a5706caddb1a751ce713493c to your computer and use it in GitHub Desktop.
Save alizaenazet/d366b879a5706caddb1a751ce713493c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
AI AFL 1 Cheat sheet.md

Artificial Intelligence (AI)

Definition

  • Kecerdasan Buatan adalah cabang ilmu komputer yang berfokus pada simulasi perilaku cerdas di dalam komputer.
  • Mengacu pada kemampuan mesin untuk meniru perilaku cerdas manusia.

Capabilities of AI

  1. Natural Language Processing (NLP): Memungkinkan AI untuk berkomunikasi dalam bahasa seperti Inggris atau bahasa lainnya.
  2. Knowledge Representation: Memungkinkan AI untuk menyimpan apa yang diketahui atau didengarnya.
  3. Automated Reasoning: Menggunakan informasi yang disimpan untuk menjawab pertanyaan dan menarik kesimpulan baru.
  4. Machine Learning: Beradaptasi dengan keadaan baru dan mendeteksi pola-pola untuk diekstrapolasi.

Agents

Definition

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

Types of Agents

  • Sprinkler A: Menyala saat dibutuhkan berdasarkan kondisi cuaca → Agen
  • Sprinkler B: Selalu menyala pada jam 2 siang → Bukan Agen

Intelligent Agents

Definition

  • An intelligent agent is capable of:
    1. Perceiving its environment.
    2. Reasoning to make decisions.
    3. Taking actions autonomously to achieve goals.

Characteristics of an Intelligent Agent

  1. Autonomy: Bertindak tanpa campur tangan langsung.
  2. Perception: Mampu mengamati dan memantau lingkungan sekitarnya.
  3. Reasoning and Decision Making: Memilih tindakan terbaik.
  4. Action: Melakukan aksi untuk mencapai tujuan.
  5. Adaptation and Learning: Menyesuaikan perilaku berdasarkan pengalaman.

Agen Rasional

Konsep Rasionalitas

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

Faktor Rasionalitas

Rasionalitas pada suatu waktu tergantung pada 4 hal:

  1. Ukuran kinerja yang menentukan kriteria keberhasilan.
  2. Pengetahuan awal agen tentang lingkungan.
  3. Tindakan yang dapat dilakukan oleh agen.
  4. Urutan persepsi agen hingga saat ini.

Agen rasional akan memilih tindakan yang memaksimalkan ukuran kinerjanya berdasarkan urutan persepsi dan pengetahuan yang dimiliki.

Lingkungan Tugas Agen

P.E.A.S (Performance, Environment, Actuators, Sensors)

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.

Sifat Lingkungan Tugas

1. Fully Observable vs Partially Observable

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

2. Single Agent vs Multi Agent

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

3. Deterministic vs Stochastic

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

4. Episodic vs Sequential

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

5. Static vs Dynamic

  • Static: Lingkungan tidak berubah saat agen mempertimbangkan tindakan.
  • Dynamic: Lingkungan bisa berubah saat agen berpikir, sehingga agen harus terus memantau.

6. Continuous vs Discrete

  • Continuous: Keadaan agen berubah secara bertahap dan berkelanjutan, contohnya mengemudi taksi.
  • Discrete: Keadaan agen berubah dalam langkah-langkah diskrit, seperti permainan catur.

Struktur dan Program Agen

Struktur Agen

  • Tugas AI adalah mendesain program agen yang mengimplementasikan fungsi agen—memetakan dari persepsi ke tindakan.

Program Agen: Contoh

Urutan Persepsi Tindakan
[A, Bersih] Pindah ke kanan
[A, Kotor] Sapu debu
[B, Bersih] Pindah ke kiri
[B, Kotor] Sapu debu

Jenis Agen

1. Simple Reflex Agent

  • Agen yang memilih tindakan hanya berdasarkan persepsi saat ini, tanpa memperhatikan sejarah persepsi.

2. Learning Agent

  • Tujuan dari agen ini adalah untuk belajar dari lingkungan yang belum diketahui sebelumnya dan menjadi lebih kompeten seiring waktu.

Goal Formulation

  • 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

Problem Formulation

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

Langkah-langkah dalam Formulasi Problem

  1. 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 Solution

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

Komponen Problem

  1. Initial State: Keadaan awal tempat agen memulai.

    • Contoh: in(Denpasar)

  2. Possible Actions: Deskripsi dari tindakan yang bisa dilakukan agen di setiap keadaan.

    • Contoh: {go(Mengwi), go(Ngerebong), go(Kuta)}

  3. Transition Model: Deskripsi dari efek setiap tindakan, ditentukan oleh fungsi RESULT(s, a), di mana s adalah keadaan dan a adalah tindakan.

    • Contoh: RESULT(in(Denpasar), Go(Ngerebong)) = in(Ngerebong)

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

  5. Goal Test: Uji untuk menentukan apakah state saat ini adalah goal state.

    • Contoh: {in(Padangbai)}

  6. Path Cost: Fungsi yang memberikan nilai numerik untuk setiap jalur. Agen memilih fungsi biaya yang mencerminkan performance measure.

Abstraction in Problem Formulation

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

Contoh Problem: Vacuum Cleaner Robot

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

Real World Problem

  • Contoh-contoh:
    • Pencarian Rute
    • Travelling Salesman
    • Navigasi Robot

Solusi Masalah & Algoritma dalam Agent AI

1. Searching for Solution

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

2. TREE-SEARCH Algorithm

  • Proses: ekspansi node pada frontier sampai solusi ditemukan atau tidak ada status lagi yang bisa diekspansi.
  • Komponen:
    • Frontier Operations:
      • EMPTY?(queue) → mengembalikan true 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.

3. GRAPH-SEARCH

  • Explored Set: digunakan untuk menyimpan status yang sudah dieksplorasi, memastikan status tidak diulang.

4. Evaluasi Kinerja Pencarian

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

5. Infrastructure of Search Algorithm

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

Tujuan dari Struktur Data:

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

6. Notasi Big O

  • Digunakan untuk mendeskripsikan efisiensi algoritma, termasuk faktor waktu dan kompleksitas ruang.
  • O(n): jumlah operasi yang diperlukan oleh algoritma

Contoh Notasi Big O:

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

Real World Problem Example

  • Contoh masalah: Traveling Salesman Problem, Navigasi Robot, dll.

Metode Pencarian dalam AI

1. Uninformed Search Strategies (Blind Search)

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

a. Depth-First Search (DFS)

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

b. Breadth-First Search (BFS)

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

Perbandingan BFS vs 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.

2. Informed (Heuristic) Search Strategies

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

a. Greedy Best-First Search

  • Strategi: Memperluas node yang paling dekat dengan goal berdasarkan heuristik (f(n) = h(n)).
  • Keuntungan: Cepat dalam menemukan solusi, tapi mungkin tidak optimal.

b. A* Search

  • Strategi: Menggabungkan biaya untuk mencapai node g(n) dan estimasi biaya dari node ke goal h(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.
  • Sifat Optimalitas:
    • Estimasi biaya (h(n)) tidak boleh melebihi biaya sebenarnya (harus konsisten).
    • h(n) ≤ h(n’) + c, di mana c adalah biaya dari node n ke successor n'

3. Adversarial Search (Pencarian Kompetitif)

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

a. Minimax Algorithm

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

b. Alpha-Beta Pruning

  • Strategi: Memangkas bagian pohon yang tidak perlu dijelajahi karena sudah pasti tidak akan mengubah keputusan akhir.
  • Keuntungan: Mempercepat proses pencarian tanpa mengorbankan hasil optimal.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment