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

  • Select an option

    Learn more about clone URLs
  • Save alizaenazet/d366b879a5706caddb1a751ce713493c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save alizaenazet/d366b879a5706caddb1a751ce713493c to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. alizaenazet revised this gist Oct 9, 2024. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions AI AFL 1 Cheat sheet.md
    View file
    Original file line number Diff line number Diff line change
    @@ -297,6 +297,7 @@ Untuk mendefinisikan lingkungan tugas agen, gunakan P.E.A.S. Contoh:
    - **Contoh masalah**: Traveling Salesman Problem, Navigasi Robot, dll.

    ---
    ---


    # Metode Pencarian dalam AI
  2. alizaenazet created this gist Oct 9, 2024.
    364 changes: 364 additions & 0 deletions AI AFL 1 Cheat sheet.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,364 @@

    # 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](file-service://file-aVGLiw6Wnvdl2bHXz5G0pGhl).
    - **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.