EECS 3401 — AI and Logic Prog. — Lecture 11
Adapted from slides of Yves Lesperance
Vitaliy Batusov
vbatusov@cse.yorku.ca
York University
October 28, 2020
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 1 / 49
Today: Search Algorithms
Required reading: Russell & Norvig Chapters 3.1–3.4
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 2 / 49
Algorithms for Search
Inputs:
an initial state—a specific world state or a set of world states
representing the agent’s knowledge, etc.
a successor function S(x) = a set of states that can be reached
from state x via a single action
a goal test—a function that can be applied to a state and returns
True if the state satisfies the goal condition
a step cost function C(x,a,y) which determines the cost of moving from state x to state y using action a. C(x,a,y)=∞ifadoesnotleadtoy fromx
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 3 / 49
Algorithms for Search
Output:
a sequence of states leading from the initial state to a state satisfying the goal test
The sequence might be
annotated by the name of the actions used; optimal in cost (for some algorithms)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 4 / 49
Algorithms for Search
Obtaining the action sequence:
The set of successors of a state x might arise from different actions, e.g.,
x⇒a⇒y x⇒b⇒z
Successor function S(x) yields a set of states that can be reached from x via any single action
Rather than just return a set of states, we might want to annotate these states by the action used to obtain them:
S(x) = {⟨y, a⟩, ⟨z, b⟩}
y via action a, z via action b S(x) = {⟨y, a⟩, ⟨y, b⟩}
y via action a, also y via action b
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 5 / 49
Tree Search
Tree Search: a way to explore the state space in a tree-like fashion Root = initial state
Frontier = set of unexplored nodes/states (so far)
Branch = action that is possible in current node/state + the resulting node/state
Use the successor state function to expand the current state
TreeSearch(Frontier, Successors, Goal?)
if Frontier is empty
return failure
Current := select state from Frontier
if Goal?(Current)
return Current
NewFrontier := (Frontier – {Current})
+ Successors(Current)
return TreeSearch(NewFrontier, Successors, Goal?)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 6 / 49
Tree search in Prolog
treeS([[State|Path]|_],Soln) :-
Goal(State), reverse([State|Path], Soln).
treeS([[State|Path]|Frontier],Soln) :-
GenSuccessors(State,Path,NewPaths),
merge(NewPaths,Frontier,NewFrontier),
treeS(NewFrontier,Soln).
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 7 / 49
Example: Travelling in Romania
Currently in Arad, need to get to Bucharest by tomorrow to catch a flight
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 8 / 49
Example: Travelling in Romania
Frontier: {Arad}
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 9 / 49
Example: Travelling in Romania
Frontier: {Zerind, Timisoara, Sibiu}
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 10 / 49
Example: Travelling in Romania
Frontier: {Zerind, Timisoara, Arad, Oradea, Fagaras, RimnicuVilcea }
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 11 / 49
Example: Travelling in Romania
Frontier: {Zerind, Timisoara, Arad, Oradea, Sibiu, Bucharest, … }
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 12 / 49
Example: Travelling in Romania
Solution: Arad–Sibiu–Fagaras–Bucharest
Cost: 140+99+211=450
That’s not the only solution
Alternative: Arad–Sibiu–Rimnicu Vilcea–Pitesti–Bucharest Cost: 140+80+97+101=418
Alternative is cheaper!
Way of picking the next node to expand is important
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 13 / 49
Example: Travelling in Romania
It gets worse with cycles
Frontier: {Zerind, Timisoara, Arad, Oradea, Fagaras, RimnicuVilcea} What if we chose to expand Arad instead?
Infinite search tree, no solution
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 14 / 49
Selection Rule
The order of selecting frontier states to expand is of critical importance to whether the solution will be found at all
the cost of the solution (if one is found)
the time and space consumed by search.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 15 / 49
Critical Properties of Search
Completeness — Will the search always find a solution if one exists? Optimality — Will the search always find the cheapest solution?
Time complexity — What is the maximum number of nodes that can be generated or expanded?
Space complexity — What is the maximum number of nodes that have to be stored in memory?
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 16 / 49
Uninformed Search Strategies
Adopt a fixed selection rule
Rule is always the same regardless of the specific search problem
Do not take into account any domain-specific information Popular uninformed search techniques:
Breadth-first Uniform-cost Depth-first Depth-limited Iterative-deepening
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 11
October 28, 2020
17 / 49
Selecting versus Sorting
The problem of selection can be reframed as the problem of sorting Commit to the following selection rule:
1 Arrange frontier elements according to some order
2 Always select the first element
Then, the sorting criteria define the search strategy Will adopt this approach
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 18 / 49
Breadth-First
Place the successors of the current state at the end of the frontier Then, frontier behaves as a First-In-First-Out queue
Example:
Let the states be non-negative integers {0, 1, 2, 3, …} Successor state: S(n) = {n + 1, n + 2}
Initial state: 0
Goal state: 5
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 19 / 49
Example
Let the states be non-negative integers {0, 1, 2, 3, …} Successor state: S(n) = {n + 1, n + 2}
Initial state: 0
Goal state: 5
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 20 / 49
Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 21 / 49
Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 22 / 49
Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 23 / 49
Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 24 / 49
Breadth-First Properties
Time Complexity — number of nodes generated (Let b the maximum number of children per node)
Level 0 (root): 1 Level 1: b
Level 2: b · b = b2 Level 3: b · b2 = b3 …
Level d: bd
Level d + 1: bd+1 − b = b(bd − 1)
when last node in level d is the goal and does not need to be expanded Total: 1+b+b2 +…+bd−1 +bd +b(bd −1)
O(bd+1) — exponential, so only works for small instances
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 25 / 49
Breadth-First Properties
Space Complexity — number of nodes stored
O(bd+1): If the goal node is the last node at level d, all of the successors of the other nodes will be on the frontier when we get to the goal, i.e., b(bd − 1)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 26 / 49
Breadth-First Properties
Optimality
Will find the shortest solution
Least-cost solution? Generally, no. Will if all step costs are equal.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 27 / 49
Breadth-First Properties
Space complexity is a real problem
Let b = 10, and say 1000 nodes can be expanded per second and each node requires 100 bytes of storage.
Depth Nodes Time Memory
1 6 8
1 1 ms 106 18 min 108 31 hrs
100 bytes 111 MB 11 GB
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 11
October 28, 2020
28 / 49
Uniform-Cost Search
Keep the frontier sorted in increasing cost of the path to a node (behaves like a priority queue)
Always expand the least-cost node
Identical to breadth-first if each transition has the same cost Example:
Let the states be non-negative integers {0, 1, 2, 3, …} Successor state: S(n) = {n + 1, n + 2}
Action n+1 has cost 2, action n+2 has cost 3
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 29 / 49
Example
203
12 4556
2334 67787889
34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 30 / 49
Example
203
12 4556
2334 67787889
34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 31 / 49
Example
203
12 4556
2334 67787889
34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 32 / 49
Example
203
12 4556
2334 67787889
34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 33 / 49
Example
203
12 4556
2334 67787889
34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 34 / 49
Uniform-Cost Search
Completeness
Assume each transition has costs ≥ ε > 0 (otherwise can have an infinite path with finite cost)
The previous argument used for breadth-first search holds: the cost of the expanded state must increase monotonically
Algorithm expands nodes in order of increasing path costs
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 35 / 49
Uniform-Cost Search
Time and Space Complexity
C⋆ ⋆ O b ε , where C
is the cost of the optimal solution
Difficulty is that there may be many long paths with cost ≤ C⋆ — uniform cost search must explore them all
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 36 / 49
Uniform-Cost Search
Optimality
If each transition has cost ≥ ε > 0, finds optimal solution
Explores paths in the search space in increasing order of cost. Thus, must find minimum cost path to a goal before finding any higher cost paths.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 37 / 49
Uniform-Cost Search: proof of optimality
Let c(n) be the cost of the path to node n.
1. If node n2 is expanded after node n1, then c(n1) ≤ c(n2).
Proof:
If n2 was already on the frontier when n1 was expanded, then c(n2) ≥ c(n1) (otherwise, n1 wouldn’t have been selected for expansion)
If n2 was added to the frontier as the result of expanding n1, then c(n2) ≥ c(n1) (since the path to n2 extends that to n1)
If n2 is a successor of a node n3 that was already on the frontier or added as the result of expanding n1, then c(n2) > c(n3) and
c(n3) ≥ c(n1) by the previous arguments
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 38 / 49
Uniform-Cost Search: proof of optimality
2. When n is expanded, every path with cost strictly less than c(n) has already been expanded.
Proof:
Let ⟨Start,n0,n1,…,nk⟩ be a path with cost less than c(n). Len ni
(0 ≤ i < k) be the last node on this path that has been expanded ni+1 must be on the frontier, also c(ni+1) < c(n) since the cost of
the entire path to nk is less than c(n)
But then uniform-cost would have expanded ni+1 and not n
Thus, every node on this path must already be expanded, i.e., this path has already been expanded.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 39 / 49
Uniform-Cost Search: proof of optimality
2. The first time uniform-cost expands a state, it has found the minimal-cost path to it (it may later find other paths to the same state)
Proof:
No cheaper path exists, else that path would have been expanded before
No cheaper path will be discovered later, as all those paths must be at least as expensive
So, when a goal state is expanded, the path to it must be optimal
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 40 / 49
Depth-First Search
Place the successors of the current state at the front of the frontier Frontier behaves like a stack
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 41 / 49
Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 42 / 49
Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 43 / 49
Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 44 / 49
Example
0 12
2334 34454556
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 45 / 49
Depth-First Properties
Completeness? No
Infinite paths cause incompleteness. Typically come from cycles in the search space.
If we prune paths with duplicate states, we obtain completeness, provided that the search space is finite
Optimality? No
Can find goal along a longer branch
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 46 / 49
Depth-First Properties
Time Complexity
O(bm), where m is the length of the longest path in the state space Why? Worstcaseexpands1+b+b2+...+bm−1+bm =O(bm)
nodes (assuming no cycles)
Very bad if m is much larger than d, but if there are many solution paths, depth-first can be much faster than breadth-first
At each step, frontier nodes are backtrack points
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 47 / 49
Depth-First Properties
Space Complexity
O(b · m) — linear space!
Only explores one path at a time
The frontier only contains the deepest states on the current path along with the backtrack points
Can even reduce to O(m) if we generate siblings one at a time
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 48 / 49
End of Lecture
Next time: Algorithms for Search continued
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 11 October 28, 2020 49 / 49