Problem-Solving Agent & Search

Kecerdasan Buatan (KI092301)

Problem-Solving Agent & Search Chastine Fatichah Teknik Informatika Institut Teknologi Sepuluh Nopember November 2012

12/7/2012

Problem-Solving Agent & Search @ Kecerdasan Buatan (KI092301)

1 / 38

Pokok Bahasan

• Problem-solving agent • Representasi masalah : state space • Pencarian solusi : search • Search strategies • Uninformed search • Ringkasan 12/7/2012


2 / 38

Problem-Solving Agent

• Goal-based agent  mempertimbangkan • •

action-action yang akan datang dan hasil yang ingin dicapai Agent problem solving  Menemukan rangkaian tindakan (sequence action) untuk mencapai tujuannya Algoritma Uninformed  Tidak ada informasi untuk problem, hanya deskripsi pada masalah tersebut

12/7/2012


3 / 38

Simple Problem-Solving Agent Function Simple-Problem-Solving-Agent(percept) return an action Input : percept //a percept Static : seq //an action sequence, initially empty state //some description of the current world state goal //a goal, initially null problem //a problem formulation

State  Update-State(state, percept) If seq is empty then do goal  Formulate-Goal(state) problem  Formulate-Problem(state,goal) seq  Search(Problem) Action  First(seq) Seq  Rest(seq) Return action 12/7/2012


4 / 38

Mekanisme Kerja ProblemSolving Agent • • • •

Perumusan tujuan (goal formulation): tentukan tujuan yang ingin dicapai

• •

Kondisi saat ini Performance measure

Perumusan masalah (problem formulation): tentukan tindakan (action) dan keadaan (state) yang dipertimbangkan dalam mencapai tujuan Pencarian solusi masalah (searching) : tentukan rangkaian tindakan yang perlu diambil untuk mencapai tujuan

•

Input: problem, output: solusi dalam bentuk rangkaian tindakan

Pelaksanaan solusi (execution): laksanakan rangkaian tindakan yang sudah ditentukan di tahap sebelumnya

12/7/2012


5 / 38

Well-Define Problem & Solution

• Problem dapat dirumuskan dengan 5 komponen

• Initial state • Actions : Successor function : Successor-Fn(x) =

• Goal Test • Path Cost

• Optimal Solution  path cost terkecil

12/7/2012


6 / 38

Contoh Kasus : Romania

• Seorang agent sedang berlibur dan •

• •

sekarang sedang di kota Arad Romania Besok dia harus naik pesawat dari Bucharest Goal dari agent sekarang adalah pergi ke Bucharest Action yang tidak berhubungan dengan goal akan dibuang -> decision agent lebih sederhana

12/7/2012


7 / 38

Contoh Kasus: Romania

• Agent  Mencapai tujuan (ke Bucharest) •

dengan naik mobil Kemana akan pergi setelah dari Arad ?

• Ada tiga jalan : ke Sibiu, Timisoara, Zerind • Agent kita ini masih belum tahu jalan disana (mana yang tercepat) tapi hanya memiliki peta. • Dari informasi peta, dilakukan hipotesa terhadap ketiga jalur tsb untuk sampai ke Bucharest

12/7/2012


8 / 38

Contoh Kasus: Romania (Agent & Environment)

• Static

• Tidak perlu memperhatikan perubahan yang terjadi pada environment

• Observable

• Ada peta, initial state diketahui (di Arad)

• Discreet

• Enumeration action

• Deterministic

• Tidak bisa menangani terhadap hal-hal yang tidak diperkirakan

12/7/2012


9 / 38

Contoh Kasus: Romania (Well-Defined problem agent)

• Initial State  di Arad • Actions : Successor function  • {,

, }

• Goal Test  In(Bucharest) • Path Cost  di slide berikutnya 12/7/2012


10 / 38

Contoh Kasus: Romania (Path Cost Solusi Agent)

12/7/2012


11 / 38

