ai_20111003

11

Click here to load reader

Upload: albaar-rubhasy

Post on 20-May-2015

484 views

Category:

Education


0 download

TRANSCRIPT

Page 1: AI_20111003

Problem Solving Agent: Searching

SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN TEKNIK KOMPUTER INDONESIA (STMIK-INDONESIA)

© 2011

Inteligensi Buatan (MKB6403)

Kuliah 3

Problem-Solving Agent

• Kelemahan reflex agent → tidak cocok untukmenangani masalah besar!

• Goal-based agent → memiliki tujuan, memungkinkan untuk mengevaluasi tindakandan memilih yang terbaikdan memilih yang terbaik

• Pada Kuliah 3 akan dibahas suatu goal-based agent: problem-solving agent

• Problem-solving agent menghasilkan solusi dalambentuk serangkaian tindakan untuk mencapaitujuan

• Apa permasalahannya? Apa solusinya?

10/19/2011 Problem Solving Agent: Searching 2

Page 2: AI_20111003

Cara Kerja Problem-Solving Agent

1. Perumusan tujuan (goal formulation): tentukantujuan yang ingin dicapai

2. Perumusan masalah (problem formulation): tentukan tindakan (action) dan keadaan (state) yang dipertimbangkan dalam mencapai tujuanyang dipertimbangkan dalam mencapai tujuan

3. Pencarian solusi masalah (searching): tentukanrangkaian tindakan yang perlu diambil untukmencapai tujuan

4. Pelaksanaan solusi (execution): laksanakanrangkaian tindakan yang sudah ditentukan ditahap sebelumnya

10/19/2011 Problem Solving Agent: Searching 3

Program Problem-Solving Agent

function SIMPLE-PROBLEM-SOLVING-AGENT(p) returns action

inputs:static:

p, a percepts, an action sequence, initially emptystate, some description of the current world stateg, a goal, initially nullproblem, a problem formulation

state ← UPDATE-STATE(state,p)if s is empty then

10/19/2011 Problem Solving Agent: Searching 4

if s is empty theng ← FORMULATE-GOAL(state)problem ← FORMULATE-PROBLEM(state,g)s ← SEARCH(problem)

action ← RECOMMENDATION(s,state)s ← REMAINDER(s,state)return action

Page 3: AI_20111003

Sifat Problem-Solving Agent

• Secara umum, problem-solving agent

mengasumsikan bahwa environment-nya:

– Accessible

– Deterministic

– Episodic

– Static

– Discrete

• Setelah mencari solusi, agent melakukan tindakan

dengan “mata tertutup” → tidak melihat percept!

10/19/2011 Problem Solving Agent: Searching 5

Contoh: Turis di Rumania

• Suatu tourist agent sedang berlibur di Rumania.

Sekarang dia berada di kota Arad. Besok, dia harus

terbang dari bandara yang ada di kota Bucharest!

• Perumusan tujuan: berada di BucharestPerumusan 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

10/19/2011 Problem Solving Agent: Searching 6

Page 4: AI_20111003

Peta Rumania

10/19/2011 Problem Solving Agent: Searching 7

Perumusan Masalah: State Space (1)

• Initial state: keadaan awal si agent, misal: BeradaDi(Arad)

• Possible action: tindakan yang dapat dilakukan siagent, misal: Nyetir(Arad,Zerind)

• Sebuah successor function S menentukan untuk• Sebuah successor function S menentukan untuksuatu state X, himpunan tindakan yang mungkindiambil beserta state yang dihasilkan. Contoh:

X = BeradaDi(Arad)

