04 – Problem Solving by Searching:�Informed Search

• Compiled by: Dr. Mohammad Alhawarat
• Department of Computer Science
• Faculty of Information Technology
• Middle East University
• Spring 2023

Agenda

• Summary of Previous Lecture
• What is “Heuristics”
• Best-first search
• Greedy search
• A* search
• Admissible Heuristics

​

​

Last time: Problem-Solving

• Problem solving:
• Goal formulation
• Problem formulation (states, operators)
• Search for solution

​

• Problem formulation:
• Initial state
• Operators
• Goal test
• Path cost

​

• Problem types:
• single state: accessible and deterministic environment
• multiple state: inaccessible and deterministic environment
• contingency: inaccessible and nondeterministic environment
• exploration: unknown state-space

3

Last time: Finding a solution

Function General-Search(problem, strategy) returns a solution, or failure

initialize the search tree using the initial state problem

loop do

if there are no candidates for expansion then return failure

choose a leaf node for expansion according to strategy

if the node contains a goal state then return the corresponding solution

else expand the node and add resulting nodes to the search tree

end

4

Solution: is a sequence of operators that bring you from current state to the goal state

Basic idea: offline, systematic exploration of simulated state-space by generating successors of explored states (expanding)

Strategy: The search strategy is determined by the order in which the nodes are expanded.

A Clean Robust Algorithm

5

Function UniformCost-Search(problem, Queuing-Fn) returns a solution, or failure

open 🡨 make-queue(make-node(initial-state[problem]))

closed 🡨 [empty]

loop do

if open is empty then return failure

currnode 🡨 Remove-Front(open)

if Goal-Test[problem] applied to State(currnode) then return currnode

children 🡨 Expand(currnode, Operators[problem])

while children not empty

​

[… see next slide …]

end

closed 🡨 Insert(closed, currnode)

open 🡨 Sort-By-PathCost(open)

end

A Clean Robust Algorithm

6

[… see previous slide …]

children 🡨 Expand(currnode, Operators[problem])

while children not empty

child 🡨 Remove-Front(children)

if no node in open or closed has child’s state

open 🡨 Queuing-Fn(open, child)

else if there exists node in open that has child’s state

if PathCost(child) < PathCost(node)

open 🡨 Delete-Node(open, node)

open 🡨 Queuing-Fn(open, child)

else if there exists node in closed that has child’s state

if PathCost(child) < PathCost(node)

closed 🡨 Delete-Node(closed, node)

open 🡨 Queuing-Fn(open, child)

end

[… see previous slide …]

Last time: search strategies

Uninformed: Use only information available in the problem formulation

• Breadth-first
• Uniform-cost
• Depth-first
• Depth-limited
• Iterative deepening

​

Informed: ?

7

Evaluation of search strategies

• Search algorithms are commonly evaluated according to the following four criteria:
• Completeness: does it always find a solution if one exists?
• Time complexity: how long does it take as a function of number of nodes?
• Space complexity: how much memory does it require?
• Optimality: does it guarantee the least-cost solution?

​

• Time and space complexity are measured in terms of:
• b – max branching factor of the search tree
• d – depth of the least-cost solution
• m – max depth of the search tree (may be infinity)

​

8

Uninformed vs Informed Search

9

Informed Search

10

Informed Search

11

Last time: uninformed search strategies

Uninformed search:

Use only information available in the problem formulation

• Breadth-first
• Uniform-cost
• Depth-first
• Depth-limited
• Iterative deepening

12

This time: informed search

Informed search:

Use heuristics to guide the search

• Best first
• Greedy Search
• A* Search
• Admissible Heuristics
• Hill-climbing
• Gradient Descent
• Simulated annealing

​

13

Search Heuristics

14

A heuristic is:

• A function that estimates how close a state is to a goal
• Designed for a particular search problem
• Examples: Manhattan distance, Euclidean distance for pathing

Example: Euclidean distance to Bucharest

15

Effect of heuristics

Guide search towards the goal instead of all over the place

16

Uninformed

Informed

Best-first search

• Idea:

use an evaluation function for each node; estimate of “desirability”

• expand most desirable unexpanded node.

​

• Implementation:

QueueingFn = insert successors in decreasing order of desirability

​

• Special cases:

greedy search

A* search

17

Romania with step costs in km

18

374

329

253

Greedy Search

19

Greedy search

• Estimation function:

h(n) = estimate of cost from n to goal (heuristic)

​

• For example:

h_SLD(n) = straight-line distance from n to Bucharest

​

​

• Greedy search expands first the node that appears to be closest to the goal, according to h(n).

20

21

22

23

24

Greedy Search

• Expand the node that seems closest…(order frontier by h)
• What can possibly go wrong?

25

Sibiu-Fagaras-Bucharest =

99+211 = 310

Sibiu-Rimnicu Vilcea-Pitesti-Bucharest =

80+97+101 = 278