Contoh Kasus: Romania (Perumusan Tujuan, Masalah, & Solusi)

• Perumusan Tujuan

• Tiba di Bucharest besok

• Perumusan Masalah

• States : kota-kota • Actions : mengemudi antar kota

• Pencarian Solusi

• Rangkaian kota : Arad, Sibiu, Fagaras, Bucharest

12/7/2012


12 / 38

Contoh Kasus: Vacuum Cleaner •

Vacuum Cleaner

• • • • •

States : Berada di salah satu dari dua lokasi yang ada, yg masing2 mungkin bersih atau kotor. Jadi jml kemungkinan state = 2 * 22 Initial State ? Successor Function ? . Goal Test ? Path Cost ?

12/7/2012


13 / 38

Contoh Kasus: Vacuum Cleaner •

Vacuum Cleaner

• • • • •

States : Berada di salah satu dari dua lokasi yang ada, yg masing2 mungkin bersih atau kotor. Jadi jml kemungkinan state = 2 * 22 Initial State : Sembarang state Successor Function : (kekiri,kekanan,bersihkan) Goal Test : Semua lokasi bersih Path Cost : Setiap aksi = 1 point

12/7/2012


14

Contoh Kasus: 8-Puzzles • 8-Puzzles

• State : ? • Initial State : ? • Successor Function : ? • •

. Goal Test : ? Path Cost : ?

12/7/2012


15 / 38

Contoh Kasus: 8-Puzzles • 8-Puzzles

• State : lokasi dari 8 kotak angka dan 1 kotak kosong • Initial State : Sembarang state • Successor Function : (kotak kosong bergerak kekiri, • •

kekanan, keatas atau kebawah) Goal Test : Tersusun kotak angka yang diinginkan Path Cost : Setiap bergerak bernilai 1

12/7/2012


16

Contoh Kasus: 8-Queen Problem • 8-Queen Problem

• State : ? • Initial State : ? • Successor Function : ? •

. .

. Goal Test : ? .

12/7/2012


17

Contoh Kasus: 8-Queen Problem • 8-Queen Problem

• State : susunan 0..8 ratu pada •

• •

papan catur Initial State : Tidak ada ratu pada papan catur Successor Function : Masukkan ratu ke papan catur Goal Test : Tidak ada ratu yang saling serang

12/7/2012


18 / 38

Real World Problem

• Airline Travel Problem • Touring Problem • Traveling Salesman Problem • VLSI Layout • Robot Navigation • Automatic Assembly Sequencing • Internet Searching 12/7/2012


19 / 38

Searching for Solution • • • • • •

•

Search Tree Search Node  Root of search tree : Initial State : In(Arad) Cek node apakah ini goalnya? Jika tidak, Expanding  menghasilkan state baru State mana yang akan di expand?  search strategy Representasi Node :

• • • • •

State Parent-Node Action Path-Cost Depth

Fringe  node collection hasil generate yang belum diexpand

Function Tree-Search(problem,strategy) return a solution or a failure initialize the search tree using the initial state loop do if there are no candidates for expansion then return failure choose a leaf node for expansion according strategy if the node contains a goal state then return the coresponding solution else expand the node and add the resulting node to the search tree 12/7/2012


20 / 38

Contoh Search Tree

12/7/2012


21 / 38

Tree Search Secara Umum Function Tree-Search(problem,fringe) return a solution or a failure fringe  Insert(Make-Node(Initial-State[problem]),fringe) loop do if empty ?(fringe) then return failure node  Remove-First(fringe) if Goal-Test[problem] applied to State[node] succeds then return Solution(node) fringe  Insert-All(Expand(node,problem),fringe) _________________________________________________________________________ Function Expand(node,problem) return a set of nodes successor  the empty set for each (action,result) in Successor-Fn[problem](State[node]) do s  a new Node State[s]  result Parent-node[s]  node Action[s]  action Path-Cost[s]  Path-Cost[node] + Step-Cost(node,action,s) Depth[s]  Depth[node] + 1 add s to successor return successors 12/7/2012


