Problem-solving Agent: Searching

Problem-solving Agent: Searching Kuliah 3 Sistem Cerdas 5 April 2010 STMIK Indonesia

Problem-Solving Problem Solving Agent

Kelemahan reflex agent → tidak cocok untuk menangani masalah l h besar! b ! Goal-based agent → memiliki tujuan, memungkinkan untuk mengevaluasi tindakan dan memilih yang terbaik Pada Kuliah 3 akan dibahas suatu goal-based agent: problem-solving agent Problem-solving agent menghasilkan solusi dalam bentuk serangkaian tindakan untuk mencapai tujuan Apa permasalahannya? Apa solusinya?

4/5/2010

Problem-solving Agent: Searching

2

Cara Kerja Problem Problem-Solving Solving Agent 1.

2.

3.

4 4.

Perumusan tujuan (goal formulation): tentukan tujuan yang ingin i i di dicapaii Perumusan masalah (problem formulation): tentukan tindakan (action) dan keadaan (state) yang dipertimbangkan dalam mencapai tujuan Pencarian solusi masalah (searching): tentukan rangkaian k i tindakan i d k yang perlu l di diambil bil untuk k mencapaii tujuan Pelaksanaan solusi (execution): laksanakan rangkaian tindakan yang sudah ditentukan di tahap sebelumnya

4/5/2010


3

Program Agent Problem-Solving Problem Solving Agent function SIMPLE-PROBLEM-SOLVING-AGENT(p) returns action inputs: puts static:

p, a pe percept cept s, an action sequence, initially empty state, some description of the current world state g, a goal, initially null problem, p , a p problem formulation

state ← UPDATE-STATE(state,p) if s is empty then g ← FORMULATE-GOAL(state) problem ← FORMULATE-PROBLEM(state,g) FORMULATE PROBLEM(state g) s ← SEARCH(problem) action ← RECOMMENDATION(s,state) s ← REMAINDER(s,state) return action

4/5/2010


4

Sifat Problem Problem-Solving Solving Agent

Secara umum, problem-solving agent mengasumsikan b h bahwa environment-nya: i t

Accessible Deterministic Episodic Static Discrete

Setelah mencari solusi, agent melakukan tindakan dengan “mata tertutup” → tidak melihat percept!

4/5/2010


5

Contoh: Turis di Rumania

Suatu tourist agent sedang berlibur di Rumania. S k Sekarang dia di b berada d di kkota t A Arad. d B Besok, k di dia h harus terbang dari bandara yang ada di kota Bucharest! Perumusan tujuan: berada di Bucharest Perumusan masalah:

Tindakan (action): menyetir dari kota ke kota Keadaan (state): kota-kota di Rumania

Pencarian solusi: rangkaian kota yang dituju, misal: Arad Sibiu Fagaras Bucharest Arad-Sibiu-Fagaras-Bucharest

4/5/2010


6

Peta Rumania

4/5/2010


7

Perumusan Masalah sebagai State Space (1)

Initial state: keadaan awal si agent, misal: B d Di(A d) BeradaDi(Arad) Possible action: tindakan yang dapat dilakukan si agent, misal: Nyetir(Arad,Zerind) Sebuah successor function S menentukan untuk suatu state X, himpunan tindakan yang mungkin diambil b beserta state yang dih dihasilkan. ilk C Contoh: h X = BeradaDi(Arad) S(X) = {, BeradaDi(Zerind)> …}}

4/5/2010


8

Perumusan Masalah sebagai State Space (2)

Initial state + successor function = state space State space → himpunan state yang dapat dicapai dari initial state St t space dapat State d t direpresentasikan di t ik sebagai b i graph h dengan path sebagai suatu rangkaian state → ingat tourist agent Rumania!!!

4/5/2010


9

Menelusuri suatu State Space

Goal test: penentuan apakah suatu state adalah tujuan yang ingin i i di dicapaii

Eksplisit: himpunan goal state, misal: {BeradaDi(Bucharest)} Implisit: p deskripsi p tujuan, j misal dalam catur: skak mat