S(X) = {<Nyetir(Arad, Zerind), BeradaDi(Zerind)>, {<Nyetir(Arad, Sibiu), BeradaDi(Sibiu)>, {<Nyetir(Arad, Timisoara), BeradaDi(Timisoara)>}

10/19/2011 Problem Solving Agent: Searching 8

Page 5: AI_20111003

Perumusan Masalah: State Space (2)

• Initial state + successor function = state space

• State space → himpunan state yang dapat dicapai

dari initial state

• State space dapat direpresentasikan sebagai graph • State space dapat direpresentasikan sebagai graph

dengan path sebagai suatu rangkaian state

→ ingat tourist agent Rumania!!!

10/19/2011 Problem Solving Agent: Searching 9

Menelusuri State Space

• Goal test: penentuan apakah suatu state adalah tujuan yang

ingin dicapai

– Eksplisit: himpunan goal state, misal: {BeradaDi(Bucharest)}

– Implisit: deskripsi tujuan, misal dalam catur: skak mat

• Path cost function: fungsi yang memberikan nilai numerik• Path cost function: fungsi yang memberikan nilai numerik

terhadap setiap path. Fungsi ini merefleksikan performance

measure si agent.

• Solusi: path dari initial state ke goal state

• Solusi optimal: solusi dengan path cost function minimal

10/19/2011 Problem Solving Agent: Searching 10

Page 6: AI_20111003

Contoh: The 8-Puzzle

• State: lokasi 8 buah angka dalam matriks 3x3

• Possible action: kiri, kanan, atas, bawah

• Goal test: apakah susunan angka seperti goal state?

• Path cost: asumsi step cost = 1. Path cost = jumlah langkah

dalam path

10/19/2011 Problem Solving Agent: Searching 11

Contoh: The 8-Queens Problem

Letakkan 8 bidak menteri (queen) sedemikian rupa sehingga tidakterjadi saling “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

10/19/2011 Problem Solving Agent: Searching 12

Page 7: AI_20111003

Contoh: The Vacuum World

• State: lokasi agent, status debu

• Possible action: DoKeKiri(L), DoKeKanan(R), Sedot(S)

• Goal test: apakah semua ruangan bebas debu?

• Path cost: jumlah langkah dalam path

10/19/2011 Problem Solving Agent: Searching 13

Mencari Solusi Melalui Search Tree

• Setelah merumuskan masalah → cari solusinyamenggunakan search algorithm

• Search tree merepresentasikan state space

• Search tree terdiri dari kumpulan node → strukturdata yang merepresentasikan suatu state pada suatupath, dan memiliki parent, children, depth, dan path data yang merepresentasikan suatu state pada suatupath, 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 disebutfringe (pinggir) sebuah search tree

10/19/2011 Problem Solving Agent: Searching 14

Page 8: AI_20111003

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. Ulangi langkah sebelumnya

Arad

10/19/2011 Problem Solving Agent: Searching 15

Arad

Sibiu ZerindTimisoara

Fagaras Oradea Rimnicu Vilcea

Algoritma Penelusuran Search Tree

function GENERAL-SEARCH(problem,fringe) returns solution or failure

fringe ← INSERT(MAKE-NODE(INITIAL-STATE(problem),fringe))loop do

if fringe is EMPTY than return failurenode ← REMOVE-FIRST(fringe)if GOAL-TEST(problem) applied to STATE(node) succeeds then return node

fringe ← INSERT-ALL(EXPAND(node,problem),fringe)

1. Pada awal, fringe = himpunan node yang mewakili initial state

2. Pilih satu node dari fringe sebagai current node. Jika fringe kosong, selesai dengan gagal

3. Jika node tsb . lolos goal test, selesai dengan sukses!

4. Jika tidak, lakukan node expansion terhadap current node tsb.

5. Ulangi langkah 2

10/19/2011 Problem Solving Agent: Searching 16

fringe ← INSERT-ALL(EXPAND(node,problem),fringe)end

Page 9: AI_20111003

Strategi Pencarian

• Ada berbagai jenis strategi dalam melakukan

searching. Perbedaannya terdapat pada node

expansion-nya

• Search strategy dievaluasi berdasarkan:Search strategy dievaluasi berdasarkan:

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

10/19/2011 Problem Solving Agent: Searching 17

Jenis-jenis Strategi Pencarian

• Ada 2 jenis strategi pencarian:

– Uninformed strategy, hanya menggunakan

informasi dari definisi masalah

– Informed strategy, menggunakan informasi– Informed strategy, menggunakan informasi

lainnya

• Uninformed strategy dapat diterapkan secara

generik terhadap semua jenis masalah yang

bisa direpresentasikan dalam sebuah state

space

10/19/2011 Problem Solving Agent: Searching 18

Page 10: AI_20111003

Contoh-contoh Strategi Pencarian

Uninformed Strategy:

• Breadth-first Search

• Depth-first Search

• Depth-limited

Informed Strategy:

• Uniform Cost Search

• Greedy Best-first

Search

10/19/2011 Problem Solving Agent: Searching 19

• Depth-limited

Search

• Iterative Deepening

Search

Search

• A* Search

Latihan

Suatu tourist agent sedang berlibur di Rumania.

Sekarang dia berada di kota Bucharest. Besok, dia harus

menghadiri pertemuan di kota Arad dan harus menyetir

dari kota ke kota!

1. Tentukan task environment (PAGE)!

2. Tentukan state space (initial state + successor

function)!

10/19/2011 Problem Solving Agent: Searching 20

Page 11: AI_20111003

Peta Rumania

10/19/2011 Problem Solving Agent: Searching 21