Shortest Path and Informed Search Brian C. Williams 16.410 - 13 October 27 th , 2003 Slides adapted from: 6.034 Tomas Lozano Perez, Winston, and Russell and Norvig AIMA Brian Williams, Spring 03 2 Assignment ? “Introduction to Algorithms” Ch. 25.1-.2 AIMA Ch. 4.1-2 ? 3 rd . Reading: Cormen Leiserson & Rivest, Homework: Brian Williams, Spring 03 – Shortest path: – Informed search and exploration: – Online problem set #6 due Monday November 1 Brian Williams, Spring 03 3 How do we maneuver? 4 Roadmaps are an effective state space abstraction Brian Williams, Spring 03 Courtesy of U.S. Geological survey. Images taken from NASA's website: http://www.nasa.gov/. 6 5 u v 1 x y 2 10 5 7 9 2 3 4 6 s Weighted Graphs and Path Lengths Graph G = <V, E> Weight function w: E :? Path p = < v o , v 1 , … v k > Path weight w(p) =  w(v i-1 ,v i ) Shortest path weight / (u,v) = min {w(p) : u : p v } else ? Outline ? planning ? Shortest Paths – ? – ? ? ? ? ? ? Creating road maps for path Exploring roadmaps: Single Source Dijkstra;s algorithm Informed search Uniform cost search Greedy search A* search Beam search Hill climbing Avoiding adversaries – (Next Lecture) Brian Williams, Spring 03 Brian Williams, Spring 03 Single Source Shortest Path u v 1 10 9 2 3 4 6 s 7 5 2 x y Problem: Compute shortest path to all vertices from source s Brian Williams, Spring 03 7 Single Source Shortest Path u v 1 89 10 9 2 3 4 6 s 0 7 5 57 2 x y Problem: Compute shortest path to all vertices from source s ? estimate d[v] estimated shortest path length from s to v Brian Williams, Spring 03 8 89 Single Source Shortest Path u v 1 10 9 0 2 3 4 6 s 7 5 57 2 x y Problem: Compute shortest path to all vertices from source s ? estimate d[v] estimated shortest path length from s to v ? predecessor ? [v] final edge of shortest path to v ? induces shortest path tree Brian Williams, Spring 03 9 Properties of Shortest Path u v 1 89 10 9 2 3 4 6 s 0 7 5 57 2 x y ? Subpaths of shortest paths are shortest paths. ?s: p v = <s, x, u, v> ?s: p u = <s, x, u> ?s: p x = <s, x> ?x: p v = <x, u, v> ?x : p v = <x, u> Brian Williams, Spring 03 10 ?u: p v = <u, v> 89 Properties of Shortest Path u v 1 10 9 0 2 3 4 6 s 7 5 57 2 x y Corollary: Shortest paths are grown from shortest paths. ? The length of shortest path s : p u :v is / (s,v) = / (s,u) + w(u,v). ?  <u,v> ?E / (s,v) ?/(s,u) + w(u,v) Brian Williams, Spring 03 11 Idea: Start With Upper Bound u v 1 ?? 10 9 2 3 4 6 s 0 7 5 ?? 2 x y Initialize-Single-Source(G, s) 1. for each vertex v ? V[G] 2. do d[u] 8? 3. ? [v] 8NIL 4. d[s] 80 O(v) Brian Williams, Spring 03 12 Relax Bounds to Shortest Path u v u v 22 5 9 5 6 Relax(u, v) Relax(u, v) u v u v 22 57 56 Relax (u, v, w) 1. if d[u] + w(u,v) < d[v] 2. do d[v] 8d[u] + w(u,v) 3. ? [v] 8u Brian Williams, Spring 03 13 Properties of Relaxing Bounds u v u v 22 5 9 5 6 Relax(u, v) Relax(u, v) u v u v 22 59 56 After calling Relax(u, v, w) ? d[u] + w(u,v) ? d[v] d remains a shortest path upperbound after repeated calls to Relax. Once d[v] is the shortest path its value persists Brian Williams, Spring 03 14 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 ?? 10 9 0 2 3 4 6 s 7 5 ?? 2 x y Q = {s,u,v,x,y} Vertices to relax S = {} Vertices with shortest path value Brian Williams, Spring 03 15 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 ?? 10 9 2 3 4 6 s 0 7 5 ?? 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Brian Williams, Spring 03 16 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 ? 10 9 0 2 3 4 6 s 7 5 ?? 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Shortest path edge  [v] = arrows Brian Williams, Spring 03 17 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 ? 10 9 2 3 4 6 s 0 7 5 5 ? 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Shortest path edge  [v] = arrows Brian Williams, Spring 03 18 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 ? 10 9 0 2 3 4 6 s 7 5 5 ? 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Shortest path edge  [v] = arrows Brian Williams, Spring 03 19 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 8 14 10 9 2 3 4 6 s 0 7 5 5 7 2 x y Q = {y,u,v} Vertices to relax S = {s, x} Vertices with shortest path value Shortest path edge  [v] = arrows Brian Williams, Spring 03 20 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 8 14 10 9 0 2 3 4 6 s 7 5 57 2 x y Q = {y,u,v} Vertices to relax S = {s, x} Vertices with shortest path value Shortest path edge  [v] = arrows Brian Williams, Spring 03 21 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 8 13 10 9 2 3 4 6 s 0 7 5 57 2 x y Q = {u,v} Vertices to relax S = {s, x, y} Vertices with shortest path value Shortest path edge  [v] = arrows Brian Williams, Spring 03 22 89 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 9 0 2 3 4 6 s 7 5 57 2 x y Q = {v} Vertices to relax S = {s, x, y, u} Vertices with shortest path value Shortest path edge  [v] = arrows Brian Williams, Spring 03 23 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 89 10 9 2 3 4 6 s 0 7 5 57 2 x y Q = {} Vertices to relax S = {s, x, y, u, v} Vertices with shortest path value Shortest path edge  [v] = arrows Brian Williams, Spring 03 24 26 25 DIJKSTRA(G,w,s) 1. Initialize-Single-Source(G, s) 2. S 8 ? 3. Q 8 V[G] 4. while Q ?? 5. do u 8Extract-Min(Q) 6. S 8S ? {u} 7. for each vertex v ? Adj[u] 8. do Relax(u, v, w) Repeatedly select minimum cost node and relax out arcs O(V) O(V) * O(V) O(E) = O(V 2 +E) w fib heap = O(VlgV+E) Outline ? planning ? Shortest Paths – ? – ? ? ? ? ? ? Dijkstra’s Algorithm or O(lg V) Creating road maps for path Exploring roadmaps: Single Source Dijkstra;s algorithm Informed search Uniform cost search Greedy search A* search Beam search Hill climbing Avoiding adversaries – (Next Lecture) Brian Williams, Spring 03 Brian Williams, Spring 03 Informed Search Extend search tree nodes to include path length g C 0 g = 8 S 2 3 G A 2 B 5 A 2 24 D 6 D C 4 6 D G 10 S 5 1 5 9 CG8 9 CG8 B Problem: Find the path to the goal G with the shortest path length g. Brian Williams, Spring 03 27 Classes of Search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Best-first Uniform-cost Using path “length” as a measure, (informed) Greedy finds “shortest” path. A* Brian Williams, Spring 03 28 Uniform cost search spreads evenly from start xx A B goal start Does uniform cost search find the shortest path? Brian Williams, Spring 03 29 Uniform Cost edge cost path length C 0 2 S 3 G A 2 24 D S 5 1 5 B Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 30 Uniform Cost edge cost path length C 0 2 S 3 G A 2 A 2 B 5 24 D S 5 1 5 B Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 31 Uniform Cost edge cost path length C 0 2 S 3 G A 2 A 2 B 5 24 D 6 DC4 S 5 1 5 B Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 32 Uniform Cost edge cost path length C 0 2 S 3 G A 2 A 2 B 5 24 D 6 DC4 S 5 1 5 B Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 33 Uniform Cost edge cost path length C 0 2 S 3 G A 2 A 2 B 5 24 D 6 D C 46D G 10 S 5 1 5 B Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 34 Uniform Cost edge cost path length C 0 2 S 3 G A 2 A 2 B 5 24 D 6 D C 4 6 D G 10 S 5 1 5 B 9 C G 8 Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 35 Uniform Cost edge cost path length C 0 2 S 3 G A 2 A 2 B 5 24 D 6 D C 4 6 D G 10 S 5 1 5 B 9 CG8 9 CG8 Expands nodes already visited Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 36 Uniform Cost edge cost path length C 0 2 S 3 G A 2 A 2 B 5 24 D 6 D C 4 6 D G 10 S 5 G 8 1 5 B 9 CG8 9 C Expands nodes already visited Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 37 Uniform Cost edge cost path length C 0 2 S 3 G A 2 A 2 B 5 24 D 6 D C 4 6 D G 10 S 5 1 5 B 9 CG8 9 CG8 Expands nodes already visited Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 38 Why Expand a Vertex More Than Once? edge cost path length 0 S A 1 A 2 D 4 2 1 D G S 4 ? The shortest path from S to G is (G D A S). ? D is reached first using path (D S). Suppose we expanded only the first path to visit each vertex X? Brian Williams, Spring 03 39 Why Expand a Vertex More Than Once? edge cost path length 0 S A 1 A 2 D 5 2 1 D G S 4 3 D ? The shortest path from S to G is (G D A S). ? D is reached first using path (D S). ? This prevents path (D A S) Suppose we expanded only the from being expanded. first path to visit each vertex X? Brian Williams, Spring 03 40 Why Expand a Vertex More Than Once? edge cost path length 0 S A 1 A 2 D 5 2 1 D G S 4 3 D G 10 ? The shortest path from S to G is (G D A S). ? D is reached first using path (D S). ? This prevents path (D A S) Suppose we expanded only the from being expanded. first path to visit each vertex X? Brian Williams, Spring 03 41 Why Expand a Vertex More Than Once? edge cost path length 0 S A 1 A 2 D 5 2 1 D G S 4 3 DG10 ? The shortest path from S to G is (G D A S). ? D is reached first using path (D S). ? This prevents path (D A S) Suppose we expanded only the from being expanded. first path to visit each vertex X? ? The suboptimal path (G D S) is returned. Brian Williams, Spring 03 42 Uniform Cost Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. Let g be the path length from S to N. 1. Initialize Q with partial path (S) as only entry; set Visited = ( ) 2. If Q is empty, fail. Else, pick partial path N from Q with best g 3. If head(N) = G, return N (we’ve reached the goal!) 4. (Otherwise) Remove N from Q 5. Find all children of head(N) not in Visited and create all the one-step extensions of N to each child. 6. Add to Q all the extended paths; 7. Add children of head(N) to Visited Brian Williams, Spring 03 438. Go to step 2. Implementing the Search Strategies Depth-first: Pick first element of Q Uses visited list Add path extensions to front of Q Breadth-first: Pick first element of Q Uses visited list Add path extensions to end of Q Uniform-cost: Pick first element of Q No visited list Add path extensions to Q in order of increasing path length g. Brian Williams, Spring 03 44 Uniform Cost using BFS Pick first element of Q; Insert path extensions, sorted by g. Q 1 (0 S) 2 (2 A S) (5 B S) 3 4 5 6 7 C S B G A D 2 5 4 2 3 2 5 1 1 Here we: ? Insert on queue in order of g. ? Remove first element of queue. Brian Williams, Spring 03 Uniform Cost using BFS Pick first element of Q; Insert path extensions, sorted by g. Q 1 (0 S) 2 (2 A S) (5 B S) 3 (4 C A S) (5 B S) (6 D A S) 4 5 6 7 C S B G A D 2 5 4 2 3 2 5 1 1 2 Here we: ? Insert on queue in order of g. ? Remove first element of queue. Brian Williams, Spring 03 45 46 Uniform Cost using BFS Pick first element of Q; Insert path extensions, sorted by g. Q 1 (0 S) 2 (2 A S) (5 B S) 3 (4 C A S) (5 B S) (6 D A S) 4 (5 B S) (6 D A S) 5 6 7 C S B G A D 2 5 4 2 3 2 5 1 1 2 3 Here we: ? Insert on queue in order of g. ? Remove first element of queue. Brian Williams, Spring 03 Uniform Cost using BFS Pick first element of Q; Insert path extensions, sorted by g. 3 C Q 7 2 2 1 (0 S) 3 G A 2 5,62 (2 A S) (5 B S) 24 1 D 3 (4 C A S) (5 B S) (6 D A S) S 5 1 4 (6 D B S) (6 D A S) (10 G B S) (5 B S) (6 D A S) 5 B 5 4 6 (6 D A S) (8 G D B S) (9 C D B S) (10 G B S) (8 G D A S) (8 G D B S) (9 C D A S) (9 C D B S) 7 (10 G B S) Brian Williams, Spring 03 48 47 49 Can we stop as soon as the goal is enqueued? ? Other paths to the goal that are shorter may not yet be enqueued. ? Only when a path is pulled off the Q are we guaranteed that no shorter path will be added. ? This assumes all edges are positive. (6 D B S) (6 D A S) (10 G B S)5 (8 G D A S) (8 G D B S) (9 C D A S) (9 C D B S) (10 G B S) 7 (6 D A S)(8 G D B S) (9 C D B S) (10 G B S)6 Q 4 3 2 1 (5 B S) (6 D A S) (4 C A S) (5 B S) (6 D A S) (2 A S) (5 B S) (0 S) 50 Implementing the Search Strategies Depth-first: Add path extensions to front of Q Breadth-first: Add path extensions to end of Q Uniform-cost: Uses visited list Uses visited list No visited list Best-first: (generalizes uniform-cost) Pick first element of Q Add path extensions in increasing order of any cost function f Pick first element of Q Pick first element of Q Pick first element of Q No visited list Brian Williams, Spring 03 Brian Williams, Spring 03 Add path extensions to Q in increasing order of path length g. 51 Best-first Search Algorithm Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. . 1. Initialize Q with partial path (S) as only entry 2. with best f 3. If head(N) = G, return N (we’ve reached the goal!) 4. (Otherwise) Remove N from Q 5. Find all children of head(N) and create all the one-step extensions of N to each child. 6. Add to Q all the extended paths; 7. Go to step 2. 52 Classes of Search Blind Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Best-first Uniform-cost Using path “length” as a measure, Greedy A* Depth-First Let f be a cost function on N If Q is empty, fail. Else, pick partial path N from Q finds “shortest” path. Brian Williams, Spring 03 Brian Williams, Spring 03 Chicago, Il Uniform cost search spreads evenly from start Rapid City, ND Boston, Ma xx A B goal start Greedy search is directed towards the goal. Uniform cost search explores the direction away from the goal as much as with the goal. Brian Williams, Spring 03 54 Greedy Search Search in an order imposed by a heuristic function, measuring cost to go. Heuristic function h – is a function of the current node n, not the partial path s to n. ? Estimated distance to goal ? Example: straight-line distance in a road network. ? “Goodness” of a node ? Example: elevation ? Foothills, plateaus and ridges are problematic. – h (n,G) – h (n) Brian Williams, Spring 03 53 Greedy Pick first element of Q; Insert path extensions, sorted by h. 1 C Q 1 (10 S) 2 3 4 5 0 2 G A 4 10 D S 1 3 B Heuristic values in red Added paths in blue; heuristic value of head is in front. Order of nodes in blue. Brian Williams, Spring 03 55 Greedy Pick first element of Q; Insert path extensions, sorted by h. 1 C Q 1(10 S) 2 (2 A S) (3 B S) 3 4 5 0 2 G A 4 10 D S 1 3 B Heuristic values in red Added paths in blue; heuristic value of head is in front. Order of nodes in blue. Brian Williams, Spring 03 56 Greedy Pick first element of Q; Insert path extensions, sorted by h. 1 C Q 1(10 S) 2 (2 A S) (3 B S) 3 (1 C A S) (3 B S) (4 D A S) 4 5 0 2 2 G A 4 10 D S 1 3 B Heuristic values in red Added paths in blue; heuristic value of head is in front. Order of nodes in blue. Brian Williams, Spring 03 57 Greedy Pick first element of Q; Insert path extensions, sorted by h. 3 1 C Q 1(10 S) 2 (2 A S) (3 B S) 3 (1 C A S) (3 B S) (4 D A S) 4(3 B S) (4 D A S) 5 0 2 2 G A 4 10 D S 1 3 B Heuristic values in red Added paths in blue; heuristic value of head is in front. Order of nodes in blue. Brian Williams, Spring 03 58 Greedy Pick first element of Q; Insert path extensions, sorted by h. 3 1 C Q 1(10 S) 2 (2 A S) (3 B S) 3 (1 C A S) (3 B S) (4 D A S) 4(3 B S) (4 D A S) 5 (0 G B S) (4 D A S) (4 D B S) 0 2 2 G A 4 10 D S 1 3 B 4 Heuristic values in red Added paths in blue; heuristic value of head is in front. Order of nodes in blue. Brian Williams, Spring 03 59 Greedy Pick first element of Q; Insert path extensions, sorted by h. 1 C Q 1 (10 S) 2 (2 A S) (3 B S) 3 (1 C A S) (3 B S) (4 D A S) 4 (3 B S) (4 D A S) 5 (0 G B S) ( 4 D A S) ) (4 D B S) 2 0 2 3 G A 2 4 10 2 4 D S 5 1 5 B 3 Heuristic values in red Added paths in blue; heuristic value of head is in front. Edge cost in green. Was the shortest path produced? Brian Williams, Spring 03 60 Classes of Search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Best-first Uniform-cost Using path “length” as a measure, Greedy finds “shortest” path. A* Brian Williams, Spring 03 61 Uniform cost search spreads evenly from start xx A B goal start Brian Williams, Spring 03 62 Uniform cost search spreads evenly from the start Greedy goes for the goal, but forgets its past. xx A B goal start A* biases uniform cost towards the goal by using h A* finds an optimal solution ? f = g + h if h never over estimates. ? g = distance from start Then h is called “admissible” Brian Williams, Spring 03 ? h = estimated distance 63 to goal. 64 Simple Optimal Search Algorithm BFS + Admissible Heuristic 1. 2. partial path N from Q 3. If head(N) = G, return N (we’ve reached the goal) 4. (Otherwise) Remove N from Q; 5. Find all the descendants of head(N) and create all the one-step extensions of N to each descendant. 6. Add to Q all the extended paths. 7. Go to step 2. Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. Initialize Q with partial path (S) as only entry; use f to pick “best” Let f = g + h be an admissible heuristic function If Q is empty, fail. Else, Brian Williams, Spring 03 65 In the example, is h an admissible heuristic? C S B G A D 2 5 4 2 3 2 5 1 Heuristic Values of h in Red Edge cost in Green ? A is ok ? B is ok ? C is ok ? D is too big, needs to be ? 2 ? S is too big, can always use 0 for start 10 2 1 0 4 3 A* finds an optimal solution if h never over estimates. Then h is called “admissible” 66 Admissible heuristics for 8 puzzle? 174 53 826 567 48 321 S G What is the heuristic? ? An underestimate of number of moves to the goal. Examples: 1. Number of misplaced tiles (7) 2. (17) Sum of Manhattan distance of each tile to its goal location Brian Williams, Spring 03 Brian Williams, Spring 03 67 A* Incorporates the Dynamic Programming Principle The shortest path from S through X to G = shortest path from S to X + shortest path from X to G. ? Idea: when shortest from S to X is found, ignore other S to X paths. ? first partial path with head node X, this path is the shortest path from S to X. Given the first path to X, we don’t need to extend other paths to X; delete them. S GX + = S G X X shortest shortest shortest 68 Simple Optimal Search Algorithm How do we add dynamic programming? 1. 2. If Q is empty, fail. 3. If head(N) = G, return N (we’ve reached the goal) 4. (Else) Remove N from Q; 5. Find all children of head(N) and create all the one-step extensions of N to each child. 6. Add to Q all the extended paths. 7. Go to step 2. Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. When BFS dequeues the Initialize Q with partial path (S) as only entry; Else, use f to pick the “best” partial path N from Q Let f = g + h be an admissible heuristic function Brian Williams, Spring 03 Brian Williams, Spring 03 69 A* Optimal Search Algorithm 1. set Expanded = ( ) 2. If Q is empty, fail. 3. If head(N) = G, return N (we’ve reached the goal) 4. (Else) Remove N from Q; 5. 6. Find all the children of head(N) (not in Expanded) and create all the one-step extensions of N to each child. 7. Add to Q all the extended paths. 8. Go to step 2. Let Q be a list of partial paths, Let S be the start node and Let G be the Goal node. 70 Q 1 (0 S) 1 Added paths in blue; cost f at head of each path. C S B G A D 2 5 4 2 3 2 5 1 Heuristic Values of g in Red Edge cost in Green 0 2 1 0 1 3 Expanded Pick first element of Q; BFS + Dyn Prog + Admissible Heuristic Initialize Q with partial path (S) as only entry; Else, use f to pick “best” partial path N from Q if head(N) is in Expanded, go to step 2, otherwise add head(N) to Expanded. Let f = g + h be an admissible heuristic function A* (BFS + DynProg + Admissible Heuristic) Insert path extensions, sorted by path length + heuristic. Brian Williams, Spring 03 Brian Williams, Spring 03 A* (BFS + DynProg + Admissible Heuristic) Pick first element of Q; Insert path extensions, sorted by path length + heuristic. Q Expanded 1 (0 S) 2 S 1 C 2 2 3 G A 2 0 1 24 1 D S 5 1 0 3 5 B Heuristic Values of g in Red Edge cost in Green Added paths in blue; cost f at head of each path Brian Williams, Spring 03 71 A* (BFS + DynProg + Admissible Heuristic) Pick first element of Q; Insert path extensions, sorted by path length + heuristic. Q Expanded 1 (0 S) 2 (4 A S) (8 B S) S 3 S A 1 C 2 2 2 3 G A 2 0 1 24 1 D S 5 1 0 3 5 B Heuristic Values of g in Red Edge cost in Green Added paths in blue; cost f at head of each path Brian Williams, Spring 03 72 A* (BFS + DynProg + Admissible Heuristic) Pick first element of Q; Insert path extensions, sorted by path length + heuristic. 3 Q Expanded 1 (0 S) 2 (4 A S) (8 B S) S 3 (5 C A S) (7 D A S) (8 B S) S A 4 S A C 1 C 2 2 2 G A 2 3 0 1 24 1 D S 5 1 0 3 5 B Heuristic Values of g in Red Edge cost in Green Added paths in blue; cost f at head of each path Brian Williams, Spring 03 73 A* (BFS + DynProg + Admissible Heuristic) Pick first element of Q; Insert path extensions, sorted by path length + heuristic. 3 Q Expanded 1 (0 S) 2 (4 A S) (8 B S) S 3 (5 C A S) (7 D A S) (8 B S) S A 4 (7 D A S) (8 B S) S A C 5 S A C D 1 C 2 2 2 3 G A 2 0 4 1 24 1 D S 5 1 0 3 5 B Heuristic Values of g in Red Edge cost in Green Added paths in blue; cost f at head of each path Brian Williams, Spring 03 74 75 (8 G D A S) (8 B S)5 Q 4 3 2 1 (7 D A S) (8 B S) (5 C A S) (7 D A S) (8 B S) (4 A S) (8 B S) (0 S) 1 2 3 4 5 Added paths in blue; cost f C S B G A D 2 5 4 2 3 2 5 1 0 2 1 0 1 3 Heuristic Values of g in Red Edge cost in Green Expanded S S A S A C S A C D Pick first element of Q; A* (BFS + DynProg + Admissible Heuristic) at head of each path Insert path extensions, sorted by path length + heuristic. Brian Williams, Spring 03 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First Beam (beam width = k) Hill-Climbing (no backup) Hill-Climbing (backup) Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 76 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Beam (beam width = k) Hill-Climbing (no backup) Hill-Climbing (backup) Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) Hill-Climbing (no backup) Hill-Climbing (backup) Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 77 78 79 Classes of Search Blind Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Variants Beam Hill-Climbing (w backup) ID A* Best-first Uniform-cost Finds Greedy “shortest” path. A* 80 C S B G A D Q 4 3 2 1 (2 A S) (3 B S) (10 S) 1 Added paths in blue; heuristic value of head is in front. Heuristic Values A=2 S=10 B=3 G=0 Hill-Climbing Pick first element of Q; Replace Q with extensions (sorted by heuristic value) Depth-First Uses path “length” measure. C=1 D=4 Brian Williams, Spring 03 Brian Williams, Spring 03 Hill-Climbing Pick first element of Q; Replace Q with extensions (sorted by heuristic value) C Q 1(10 S) 2 (2 A S) (3 B S) Removed 3 (1 C A S) (4 D A S) 4 2 G A D S 1 B Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Brian Williams, Spring 03 81 Hill-Climbing Pick first element of Q; Replace Q with extensions (sorted by heuristic value) 3 C Q 1(10 S) 2 (2 A S) (3 B S) 3 (1 C A S) (4 D A S) 4 ( ) 2 G A D S 1 B Heuristic Values Fails to find a path! A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Brian Williams, Spring 03 82 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) Hill-Climbing (no backup) Hill-Climbing (backup) Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) Hill-Climbing (no backup) b*m Hill-Climbing (backup) Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 83 84 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) Hill-Climbing (no backup) b*m b Hill-Climbing (backup) Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) Hill-Climbing (no backup) b*m b No No Hill-Climbing (backup) Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 85 86 Hill-Climbing (with backup) Pick first element of Q; Add path extensions (sorted by heuristic value) to front of Q C Q 1 (10 S) 2 (2 A S) (3 B S) 3 4 5 G A D S 1 B Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Brian Williams, Spring 03 87 Hill-Climbing (with backup) Pick first element of Q; Add path extensions (sorted by heuristic value) to front of Q C Q 1 (10 S) 2 (2 A S) (3 B S) 3 (1 C A S) (4 D A S) (3 B S) 4 All new nodes before old 5 2 G A D S 1 B Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Brian Williams, Spring 03 88 Hill-Climbing (with backup) Pick first element of Q; Add path extensions (sorted by heuristic value) to front of Q 3 C Q 1 (10 S) 2 (2 A S) (3 B S) 3 (1 C A S) (4 D A S) (3 B S) 4 (4 D A S) (3 B S) 5 2 G A D S 1 B Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Brian Williams, Spring 03 89 Hill-Climbing (with backup) Pick first element of Q; Add path extensions (sorted by heuristic value) to front of Q 3 C Q 1 (10 S) 2 (2 A S) (3 B S) 3 (1 C A S) (4 D A S) (3 B S) 4 (4 D A S) (3 B S) 5 (0 G D A S) (1 C A S) (3 B S) 2 G A 4 D S 1 B Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Brian Williams, Spring 03 90 91 Hill-Climbing (with backup) C S B G A D Q 5 4 3 2 1 (0 G D A S) (1 C A S) (3 B S) (4 D A S) (3 B S) (1 C A S) (4 D A S) (3 B S) (2 A S) (3 B S) (10 S) 1 2 3 4 Added paths in blue; heuristic value of head is in front. 5 Heuristic Values A=2 S=10 B=3 G=0 Add path extensions (sorted by heuristic value) to front of Q C=1 D=4 Pick first element of Q; Brian Williams, Spring 03 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) Hill-Climbing (no backup) b*m b No No Hill-Climbing (backup) Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 92 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) Hill-Climbing (no backup) b*m b No No Hill-Climbing (backup) b m b*m Yes No Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 94 Classes of Search Blind Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Variants Beam Hill-Climbing (w backup) ID A* Best-first Uniform-cost Finds Greedy “shortest” path. A* Depth-First Uses path “length” measure. Brian Williams, Spring 03 93 Beam Expand all Q elements; Keep the k best extensions (sorted by heuristic value) C Q 1 (10 S) 2 G A D S 1 B Idea: Incrementally expand the k best paths Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Let k = 2 Brian Williams, Spring 03 95 Beam Expand all Q elements; Keep the k best extensions (sorted by heuristic value) C Q 1 (10 S) 2 (2 A S) (3 B S) G A D S 1 B Idea: Incrementally expand the k best paths Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Let k = 2 Brian Williams, Spring 03 96 Beam Expand all Q elements; Keep the k best extensions (sorted by heuristic value) C Q 1(10 S) 2 (2 A S) (3 B S) 3 (0 G B S) (1 C A S) (4 D A S) (4 D B S) Keep k best 2 G A D S 1 2 B Idea: Incrementally expand the k best paths Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Let k = 2 Brian Williams, Spring 03 97 Beam Expand all Q elements; Keep the k best extensions (sorted by heuristic value) C 3 Q 2 G A 1(10 S) D 2 (2 A S) (3 B S) S (0 G B S) (1 C A S) Keep 1 2 3 B (4 D A S) (4 D B S) k best Idea: Incrementally expand the k best paths Heuristic Values A=2 C=1 S=10 B=3 D=4 G=0 Added paths in blue; heuristic value of head is in front. Let k = 2 Brian Williams, Spring 03 98 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) Hill-Climbing (no backup) b*m b No No Hill-Climbing (backup) b m b*m Yes No Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) k*b Hill-Climbing (no backup) b*m b No No Hill-Climbing (backup) b m b*m Yes No Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 99 100 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) k*b*m k*b Hill-Climbing (no backup) b*m b No No Hill-Climbing (backup) b m b*m Yes No Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 Cost and Performance Searching a tree with branching factor b, solution depth d, and max depth m Search Method Worst Time Worst Space Guaranteed to find a path? Optimal? Depth-First b m b*m Yes No Breadth-First b d+1 b d+1 Yes Yes for unit edge cost Best-First b d+1 b d+1 Yes Yes if uniform cost or A* w admissible heuristic. Beam (beam width = k) k*b*m k*b No No Hill-Climbing (no backup) b*m b No No Hill-Climbing (backup) b m b*m Yes No Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Brian Williams, Spring 03 101 102 103 Outline ? planning ? Path – ? – ? ? ? ? ? ? Creating road maps for path Exploring roadmaps: Shortest Single Source Dijkstra;s algorithm Informed search Uniform cost search Greedy search A* search Beam search Hill climbing Avoiding adversaries – (Next Lecture) Brian Williams, Spring 03