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

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


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


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

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!


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


Peta Rumania


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


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!!!


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


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


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


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


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


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


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


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

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?


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


Contoh-contoh Strategi Pencarian

Uninformed Strategy:

• Breadth-first Search

• Depth-first Search

• Depth-limited

Informed Strategy:

• Uniform Cost Search

• Greedy Best-first

Search


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


Peta Rumania


ai_20111003

Education