Path cost function: fungsi yang memberikan nilai numerik terhadap setiap path. Fungsi ini merefleksikan performance measure si agent agent. Solusi: path dari initial state ke goal state Solusi optimal: solusi dengan path cost function minimal

4/5/2010


10

Contoh: The 8-Puzzle 8 Puzzle

State: lokasi 8 buah angka dalam matriks 3x3 P Possible ibl action: ti ki i kkanan, atas, kiri, t b bawah h Goal test: apakah susunan angka seperti goal state? Path cost: asumsi step cost = 1. Path cost = jumlah langkah dalam path

4/5/2010


11

Contoh: The 8-Queens 8 Queens Problem

Letakkan 8 bidak menteri (queen) sedemikian rupa sehingga tidak terjadi saling “makan” makan antara satu menteri dengan yang lainnya State: papan catur dengan 0 sampai 8 bidak menteri Possible action: letakkan sebuah bidak menteri di posisi yang kosong Goal test: 8 menteri di papan, tidak ada saling makan Path cost: 0

4/5/2010


12

Contoh: The Vacuum World

State: lokasi agent agent, status debu Possible action: DoKeKiri(L), DoKeKanan(R), Sedot(S) Goal test: apakah semua ruangan bebas debu? P th cost: Path t jumlah j l h llangkah k hd dalam l path th

4/5/2010


13

Mencari Solusi Melalui Search Tree

Setelah merumuskan masalah → cari solusinya menggunakan k search h algorithm l ith Search tree merepresentasikan state space Search tree terdiri dari kumpulan node → struktur data yang merepresentasikan suatu state pada suatu path, dan memiliki parent, children, depth, dan path cost Root node merepresentasikan initial state Node expansion merupakan penerapan successor function terhadap node menghasilkan children baru Kumpulan semua node yang belum di-expand disebut g ((pinggir) gg ) sebuah search tree fringe

4/5/2010


14

Contoh Penelusuran Search Tree

Mulai dari root node (Arad) sebagai current node Lakukan node expansion Pilih salah satu node yang di-expand sebagai current node yang baru. baru Ulangi langkah sebelumnya Arad

Sibiu

Arad

4/5/2010

Fagaras

Timisoara

Oradea

Zerind

Rimnicu Vilcea


15

Algoritma Penelusuran Search Tree function GENERAL-SEARCH(problem,fringe) returns solution or failure fringe ← INSERT(MAKE-NODE(INITIAL-STATE(problem),fringe)) l loop d do if fringe is EMPTY than return failure node ← REMOVE-FIRST(fringe) if GOAL-TEST(problem) applied to STATE(node) succeeds th then return t node d fringe ← INSERT-ALL(EXPAND(node,problem),fringe) end 1 1. 2. 3 3. 4. 5.

Pada awal, awal fringe = himpunan node yang mewakili initial state Pilih satu node dari fringe sebagai current node. Jika fringe kosong, selesai dengan gagal Jika node tsb . lolos goal test, test selesai dengan sukses! Jika tidak, lakukan node expansion terhadap current node tsb. Ulangi langkah 2

4/5/2010


16

Strategi Pencarian

Ada berbagai jenis strategi dalam melakukan searching. P b d Perbedaannya tterdapat d t pada d node d expansion-nya i Search strategy dievaluasi berdasarkan:

4/5/2010

Completeness: apakah solusi (jika ada) pasti ditemukan? Time complexity: berapa lama untuk mencari solusi? atau berapa banyak jumlah node yang di-expand? Space complexity: jumlah maksimum node di dalam memori Optimality: apakah solusi dengan minimum cost pasti ditemukan?


17

Uninformed Search Strategies

Uninformed strategy hanya menggunakan informasi d id dari definisi fi i i masalah l h Dapat diterapkan secara generik terhadap semua jenis masalah yang bisa direpresentasikan dalam sebuah state space Jenis-jenis uninformed strategy:

4/5/2010

Breadth-first search Uniform cost search Depth-first p search Depth-limited search Iterative deepening search


18

Problem-solving Agent: Searching

Recommend Documents