# Informed search algorithms

Informed search algorithms CHAPTER 3b CMPT 310 Oliver Schulte Outline Best-first search A* search Heuristics

Environment Type Discussed In this Lecture 3 Fully Observable Static Environment

yes Deterministic yes yes yes Sequential no Discrete

Discrete no no yes Planning, heuristic search

Control, cybernetics CMPT 310 - Blind Search Vector Search: Constraint Satisfaction Continuous Function Optimization

Review: Tree search A search strategy is defined by picking the order of node expansion Which nodes to check first? Heuristic Search Knowledge and Heuristics

Simon and Newell, Human Problem Solving, 1972. Thinking out loud: experts have strong opinions like this looks promising, no way this is going to work. S&N: intelligence comes from heuristics that help find promising states fast. Evaluation Functions Idea: use an evaluation function f(n) for each node.

estimate of "desirability" Expand most desirable unexpanded node. Especially useful with state transition costs. Implementation: Order the paths in frontier in decreasing order of desirability. Special cases:

greedy best-first search A* search Romania with step costs in km Greedy best-first search Evaluation function

f(n) = h(n) (heuristic) = estimate 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 Greedy best-first search example

Greedy best-first search example Greedy best-first search example Greedy best-first search example http://aispace.org/search/ Properties of greedy best-first search Complete? No can get stuck in loops, e.g. as Oradea as goal

Iasi Neamt Iasi Neamt Time? O(bm) = full tree in worst case. But a good heuristic can give dramatic improvement. Space? O(bm) -- keeps all nodes in memory Optimal? No The A* Search Algorithm

A* search Idea: avoid expanding paths that are already expensive. Widely used! Evaluation function f(n) = g(n) + h(n) h(n) = estimated cost from n to goal f(n) = estimated total cost of path through n to goal

g(n) = cost so far to reach n A* search example A* search example A* search example A* search example A* search example

A* search example http://aispace.org/search/ We stop when the node with the lowest f-value is a goal state. Is this guaranteed to find the shortest path? Behaviour of A*

A* expands nodes in order of increasing f value. Let C* be cost of optimal solution. 1. 2. A* expands all nodes n with f(n) < C*. A* expands no nodes n with f(n) > C*.

1. Gradually adds "f- contours" of nodes Contour i has all nodes with f=fi, where fi < fi+1.

Admissible heuristics A heuristic h(n) is admissible if for every node n, h(n) h*(n), where h*(n) is the true cost to reach the goal state from n. An admissible heuristic never overestimates the cost to reach the goal, i.e., it is optimistic. Example: hSLD(n) (straight-line distance never overestimates the actual road distance) Fly heuristic is not admissible: if wall is dark,

then distance from exit is large. Theorem: If h(n) is admissible, A* using TREE- SEARCH finds the optimal solution. Optimality of A* (proof) I Suppose some suboptimal goal path G2 has been generated and is in the frontier. Let n be an unexpanded path in the

frontier such that n is on a shortest path to an optimal goal G. f(G2) = g(G2) since h(G2) = 0 because h is admissible g(G2) > g(G) since G2 is suboptimal, cost of reaching G is less. f(G) = g(G)

since h(G) = 0 f(G2) > f(G) from above Optimality of A* (proof) II Suppose some suboptimal goal path G2 has been generated and is in the frontier. Let n be an unexpanded node in the frontier such that n is on a shortest path to an optimal goal

G. f(G2) > f(G) from above h(n) h*(n) since h is admissible, h* is minimal distance. g(n) + h(n) g(n) + h*(n) = f(G)

f(n) f(G) Hence f(G2) > f(n), and A* will never select G2 for expansion Properties of A* Complete? Yes (unless there are infinitely many nodes with f f(Goal) ) Time? Exponential

Space? Keeps all nodes in memory Optimal? Yes Admissible Heuristics Admissible heuristics E.g., for the 8-puzzle:

h1(n) = number of misplaced tiles h2(n) = total Manhattan distance (i.e., no. of squares from desired location of each tile) h1(S) = ? h2(S) = ?

Admissible heuristics E.g., for the 8-puzzle: h1(n) = number of misplaced tiles h2(n) = total Manhattan distance (i.e., no. of squares from desired location of each tile) h1(S) = ? 8 h2(S) = ? 3+1+2+2+2+3+3+2 = 18

Dominance If h2(n) h1(n) for all n (both admissible) then h2 dominates h1 . h2 is better for search (closer to true cost). 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

Relaxed problems A problem with fewer restrictions on the actions is called a relaxed problem The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem

If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) gives the shortest solution Summary

Heuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cost Greedy best-first search expands lowest h incomplete and not always optimal A search expands lowest g + h

complete and optimal also optimally efficient (up to tie-breaks) Admissible heuristics can be derived from exact solution of relaxed problems

## Recently Viewed Presentations

• Registered Nurses in Primary Care (RNPC) Acknowledgements. This project is supported by the Health Resources and Services Administration (HRSA) of the U.S. Department of Health and Human Services (HHS) under grant number UK1HP31714 and titled "Nurse, Education, Practice, Quality, and...
• Mission Statement. Implement advanced technologies to design a future large commercial airliner (200 passenger minimum) that simultaneously addresses all of the N+2 goals for noise, emissions and fuel burn as set forth by NASA.
• What is Web 2.0? Web 2.0 has been defined many ways. According to Dictionary.com, Web 2.0. is . the internet viewed as a medium in which interactive experience, in the form of blogs, wikis, forums, etc, plays a more important...
• Interwoven (Deep) IntegrationLearning Tools Interoperability (LTI)Remote Plugins (LTI 2.0)Valence - requires programming skill. ... Lorene Flanders and Carol Goodson, University of West Georgia, Ingram Library. ... PowerPoint Presentation
• 7th Lecture, STV4346B: "The economic effects of institutions" Carl Henrik Knutsen, Department of Political Science, UiO 24/11-2008 Some introductory notes Last lecture, we looked at studies that claimed a positive effect on the economy from a complex (of little specified)...
• Academic Sports Medicine Physicians History Founded 1993 Accredited 2003 - 2/2007 recertified through 2012 Program Director since 2002 - Andrew Gregory, MD Assistant Program Director - Gene Hannah, MD Program Coordinator - Sarah Wilder, MSA, ATC Past Fellowship Directors -...
• UHM SUSTAINABLE SAUNDERS SUSTAINABLE SAUNDERS SUSTAINABLE SAUNDERS 3.2 X "The lights are too bright" "My office is too cold!" 3.2 X Conservation Values and Attitudes Conserving Behavior = Feedback Commitment, especially public Increased social reinforcement = Conserving Behavior * -students...
• Nursing Practice Act (ncbon.org) Main components of RN practice: Assessing, planning, and implementing care. Documentation. Hand-off communication (SBAR, shift change, unit/facility transfer) Teaching. Collaboration. Supervising and evaluating. Making sure safe and effective nursing care is practiced, whether by you or...