CS 2710 1 Informed Search and Beyond Chapters 3 (3.5-3.7), 4 (4.1)CS 2710 – Informed Search 2 Introduction • Uninformed searches – good building blocks for learning about search • But vastly inefficient • Can we do better?CS 2710 – Informed Search 3 (Quick Partial) Review  Previous algorithms differed in how to select next node for expansion eg:  Breadth First  Fringe nodes sorted old -> new  Depth First  Fringe nodes sorted new -> old  Uniform cost  Fringe nodes sorted by path cost: small -> big  Used little (no) “external” domain knowledgeCS 2710 – Informed Search 4 Overview  Heuristic Search  Best-First Search Approach  Greedy  A*  Heuristic Functions  Local Search and Optimization  Hill-climbing  Simulated AnnealingCS 2710 – Informed Search 5 Informed Searching  An informed search strategy uses knowledge beyond the definition of the problem  The knowledge is embodied in an evaluation function f(n)CS 2710 – Informed Search 6 Best-First Search  An algorithm in which a node is selected for expansion based on an evaluation function f(n)  Fringe nodes ordered by f(n)  Traditionally the node with the lowest evaluation function is selected  Not an accurate name…expanding the best node first would be a straight march to the goal.  Choose the node that appears to be the bestCS 2710 – Informed Search 7 Best-First Search  Remember: Uniform cost search  F(n) = g(n)  Best-first search:  F(n) = h(n)  Later, a-star search:  F(n) = g(n) + h(n)CS 2710 – Informed Search 8 Best-First Search (cont.)  Some BFS algorithms also include the notion of a heuristic function h(n)  h(n) = estimated cost of the cheapest path from node n to a goal node  Best way to include informed knowledge into a search  Examples:  How far is it from point A to point B  How much time will it take to complete the rest of the task at current node to finishCS 2710 – Informed Search 9 Greedy Best-First Search  Expands node estimated to be closest to the goal  f(n) = h(n)  Consider the route finding problem.  Can we use additional information to avoid costly paths that lead nowhere?  Consider using the straight line distance (SLD)CS 2710 – Informed Search 10 Route Finding 374 253 366 329CS 2710 – Informed Search 11 Route Finding: Greedy Best First Arad f(n) = 366CS 2710 – Informed Search 12 Route Finding: Greedy Best First Arad f(n) = 366 Timisoara Sibiu Zerind 374 329 253CS 2710 – Informed Search 13 Route Finding: Greedy Best First Arad f(n) = 366 Timisoara Sibiu Zerind 374 329 253 Arad Rimnicu Vilcea Oradea Fagaras 366 176 380 193CS 2710 – Informed Search 14 Route Finding: Greedy Best First Arad f(n) = 366 Timisoara Sibiu Zerind 374 329 253 Arad Rimnicu Vilcea Oradea Fagaras 366 176 380 193 Bucharest Sibiu 0 253CS 2710 – Informed Search 15 Exercise So is Arad->Sibiu->Fagaras->Bucharest optimal?CS 2710 – Informed Search 16 Greedy Best-First Search  Not optimal.  Not complete.  Could go down a path and never return to try another.  e.g., Iasi  Neamt  Iasi  Neamt  …  Space Complexity  O(bm) – keeps all nodes in memory  Time Complexity  O(bm) (but a good heuristic can give a dramatic improvement)CS 2710 – Informed Search 17 Heuristic Functions • Example: 8-Puzzle – Average solution cost for a random puzzle is 22 moves – Branching factor is about 3 • Empty tile in the middle -> four moves • Empty tile on the edge -> three moves • Empty tile in corner -> two moves – 322 is approx 3.1e10 • Get rid of repeated states • 181,440 distinct statesCS 2710 – Informed Search 18 Heuristic Functions • h1 = number of misplaced tiles • h2 = sum of distances of tiles to goal position.CS 2710 – Informed Search 19 Heuristic Functions  h1 = 7  h2 = 4+0+3+3+1+0+2+1 = 14CS 2710 – Informed Search 20 Admissible Heuristics  A heuristic function h(n) is admissible if it never overestimates the cost to reach the goal from n  Is h1 (#of displaced tiles)  admissible?  Is h2 (Manhattan distance)  admissible?CS 2710 – Informed Search 21 Dominance  If h2(n) ≥ h1(n) for all n (both admissible)  then h2 dominates h1 h2 is better for search  Typical search costs (average number of nodes expanded): d=12 IDS = 3,644,035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes CS 2710 – Informed Search 22 Heuristic Functions  Heuristics are often obtained from relaxed problem  Simplify the original problem by removing constraints  The cost of an optimal solution to a relaxed problem is an admissible heuristic.CS 2710 – Informed Search 23 8-Puzzle  Original  A tile can move from A to B if A is horizontally or vertically adjacent to B and B is blank.  Relaxations  Move from A to B if A is adjacent to B(remove “blank”) h2 by moving each tile in turn to destination  Move from A to B (remove “adjacent” and “blank”) h1 by simply moving each tile directly to destinationCS 2710 – Informed Search 24 How to Obtain Heuristics?  Ask the domain expert (if there is one)  Solve example problems and generalize your experience on which operators are helpful in which situation (particularly important for state space search)  Try to develop sophisticated evaluation functions that measure the closeness of a state to a goal state (particularly important for state space search)  Run your search algorithm with different parameter settings trying to determine which parameter settings of the chosen search algorithm are “good” to solve a particular class of problems.  Write a program that selects “good parameter” settings based on problem characteristics (frequently very difficult) relying on machine learningCS 2710 – Informed Search 25 A* Search  The greedy best-first search does not consider how costly it was to get to a node.  f(n) = h(n)  Idea: avoid expanding paths that are already expensive  Combine g(n), the cost to reach node n, with h(n)  f(n) = g(n) + h(n)  estimated cost of cheapest solution through nCS 2710 – Informed Search 26 A* Search  When h(n) = actual cost to goal  Only nodes in the correct path are expanded  Optimal solution is found  When h(n) < actual cost