1000000

Greedy Search

• Strategy: expand a node that seems closest to a goal state, according to h

​

​

• Problem 1: it chooses a node even if it’s at the end of a very long and winding road

​

​

​

• Problem 2: it takes h literally even if it’s completely wrong

26

…

b

Properties of Greedy Search

• Complete? No – can get stuck in loops

e.g., Iasi > Neamt > Iasi > Neamt > …

Complete in finite space with repeated-state checking.

​

• Time? O(b^m) but a good heuristic can give

dramatic improvement

​

• Space? O(b^m) – keeps all nodes in memory

​

​

• Optimal? No.

27

A* Search

28

A* search

• Idea: avoid expanding paths that are already expensive

​

evaluation function: f(n) = g(n) + h(n) with:

g(n) – cost so far to reach n

h(n) – estimated cost to goal from n

f(n) – estimated total cost of path through n to goal

​

• A* search uses an admissible heuristic, that is,

h(n) ≤ h*(n) where h*(n) is the true cost from n.

For example: h_SLD(n) never overestimates actual road distance.

​

• Theorem: A* search is optimal

29

Combining UCS and Greedy

• Uniform-cost orders by path cost, or backward cost g(n)
• Greedy orders by goal proximity, or forward cost h(n)

​

​

​

​

​

​

​

​

• A* Search orders by the sum: f(n) = g(n) + h(n)

30

S

a

d

b

G

h=5

h=6

h=2

1

8

1

1

2

h=6

h=0

c

h=7

3

e

h=1

1

S

a

b

c

e

d

d

G

G

g = 0 h=6

g = 1 h=5

g = 2 h=6

g = 3 h=7

g = 4 h=2

g = 6 h=0

g = 9 h=1

g = 10 h=2

g = 12 h=0

31

32

33

34

35

36

Optimality of A* (standard proof)

Suppose some suboptimal goal G₂ has been generated and is in the queue. Let n be an unexpanded node on a shortest path to an optimal goal G₁.

37

Optimality of A* (more useful proof)

38

f-contours

39

How do the contours look like when h(n) =0?

Properties of A*

• Complete? Yes, unless infinitely many nodes with f ≤ f(G)

​

​

• Time? Exponential in [(relative error in h) x (length of solution)]

​

​

• Space? Keeps all nodes in memory

​

​

• Optimal? Yes – cannot expand f_i+1 until f_i is finished

40

Is A* Optimal?

• What went wrong?
• Actual bad goal cost < estimated good goal cost
• We need estimates to be less than actual costs!

41

A

G

S

1

3

h = 6

h = 0

5

h = 7

Admissible Heuristics

42

Admissible Heuristics

• A heuristic h is admissible (optimistic) if:

0 ≤ h(n) ≤ h*(n)

where h*(n) is the true cost to a nearest goal

​

• Example:

​

​

​

• Coming up with admissible heuristics is most of what’s involved in using A* in practice.

43

Admissible Heuristics

44

Admissible heuristics

45

Optimality of A* Tree Search

Assume:

• A is an optimal goal node
• B is a suboptimal goal node
• h is admissible

​

​

Claim:

• A will be chosen for exploration (popped off the frontier) before B

46

…

A

B

Optimality of A* Tree Search: Blocking

Proof:

• Imagine B is on the frontier
• Some ancestor n of A is on the frontier, too (Maybe the start state; maybe A itself!)
• Claim: n will be explored before B
1. f(n) is less than or equal to f(A)

47

f(n) = g(n) + h(n) Definition of f-cost

f(n) ≤ g(A) Admissibility of h

…

g(A) = f(A) h = 0 at a goal

A

B

Optimality of A* Tree Search: Blocking

Proof:

• Imagine B is on the frontier
• Some ancestor n of A is on the frontier, too (Maybe the start state; maybe A itself!)
• Claim: n will be explored before B
1. f(n) is less than or equal to f(A)
2. f(A) is less than f(B)

​

48

…

A

B

g(A) < g(B) Suboptimality of B

f(A) < f(B) h = 0 at a goal

Optimality of A* Tree Search: Blocking

Proof:

• Imagine B is on the frontier
• Some ancestor n of A is on the frontier, too (Maybe the start state; maybe A itself!)
• Claim: n will be explored before B
1. f(n) is less than or equal to f(A)
2. f(A) is less than f(B)
3. n is explored before B
• All ancestors of A are explored before B
• A is explored before B
• A* search is optimal

​

​

49

…

A

B

Properties of A*

50

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

…

b

…

b

Uniform-Cost

A*

UCS vs A* Contours

• Uniform-cost expands equally in all “directions”

​

​

​

• A* expands mainly toward the goal, but does hedge its bets to ensure optimality

51

Comparison

52

Greedy

Uniform Cost

A*

A* Search Algorithms

• A* Tree Search
• Same tree search algorithm as before but with a frontier that is a priority queue using priority f(n) = g(n) + h(n)

