wexInformedSearchandExploration.pptVIP

Informed Search and Exploration Chapter 4 (4.1-4.3) Introduction Ch.3 searches – good building blocks for learning about search But vastly inefficient eg: Can we do better? (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 knowledge Overview Heuristic Search Best-First Search Approach Greedy A* Heuristic Functions Local Search and Optimization Hill-climbing Simulated Annealing Local Beam Genetic Algorithms Informed Searching An informed search strategy uses knowledge beyond the definition of the problem The knowledge is embodied in an evaluation function f(n) 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 best 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) 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 finish 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) Route Finding Route Finding: Greedy Best First Route Finding: Greedy Best First Route Finding: Greedy Best First Route Findi