EECS 3401 — AI and Logic Prog. — Lecture 12
Adapted from slides of Yves Lesperance
Vitaliy Batusov
vbatusov@cse.yorku.ca
York University
November 2, 2020
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 1 / 29
Today: Search Algorithms Continued
Required reading: Russell & Norvig Chapters 3.1–3.6, 4.1
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 2 / 29
Depth-Limited Search
Breadth-first search has computational problems (esp. space). Depth-first can run off down a very long (infinite) path. Depth-Limited Search
Perform DFS but only to a pre-specified depth limit L
No node on a path that is more than L steps from the initial state is placed on the Frontier
We truncate the search by looking only at paths of length L or less
Infinite-length paths are no longer a problem!
But will only find a solution if a solution of length ≤ L exists
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 3 / 29
Depth-Limited Search
DLS(Frontier, Successors, Goal?)
If Frontier is empty:
return Failure
Curr := select state from Frontier
If Goal?(Curr):
return Curr
If Depth(Curr) < L:
NewFrontier := (Frontier - {Curr}) + Successors(Curr)
Else:
NewFrontier := Frontier - {Curr}
CutoffOccurred := True
return DLS(NewFrontier, Successors, Goal?)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 4 / 29
Iterative Deepening Search
Take the idea of DLS one step further
Starting at depth limit L = 0, we iteratively increase the depth limit, performing a depth-limited search for each depth limit
Stop if no solution is found or if the depth limited search failed without cutting off any nodes becayse of the depth limit
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 5 / 29
Iterative Deepening Search: Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 6 / 29
Iterative Deepening Search Properties
Completeness
Yes, if solution of length d exists, it will be found when L = d
Time Complexity
At first glance, looks bad because nodes are expanded many times
(d+1)b0+db1+(d−1)b2+...+bd =O(bd)
Root expanded d + 1 times, level 1 nodes expanded d times, etc. Example: b = 4,d = 10
11·40 +10·41 +9·42 +...+2·49 =815555
410 = 1048576
Most nodes lie on the bottom layer
In fact, IDS can be more efficient than breadth-first search: nodes at limit are not expanded. BFS must expand all nodes until it expands a goal node.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 7 / 29
Iterative Deepening Search Properties
Space Complexity
O(bd) — still linear Optimality
Will find shortest-length solution (which is optimal if costs are uniform)
If costs are not uniform, we can use a “cost” bound instead
Only expand paths of cost less than the cost bound
Keep track of the minimum cost unexpanded path in each depth-first iteration, increase the cost bound to this on the next iteration
This can be very expensive. Need as many iterations of the search as there are distinct path costs
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 8 / 29
A Note on Cycle Checking
Idea: Keep track of all states previously expanded during the search When we expand node nk to obtain child c, ensure c is not equal to
any previously expanded state
This is known as cycle checking or multiple path checking
Why can’t we utilize this technique with DFS? — what happens to space complexity?
Thus, only useful with BFS, which is already bad in terms of space complexity
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 9 / 29
Heuristic Search
In uninformed search, we don’t try to evaluate which of the nodes on the frontier are the most promising. We never look-ahead to the goal
Even with uniform-cost search, we always expand the cheapest path regardless of what and where the goal is.
Often, we have some other knowledge about the merit of nodes, e.g., going the wrong direction in Romania
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 10 / 29
Heuristic Search
Different notions of merit
If we are concerned about the cost of the solution, we might want a notion of merit of how costly it is to get to the goal from that search node
If we are concerned about minimizing computation in search, we might want a notion of ease in finding the ggoal from that search node
We will focus on the cost of solution notion of merit
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 11 / 29
Heuristic Search
The idea is to develop a domain-specific heuristic function h(n) h(n) guesses the cost of getting to the goal from node n
There are different ways of guessing this cost in different domains. That is, heuristics are domain-specific
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 12 / 29
Heuristic Search
Convention: If h(n1) < h(n2), this means that we guess that it is cheaper to get to the goal from n1 than from n2
We require that h(n) = 0 for every node n that satisfies the goal.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 13 / 29
Using only h(n) — Greedy best-first search
Use h(n) to rank the nodes on open and always expand the node with lowest h-value
We are greedily trying to achieve a low-cost solution
However, this method ignores the cost of getting to n, so it ca be lead astray exploring nodes that cost a lot to get to but seem to be close to the goal
10
10
S 100
n3 100
h(n1) = 200
n1
h(n3) = 50
n2
10 Goal
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 12
November 2, 2020
14 / 29
A* Search
Take into account the cost of getting to the node as well as our estimate of the cost of getting to the goal from n
Define: f (n) = g (n) + h(n), where
g(n) is the cost of the path to node n
h(n) is the heuristic estimate of the cost of getting to a goal node from node n
Always expand the node with lowest f -value on the frontier The f -value is an estimate of the cost of getting to the goal via this
node (path)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 15 / 29
Conditions on h(n)
We want to analyze the behaviour of the resultant search
Completeness, time, space, optimality?
To obtain such results, we must put some further conditions on the heuristic function h(n) and the search space
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 16 / 29
Conditions on h(n): Admissibility
Assumeasusualthatc(n1 →n2)≥ε>0—thecostofany transition is greater than zero and can’t be arbitrarily small
Let h∗(n) be the cost of an optimal path fron n to a goal node (∞ if there is no path)
A heuristic h is admissible if it satisfies the condition h(n) ≤ h∗(n).
That is, an admissible h always underestimates the true cost, never overestimates.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 17 / 29
Consistency / monotonicity
A heuristic h is monotone (consistent) if it satisfies the trangle inequality for all nodes n1, n2:
h(n1) ≤ c(n1 → n2) + h(n2).
Note that there might be multiple transitions (action) from n1 to n2,
and the inequality must hold for all of them
This is a stronger condition than admissibility. Monotonicity implies admissibility.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 18 / 29
Intuition behind admissibility
h(n) ≤ h∗(n) means that the search won’t miss any promising paths
If it really is cheap to get to a goal via n (i.e., both g(n) and h∗(n) are low), then f (n) = g (n) + h(n) will also be low, and the search won’t ignore n in favour of more expensive options
This can be formalized to show that admissibility implies optimality
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 19 / 29
Intuition behind monotonicity
h(n1) ≤ c(n1 → n2) + h(n2)
This says something similar, but in addition one won’t be “locally”
mislead — see example
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 20 / 29
Example: admissible but non-monotonic
200
h(n1) = 50 n1 200
h(n3) = 50 n3
200
S 100 n2
n4
Goal 100
h(n2) = 200 100
h(n4) = 50
{S} ⇒ {n1[200 + 50 = 250], n2[200 + 100 = 300]} ⇒ {n2[200 + 100 = 300], n3[400 + 50 = 450]} ⇒ {n4[200 + 50 = 250], n3[400 + 50 = 450]} ⇒ {Goal[300 + 0 = 300], n3[400 + 50 = 450]}
We do find the optimal path as the heuristic is still admissible, but we are mislead into
ignoring n2 until after we expand n1
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 21 / 29
Monotonicity implies admissibility
If h(n1) ≤ c(n1 → n2) + h(n2) then h(n) ≤ h∗(n) Proof by induction on the number of steps to a goal node M
(Base case) If n is a goal node, then h(n) = 0 = h∗(n), so
h(n) ≤ h∗(n)
(Induction step) Assume h(nk) ≤ h∗(nk) if number of steps to goal at nk is at most K. Show that the proposition must hold for nodes nk+1 where number of steps to goal is K + 1:
Let nk be the next node along a shortest path from nk+1 to goal Since h is monotone, have h(nk+1) ≤ c(nk+1 → nk ) + h(nk )
By ind. hypothesis, h(nk ) ≤ h∗(nk )
Soh(nk+1)≤c(nk+1 →nk)+h∗(nk)
Thus, h(nk+1) ≤ h∗(nk+1)
If goal is unreachable from a node n, then h∗(n) = ∞ and the result
trivially holds.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 22 / 29
Consequences of monotonicity
1. The f -values of nodes along a path must be non-decreasing I.e., If path is ⟨S → n1 → n2 → . . . → nk ⟩, we claim that
f (ni ) ≤ f (ni+1) Proof:
f (ni ) = c(Start → . . . → ni ) + h(ni ) ≤c(Start→…→ni)+c(ni →ni+1)+h(ni+1) =c(Start→…→ni →ni+1)+h(ni+1)
= g(ni+1) + h(ni+1)
= f (ni+1)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 23 / 29
Consequences of monotonicity
2. If n2 is expanded after n1, then f (n1) ≤ f (n2) Proof:
If n2 was on the frontier when n1 was expanded, then f (n1) ≤ f (n2), because otherwise we would’ve selected n2 to expand
If n2 was added to the frontier after n1’s expansion, then let n be an ancestor of n2 that was present when n1 was being expanded (this could be n1 itself). We have f (n1) ≤ f (n) since A* chose n1 rather than n. Also, since n is along the apth to n2, by the previous property, wehavef(n)≤f(n2). Thus,wegetf(n1)≤f(n2).
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 24 / 29
Consequences of monotonicity
3. When n is expanded, every path with a lower f -value has already been expanded
Assume by contradiction that there exists a path ⟨Start,…,ni−1,ni,ni+1,…,nk⟩withf(nk)
All of these paths myst be explored before any path of cost
> c(Solution)
So eventually Solution, or some equal-cost path to a goal must be expanded
Time and Space Complexity
When h(n) = 0 for all n, h is monotone, and A* becomes uniform-cost search.
It can be shown that when h(n) > 0 for some n, the number of nodes expanded can be no larger than uniform-cost
Thus, same worst-case bounds as uniform-cost apply
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 27 / 29
Consequences of monotonicity
Optimality
Yes, by last property, the first path to a goal node must be optimal
Cycle Checking
If we do cycle checking, it is still optimal. Due to last property, we need to keep only the first path to a node, rejecting all subsequent paths
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 28 / 29
End of Lecture
Next time: Heuristic Search continued
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 12 November 2, 2020 29 / 29