​

• A* Graph Search
• Same as UCS graph search algorithm but with a frontier that is a priority queue using priority f(n) = g(n) + h(n)

​

53

54

function UNIFORM-COST-SEARCH(problem) returns a solution, or failure

initialize the explored set to be empty

initialize the frontier as a priority queue using g(n) as the priority

add initial state of problem to frontier with priority g(S) = 0� loop do

if the frontier is empty then

return failure� choose a node and remove it from the frontier� if the node contains a goal state then

return the corresponding solution

add the node state to the explored set

for each resulting child from node

if the child state is not already in the frontier or explored set then

add child to the frontier

else if the child is already in the frontier with higher g(n) then

replace that frontier node with child

55

function A-STAR-SEARCH(problem) returns a solution, or failure

initialize the explored set to be empty

initialize the frontier as a priority queue using f(n) = g(n) + h(n) as the priority

add initial state of problem to frontier with priority f(S) = 0 + h(S)� loop do

if the frontier is empty then

return failure� choose a node and remove it from the frontier� if the node contains a goal state then

return the corresponding solution

add the node state to the explored set

for each resulting child from node

if the child state is not already in the frontier or explored set then

add child to the frontier

else if the child is already in the frontier with higher f(n) then

replace that frontier node with child

A* Applications

• Pathing / routing problems
• Resource planning problems
• Robot motion planning
• Language analysis
• Video games
• Machine translation
• Speech recognition
• …

56

Image: maps.google.com

Creating Heuristics

57

Creating Admissible Heuristics

• Most of the work in solving hard search problems optimally is in coming up with admissible heuristics

​

• Often, admissible heuristics are solutions to relaxed problems, where new actions are available

​

​

​

​

​

58

366

Example: 8 Puzzle

• What are the states?
• How many states?
• What are the actions?
• How many actions from the start state?
• What should the step costs be?

59

Start State

Goal State

Actions

8 Puzzle I

• Heuristic: Number of tiles misplaced
• Why is it admissible?
• h(start) =
• This is a relaxed-problem heuristic

60

8

Statistics from Andrew Moore

8 Puzzle II

• What if we had an easier 8-puzzle where any tile could slide any direction at any time, ignoring other tiles?

​

• Total Manhattan distance

​

• Why is it admissible?

​

• h(start) =

​

61

3 + 1 + 2 + … = 18

Combining heuristics

• Dominance: h_a ≥ h_c if

∀n h_a(n) ≥ h_c(n)

• Roughly speaking, larger is better as long as both are admissible
• The zero heuristic is pretty bad (what does A* do with h=0?)
• The exact heuristic is pretty good, but usually too expensive!

​

• What if we have two heuristics, neither dominates the other?
• Form a new heuristic by taking the max of both:

h(n) = max( h_a(n), h_b(n) )

• Max of admissible heuristics is admissible and dominates both!

​

62

Optimality of A* Graph Search

63

Consistency of Heuristics

• Main idea: Estimated heuristic costs ≤ actual costs
• Admissibility:

heuristic cost ≤ actual cost to goal

h(A) ≤ actual cost from A to G

• Consistency:

“heuristic step cost” ≤ actual cost for each step

h(A) – h(C) ≤ cost(A to C)

triangle inequality

h(A) ≤ cost(A to C) + h(C)

• Consequences of consistency:
• The f value along a path never decreases
• A* graph search is optimal

​

64

A

C

G

h=4

h=1

1

h=2

Optimality of A* Graph Search

• Sketch: consider what A* does with a consistent heuristic:

​

• Fact 1: In tree search, A* expands nodes in increasing total f value (f-contours)�
• Fact 2: For every state s, nodes that reach s optimally are explored before nodes that reach s suboptimally

​

• Result: A* graph search is optimal

65

…

f ≤ 3

f ≤ 2

f ≤ 1

Optimality

• Tree search:
• A* is optimal if heuristic is admissible
• UCS is a special case (h = 0)

​

• Graph search:
• A* optimal if heuristic is consistent
• UCS optimal (h = 0 is consistent)

​

• Consistency implies admissibility

​

• In general, most natural admissible heuristics tend to be consistent, especially if from relaxed problems

66

Relaxed Problem

• Admissible heuristics can be derived from the exact solution cost of a relaxed version of the problem.

​

• If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h₁(n) gives the shortest solution.

​

• If the rules are relaxed so that a tile can move to any adjacent square, then h₂(n) gives the shortest solution.

​

​

67

A*: Summary

68

A*: Summary

• A* uses both backward costs and (estimates of) forward costs

​

• A* is optimal with admissible / consistent heuristics

​

• Heuristic design is key: often use relaxed problems

69

Next time

• Iterative Improvement
• Hill-climbing
• Gradient methods
• Simulated annealing
• Genetic Algorithms
• Issues with local search

70

QUESTIONS