22 / 38

Search Strategies • Strategy  memilih node yang akan diexpand : • Completeness Menemukan solusi jika ada • Optimality  Optimal solution (cost terkecil) • Time Complexity  berapa lama menemukan solusinya ? • Space Complexity  berapa banyak memory yang dibutuhkan ?

• Time dan Space Complexity bisa dilihat dari ukuran :

• b  maks branch factor • d  depth dari solusi terkecil • m  maks depth dari state space

12/7/2012


23 / 38

Uninformed Search Strategies

• Breadth-First search • Uniform-cost search • Depth-first search • Depth-limited search • Iterative deepening search • Bidirectional search 12/7/2012


24 / 38

Breadth-First Search (BFS)

• Setelah Root di expand, selanjutnya •

successor dari root, selanjutnya successor dari successor mereka  expand melebar Mengimplementasikan fringe  FIFO A

B

D 12/7/2012

C

E

F


G 25 / 38

Keterangan pada BFS

• Complete ? Ya, jika b terbatas • Time ? 1 + b + b + b + … + b + b(b -1) = O(b ) • Space ? O(bd+1) • Optimal ? Ya, jika semua aksi bernilai sama • Masalah  Space & Time. Lihat buku hal 2

3

d

d

d+1

74

12/7/2012


26 / 38

Uniform Cost Search • • • • • •

•

Hampir sama dengan BFS  melebar Bedanya pada pemilihan node yang akan diexpand  cost terkecil

•

Fringe = queue berdasarkan cost terkecil

Jika masing-masing node memiliki cost yang sama = BFS Complete ? Ya jika step cost >= Є (positif const) Time ? O(b C*/ Є) ; C* = Optimal solution

•

Jumlah node dengan g <= cost optimal solution

Space ? O(b C*/ Є)

•

Jumlah node dengan g <= cost optimal solution

Optimal ? Ya, node diekspand  urutan penambahan g(n)

12/7/2012


27 / 38

Depth-First Search (DFS) • Expand node yang terdalam • Fringe  LIFO

B

12/7/2012

F

• •

G

• •

Tidak jika memiliki depth tak terbatas, Modifikasi untuk limited depth Ya, jika depth terbatas

Time ? O(bm)

• •

C

E

Complete ?

•

•

A

D

•

Bermasalah jika m jauh lebih besar dari d Jika solusinya banyak/dense, bisa lebih cepat dari BFS

Space ? O(bm), linier space Optimal ? Tidak


28 / 38

Depth-Limited Search

• Sama dengan DFS dengan deep limit l • Implementasi dengan Rekursif Function Depth-Limited-Search(problem,limit) return a solution or a failure/cutoff return Recursive-DLS(Make-Node(Initial-State[problem]),problem,limit) Function Recursive-DLS(node,problem,limit) return a solution or failure/cutoff cutoff_occured?  false if Goal-Test[problem](State[node]) then return solution else if Depth[node] = limit then return cutoff else for each successor in Expand(node,problem) do result  recursive-DLS(successor,problem,limit) if result  cutoff then cutoff_occured?  true else if result <> failure then return result if cutoff_occured? Then return cutoff else return failure

12/7/2012


29 / 38

Iterative-deepening Search

• Merupakan DFS yang diiterasi berdasarkan • •

kedalamannya Mengkombinasi DFS dan BFS Bottom level digenerate 1x, sedangkan dilevel berikutnya digenerate 2x, 3x dan seterusnya

Function Iterative-Deepening-Search(problem) return a solution or a failure input problem // a problem

for depth  0 to  do result  Depth-Limited-Search(problem,depth) if result <> cutoff then return result

12/7/2012


30 / 38

Iterative-deepening Search A

Limit = 3 0 1 2 B

D

H

12/7/2012

C

E

I

J

F

K

G

L


M

31 / 38

