Path Planning Algorithms: BFS, DFS, UCS, Greedy Search

Penentuan Penentuan Rute ( (Route/Path Planning Route/Path Planning) ) Rute Bagian Bagian 1: BFS, DFS, UCS, Greedy Best First Search 1: BFS, DFS, UCS, Greedy Best First Search IF221 Strategi Algoritma Program Studi Informatika STEI-ITB

Referensi 1. Materi kuliah IF3170 Inteligensi Buatan Teknik Informatika ITB, Course Website: http://kuliah.itb.ac.id STEI Teknik Informatika IF3170 2. Stuart J Russell & Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd Edition, Prentice-Hall International, Inc, 2010, Textbook Site: http://aima.cs.berkeley.edu/ (2nd edition) 3. Free online course materials | MIT OpenCourseWare Website: Site: http://ocw.mit.edu/courses/electrical-engineering-and- computer-science/ 4. Lecture Notes in Informed Heuristic Search, ICS 271 Fall 2008, http://www.ics.uci.edu/~dechter/courses/ics-271/fall-08/lecture- notes/4.InformedHeuristicSearch.ppt 2 IF2211/NUM/29Mar2016

Route Planning 3 IF2211/NUM/29Mar2016

Source: Russells book Search O F 71 151 S 99 Z 211 75 A 80 140 R B P 97 120 101 118 D 75 M 146 138 T 70 L 111 C (a part of graph of Romania) S: set of cities i.s: A (Arad) g.s: B (Bucharest) Goal test: s = B ? Path cost: time ~ distance 5 IF2211/NUM/29Mar2016

Blind Search Uninformed Search Uninformed Search BFS ( BFS (Breadth First Search Breadth First Search) ) DFS ( DFS (Depth First Search Depth First Search) ) DLS ( DLS (Deep Limited Search Deep Limited Search) ) IDS ( IDS (Iterative Deepening Search Iterative Deepening Search) ) UCS ( UCS (Uniform Cost Search Uniform Cost Search) ) 6 IF2211/NUM/29Mar2016

A Pohon BFS Breadth-First Search (BFS) Treat agenda as a queue (FIFO) Z S T O O O F R F L 71 S 151 Z 99 211 75 B P C Goal M A 80 140 R B Simpul-E Simpul Hidup P 97 101 120 A ZA,SA,TA 118 ZA SA,TA,OAZ D 75 138 SA TA,OAZ,OAS,FAS,RAS M 146 T 70 L 111 TA OAZ,OAS,FAS,RAS,LAT C Queue OAZ OAS,FAS,RAS,LAT OAS FAS,RAS,LAT Path: A Path-cost = 450 S F B, FAS RAS,LAT,BASF RAS LAT,BASF,DASR,CASR,PASR LAT BASF,DASR,CASR,PASR,MATL 7 BASF Solusi ketemu IF2211/NUM/29Mar2016

A Depth-First Search (DFS) Pohon DFS Treat agenda as a stack (LIFO) S Z T O F 71 S 151 Z 99 O 211 75 A S 80 140 R B P 97 120 F R 101 118 D 75 M 146 138 B Stack Goal T 70 L 111 C Simpul-E Simpul Hidup A ZA,SA,TA ZA OAZ, SA,TA Path: A Path-cost = 607 Z O S F B OAZ SAZO,SA,TA SAZO FAZOS, RAZOS,SA,TA FAZOS BAZOSF, RAZOS,SA,TA 8 IF2211/NUM/29Mar2016 BAZOSF Solusi ketemu

Pohon IDS Iterative Deepening Search (IDS) Depth 0 A O F 71 S 151 Z 99 Z 1 S T 211 75 A 80 140 R O R 2 L F B P 97 120 101 118 B Goal D 3 75 M 146 138 T 70 L 111 C Depth=0: A: cutoff Depth=1: A ZA,SA,TA ZA: cutoff, SA: cutoff, TA: cutoff Depth=2: A ZA,SA,TA OAZ, SA,TA OAZ : cutoff FAS, RAS,TA FAS : cutoff RAS : cutoff LAT LAT : cutoff Depth=3: A ZA,SA,TA OAZ, SA,TA SAZO,SA,TA SAZO: cutoff FAS, RAS,TA BASF, RAS,TA BASF Stop: B=goal, path: A S F B, path-cost = 450 IF2211/NUM/29Mar2016 9

Simpul-E Simpul Hidup Uniform Cost Search (UCS) A ZA-75, TA-118, SA-140 ZA-75 TA-118, SA-140,OAZ-146 TA-118 SA-140,OAZ-146,LAT-229 BFS & IDS find path with fewest steps (A-S-F-B) If steps cost, this is not relevant (to optimal solution) How can we find the shortest path (measured by sum of distances along path)? g(n) = path cost from root to n SA-140 OAZ-146,RAS-220, LAT-229,FAS-239,OAS-291 OAZ-146 RAS-220, LAT-229, FAS-239,OAS-291 RAS-220 LAT-229, FAS-239,OAS-291, PASR-317,DASR-340,CASR-366 LAT-229 FAS-239,OAS-291,MATL-299, PASR-317,DASR-340,CASR-366 FAS-239 OAS-291,MATL-299,PASR-317,DASR-340,CASR-366,BASF-450 O OAS-291 MATL-299,PASR-317,DASR-340,CASR-366,BASF-450 71 F S 151 Z 99 211 MATL-299 PASR-317,DASR-340,DATLM-364,CASR-366,BASF-450 75 A 80 140 R PASR-317 DASR-340,DATLM-364,CASR-366,BASRP-418, CASRP-455, BASF- B 97 P 120 450 101 DASR-340 DATLM-364,CASR-366,BASRP-418, CASRP-455, BASF-450 118 D 75 M 146 138 T 70 DATLM-364 CASR-366,BASRP-418, CASRP-455, BASF-450 111 L C Path: A Path-cost = 418 S R P optimal solution B CASR-366 BASRP-418, CASRP-455, BASF-450 10 IF2211/NUM/29Mar2016 BASRP-418 Solusi ketemu

Heuristic Search Informed Search Informed Search Greedy Best First Search Greedy Best First Search A* A* 11 IF2211/NUM/29Mar2016

Greedy Best-First Search Idea: use an evaluation function f(n) for each node f(n) = h(n) estimates of cost from n to goal e.g., hSLD(n) = straight-line distance from n to Bucharest Greedy best-first search expands the node that appears to be closest to goal Romania with step costs in km: 12 IF2211/NUM/29Mar2016

Greedy best-first search example 13 IF2211/NUM/29Mar2016

Greedy best-first search example 14 IF2211/NUM/29Mar2016

Greedy best-first search example 15 IF2211/NUM/29Mar2016

Greedy best-first search example Path: Arad Path-cost = 450 Sibiu Fagaras not optimal solution Bucharest, 16 IF2211/NUM/29Mar2016

Problems with Greedy Best First Search 1. Not complete Lasi to Fragaras?

Problems with Greedy Best First Search 2. Get stuck with local minima/plateu 3. Irrevocable (not able to be reversed/changed) 4. Can we incorporate heuristics in systematic search? 18 IF2211/NUM/29Mar2016

(Bersambung pada Bagian 2)