Informed search algorithms

Informed search algorithms

• CHAPTER 4
• Oliver Schulte
• Summer 2011

Outline

• Best-first search
• A* search
• Heuristics
• Local search algorithms
• Hill-climbing search
• Simulated annealing search
• Local beam search

Environment Type Discussed In this Lecture

• Static Environment

• CMPT 310 - Blind Search

• Fully Observable

• Deterministic

• Sequential

• yes

• yes

• Discrete

• Discrete

• yes

• Planning, heuristic search

• yes

• Control, cybernetics

• no

• no

• Continuous Function Optimization

• Vector Search: Constraint Satisfaction

• no

• yes

Review: Tree search

• A search strategy is defined by picking the order of node expansion
• Which nodes to check first?

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.

Best-first search

• Idea: use an evaluation function f(n) for each node
• estimate of "desirability"
• Expand most desirable unexpanded node
• Implementation:
• Order the nodes 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