Keterangan pada IDS • Complete ? Ya • Time ? (d+1)b0 + (d)b + (d-1)b2+…+bd= O(bd) •

BFS menggenerate node sampai d + 1 sementara IDS hanya d  IDS lebih cepat dari BFS

• Space ? O(bd) • Optimal ? Ya, jika memiliki cost yang sama untuk tiap aksi

•

Bisa dimodifikasi untuk uniform cost

• •

N(IDS) : 50 + 400 + 3.000 + 20.000 + 100.000 = 123.450 N(BFS) : 10 + 100 + 1.000 + 10.000 + 100.000 + 999.990 = 1.111.100

• Perbandingan IDS >< BFS : b = 10; d = 5 12/7/2012


32 / 38

Bidirectional Search • • •

Mencari dari 2 arah secara simultan Motivasi  bd/2 + bd/2 jauh lebih kecil dari bd Misal d = 6, masing2 menggunakan BFS  depth=3, b=10; dengan bidirectional hanya 22.200 node sedang dengan BFS standar mencapai 11.111.000 node

12/7/2012


33 / 38

Perbandingan: Uninformed search strategies Criteria

BFS

Uniform

DFS

DLS

IDS

bdirect

Complete

Ya

Ya

No

No

Ya

Ya

Time

O(bd+1) O(bC*/ Є)

O(bm)

O(bl)

O(bd)

O(bd/2)

Space

O(bd+1) O(bC*/ Є)

O(bm)

O(bl)

O(bd)

O(bd/2)

Optimal

Ya

No

No

Ya

Ya

12/7/2012

Ya


34 / 38

Menghindari Repeated States • •

Pada beberapa kasus, ada kemungkinan terjadi state yang berulang  looping

•

solveable problem  unsolveable problem

Dibuat closed list  menyimpan node yang sudah diexpand

•

Node yang tidak bisa diexpand  open list

Function Graph-Search(problem,fringe) return a solution or a failure closed  empty set fringe  Insert(Make-Node(Initial-State[problem]),fringe) loop do if empty ?(fringe) then return failure node  Remove-First(fringe) if Goal-Test[problem](State[node]) then return Solution(node) if State[node] is not in closed then add State[node] to closed fringe  Insert-All(Expand(node,problem),fringe) 12/7/2012


35

Pencarian dengan Informasi Parsial • • • •

Deterministic, Fully Observable  Single state problem

• •

Agent tahu pasti state-state apa saja yang akan dimasuki Solusi berupa sequence

• •

Agent masih belum tahu pasti dimana posisinya Solusi (jika ada) berupa sequence

• • •

Percept memberikan informasi baru mengenai kondisi saat itu Solusi berupa tree or policy Interleace search

Non Observable  Sensorless/Conformant Problem Nondeterministic and/or partially observable  contingency problem

Unknown state space  Exploration Problem (“online”)

12/7/2012


36 / 38

Ringkasan • • • • • • • • •

Problem solving agents Perumusan masalah  state space Pencarian solusi  penelusuran search tree Breadth-first search: completeness terjamin, tapi rakus memory Uniform-cost search: mirip BFS, optimality terjamin jika cost path untuk > 0 Depth-first search: Space complexity linier, tetapi tidak complete (maupun optimal) Depth-limited search: mirip DFS, tetapi kedalaman search dibatasi sampai Iterative-deepening search: lakukan DLS secara bertahap dengan = 0, 1, 2, . . .. Pengulangan state bisa dihindari dengan mencatat state yang sudah pernah dicoba

12/7/2012


37 / 38

Sumber : 1. Slide perkuliahan Stuart Russell's (Berkeley) http://aima.cs.berkeley.edu/ 2. Slide perkuliahan Sistem Cerdas Ruli Manurung (Universitas Indonesia) http://www.cs.ui.ac.id/WebKuliah/IKI30320/

12/7/2012


38 / 38

Problem-Solving Agent & Search

Recommend Documents