COMP3620 / 6320 – S1 2022
This lecture will be recorded
Turn off your camera if you do not want to be in the recording
If you cannot see my whole slide, go to View Options -> Zoom Ratio and select Fit to Window
Copyright By PowCoder代写 加微信 powcoder
If you want to ask a question, either:
• Raise your hand and I will open your mic, or • Type the question in the chat box
• Class representatives
– Please nominate yourself by sending a private message on piazza by 2nd
March 2022.
– You are free to nominate yourself whether you are currently on-campus or studying remotely.
• Labs and Tutorials
– Sign-up available on wattle on 5 March 2022. – First tutorial and lab: 15-18 March 2022
Goal-Based Agents: Solving Problems by Searching
Chapter 3, Sections 1-4
Search for Atari Games
Lipovetzky, Nir, , and . “Classical planning with simulators: Results on the atari video games.” In 24th International Joint Conference on Artificial Intelligence. 2015. https://www.youtube.com/watch?v=P-603qPMkSg
Problem solving agents
• Form of goal-based agent that formulates the problem of reaching a goal in its environment, searches for a sequence of actions solving the problem, and executes it.
• Assumptions about the task environment: – fully observable
– deterministic
– single agent
• Offline (or open-loop) problem solving is suitable under those assumptions; the entire sequence solution can be executed “eyes closed.”
• Problem formulation
• Problem formulation examples • Tree search algorithm
• Uninformed search strategies • Informed search strategies
Example: Romania
146 101 138
Urziceni Bucharest
Example: Romania
• On holiday in Romania
– currently in Arad
– flight leaves tomorrow from Bucharest
• Formulate problem:
– initialstate:inArad
– goal:beinBucharest
– states:variouscities
– actions: drive between cities
• Search for a solution:
– sequence of drive actions or equivalently (in this case) sequence of cities, e.g. Arad,
Sibiu, Fagaras, Bucharest
Problem formulation
A problem is defined by four items:
• initial state: e.g., “at Arad”
• successor function: 𝑆(𝑥) = set of action–state pairs
e.g., 𝑆(𝐴𝑟𝑎𝑑) = { 𝐴𝑟𝑎𝑑 → 𝑍𝑒𝑟𝑖𝑛𝑑, 𝑍𝑒𝑟𝑖𝑛𝑑 , 𝐴𝑟𝑎𝑑 → 𝑆𝑖𝑏𝑖𝑢, 𝑆𝑖𝑏𝑖𝑢 , 𝐴𝑟𝑎𝑑 → 𝑇𝑖𝑚𝑖𝑠𝑜𝑎𝑟𝑎, 𝑇𝑖𝑚𝑖𝑠𝑜𝑎𝑟𝑎 }
• goal test, can be
– explicit, e.g., if 𝑥 = “𝑎𝑡𝐵𝑢𝑐h𝑎𝑟𝑒𝑠𝑡”
– implicit, e.g., if 𝐻𝑎𝑠𝐴𝑖𝑟𝑝𝑜𝑟𝑡(𝑥) is True
• path cost (additive)
– e.g., sum of distances, number of actions executed, etc.
– 𝑐(𝑥,𝑎,𝑦) ≥ 0 is the step cost of going from state 𝑥 to state 𝑦 via action 𝑎.
• A solution is a sequence of actions leading from the initial state to a goal state
Example: Vacuum world
• states? dirt presence in each room and robot location (ignore dirt amounts) • actions? 𝐿𝑒𝑓𝑡, 𝑅𝑖𝑔h𝑡, 𝑆𝑢𝑐𝑘, 𝑁𝑜𝑂𝑝
• goal test? no dirt
• path cost? 1 per action (0 for 𝑁𝑜𝑂𝑝)
Example: The 8-puzzle
Start State Goal State
• states? Integer locations of tiles (ignore intermediate positions)
• actions? move blank left, right, up, down (ignore unjamming etc.) • goal test? goal state (given)
• path cost? 1 per move
[Note: optimal solution of 𝑛-Puzzle family is NP-hard]
Selecting a state space
• Real world is absurdly complex
⇒ state space must be abstracted for problem solving
• (Abstract) state = set of real states
• (Abstract) action = complex combination of real actions
– e.g., “𝐴𝑟𝑎𝑑 → 𝑍𝑒𝑟𝑖𝑛𝑑” represents a complex set of possible routes, detours, rest stops, etc.
– For guaranteed realizability, any real state “in Arad” must get to some real state in “in Zerind”.
• (Abstract) solution = set of real paths that are solutions in the real world
• Abstraction should be “easier” than the original problem!
Tree search example
Romania Map:
Explored Frontier Unseen nodes
Tree search algorithm
Basic idea:
• offline, simulated exploration of state space by generating successors of
already-explored nodes (a.k.a. expanding nodes)
Implementation: states vs. nodes
• A state is a (representation of) a physical configuration
• A node is a data structure constituting part of a search tree
– includes: state, parent, children, depth, path cost 𝒈(𝒏) • States do not have parents, children, depth, or path cost!
parent, action
55 4 Node 66 1 88
depth = 6 g=6
Implementation: Expand and Frontier
• The EXPAND function creates new nodes, filling in the various fields and using the SUCCESSORFN of the problem to create the corresponding states.
– Example: SUCCESSORFN(Arad) = { 𝐴𝑟𝑎𝑑 → 𝑍𝑒𝑟𝑖𝑛𝑑, 𝑍𝑒𝑟𝑖𝑛𝑑 , 𝐴𝑟𝑎𝑑 → 𝑆𝑖𝑏𝑖𝑢, 𝑆𝑖𝑏𝑖𝑢 , 𝐴𝑟𝑎𝑑 → 𝑇𝑖𝑚𝑖𝑠𝑜𝑎𝑟𝑎, 𝑇𝑖𝑚𝑖𝑠𝑜𝑎𝑟𝑎 }
A r a d F a g a r a s
O r a d e a A r a d
L u g o j A r a d
O r a d e a
• Frontier implemented as priority queue of nodes ordered according to strategy
Implementation: general tree search
Uniformed Search Strategies
Chapter 3, Section 4
Uninformed search strategies
• A strategy is defined by picking the order of node expansion.
• This is the order used for the priority queue implementing the frontier.
• Uninformed strategies use only the information available in the definition of the problem:
– Breadth-first search
– Uniform-cost search
– Depth-first search
– Depth-limited search
– Iterative deepening search
Breadth-first search
• Strategy: expand shallowest unexpanded node • Implementation:
– frontier is a FIFO queue, i.e., new successors go at end Depth
Evaluating Search Strategies
• Strategies are evaluated along the following dimensions:
– completeness – does it always find a solution if one exists?
– solution optimality – does it always find a least-cost solution? – time complexity – number of nodes generated (or expanded) – space complexity – maximum number of nodes in memory
DEFG Goal HILNO
Time and Space Complexity
• Time and space complexity are measured using big-O notation in terms of – 𝑏: maximum branching factor of the search tree
– 𝑑: depth of the shallowest solution
– 𝑚: maximum depth of the state space (may be ∞)
2DEFG 3HILNO
Properties of breadth-first search
• Complete? Yes (if 𝑏 and 𝑑 are finite) 23𝑑𝑑+1 𝑑+1
• Time? 1+𝑏+𝑏 +𝑏 +…+𝑏 +(𝑏 − 𝑏) = 𝑂(𝑏 ),i.e., exp. in 𝑑 𝑑+1
• Space? 𝑂 𝑏
• if 𝑏 and 𝑑 are finite 𝑏 = 10, 1 million node/sec, 1Kb/node, 𝑑 = 12 would
take 13 days and 1 petabyte of memory.
• Optimal? Yes if cost = 1 per step; not optimal in general
DEFG HIJKLMNO
𝑏: max. branching factor
𝑑: depth of the shallowest solution 𝑚: max. depth of the state space
2=d b=b 3=d+1 b3 −b = bd+1−b
Urziceni Bucharest
146 101 138
Example: Romania
Uniform-cost search
• Strategy: Expand least-cost unexpanded node
• Implementation:
– frontier = queue ordered by path cost (i.e., 𝑔(𝑛)), lowest first
• Equivalent to breadth-first if step costs all equal
• Complete? Yes, if step cost ≥ 𝜖 (for 𝜖 > 0). ∗ 1+ 𝐶∗/𝜖
𝑏: max. branching factor
𝑑: depth of the shallowest solution 𝑚: max. depth of the state space
• Time? # of nodes with 𝑔 ≤ 𝐶 ,𝑂(𝑏 )
where 𝐶∗ is the cost of the optimal solution
• Space? # of nodes with 𝑔 ≤ 𝐶 ,𝑂(𝑏 )
• Optimal? Yes—nodes expanded in increasing order of 𝑔(𝑛)
• Strategy: Expand deepest unexpanded node • Implementation:
– frontier = LIFOqueue,i.e.,putsuccessorsatfront
Depth-first search
L NO HILNO H I L N O
Properties of depth-first search
• Complete? No: fails in infinite-depth spaces, spaces with loops
⇒ complete in finite spaces if we modify to avoid repeated
states along path
• Time? O(bm): terrible if m is much larger than d
⇒ if solutions are dense, maybe much faster than breadth-first
• Space? O(bm), i.e., linear space! (deepest node + ancestors + their siblings)
• Optimal?
…………..
𝑏: max. branching factor
𝑑: depth of the shallowest solution 𝑚: max. depth of the state space
Breadth-first versus depth-first search
• Use breadth-first search when there exists short solutions. • Use depth-first search when there exists many solutions.
Eternity II Puzzle
2 million dollar prize! Few deep solutions
Iterative deepening search
• Combines advantages of breadth-first and depth-first search: – is complete
– returns shallowest solution
– use linear amount of memory
• Performs a series of depth limited depth-first searches
Depth-limited search
• Depth-first search with depth limit l, i.e., nodes at depth l have no successors • Recursive implementation:
• solution: solution found within depth limit • cutoff: no solution within the depth limit • failure: the problem has no solution
Iterative deepening search – Example
Properties of iterative deepening search
• Complete? Yes (if 𝑏 and 𝑑 are finite) 012𝑑𝑑
𝑏: max. branching factor
𝑑: depth of the shallowest solution 𝑚: max. depth of the state space
•Time? 𝑑+1𝑏+𝑑𝑏+𝑑−1𝑏+⋯+𝑏=𝑂(𝑏)
• Space? 𝑂(𝑏𝑑)
• Optimal? Yes, if step cost = 1 (can be modified to explore uniform-cost tree)
Numerical comparison for 𝑏 = 10 and 𝑑 = 5, solution at far-right leaf: Time: IDS doesn’t do much worse than BFS
𝑁(𝐵𝐹𝑆) = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
𝑁(𝐼𝐷𝑆)=6+50+400+3,000+20,000+100,000=123,456
Assumes BFS applies the goal test when a node is generated Space: IDS does much better 𝑁(𝐼𝐷𝑆) = 50, 𝑁(𝐵𝐹𝑆) ≃ 1,000,000
Summary of algorithms
Breadth- Uniform- Depth- Depth- Iterative First Cost First Limited Deepening
Complete? Time Space Optimal?
Yes1 Yes1 No Yes, if 𝑙 ≥ 𝑑 Yes1 𝑑+1 1+𝐶∗/𝜖 𝑚 𝑙 𝑑
Yes No No Yes2
1. Onlyifbanddarefinite.
2. Onlyifallstepcostsareidentical.
𝑏: max. branching factor
𝑑: depth of the shallowest solution 𝑚: max. depth of the state space
• Search Assignment is already out: due by April 1st 6pm
– Submission using gitlab
– Your last push to the gitlab server before 6pm is your submission
• Tutorials and Labs:
– Sign-in is already open
– Tutorial questions are already out (wattle)
Informed search algorithms
Chapter 3, Sections 5–6
Heuristic Function
• Estimates the cost from a given state to the goal
Straight-line dist. to Bucharest
– Estimate for the Travel in Romania example?
➢ Straight Line Distance
Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 100 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374
Bucharest 90
• Evaluation functions (use heuristics) • Greedy search
• A search
Review: Tree search
• The goal test is performed when the node is popped from the frontier,
NOT when it is generated during expansion.
– This is important when looking for optimal solutions.
• A strategy is defined by picking the order of node expansion
Evaluation function
• Evaluation function f (n) = g(n) + h(n)
– estimateof“desirability”,usuallyproblem-specific.
– g(n)=costsofartoreachn
– h(n) = estimated cost from n to the closest goal (heuristic) – f(n)=estimatedtotalcostofpaththroughntogoal
➢ The lower f (n), the more desirable n is • Implementation:
– frontier is a queue sorted in ascending value of f (n)
• Special cases:
– uniform cost search (uninformed): f (n) = g(n)
– greedy search (informed): f (n) = h(n)
start node
– A search (informed): f (n) = g(n) + h(n)
Greedy search
• Evaluation function f (n) = h(n) (entirely heuristic) = estimate of cost from n to the closest goal
• E.g., hSLD(n) = straight-line distance from n to Bucharest
• Greedy search expands the node that appears to be closest to goal
Straight-line dist to Bucharest
Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 100 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374
Lugoj 97 Mehadi 146
Bucharest 90
Greedy Search Example
Straight-line dist. to Bucharest
Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 100 193 Sibiu
Timisoara 329
Zerind 374
Oradea 380
RimnicuVilcea
Bucharest 0
Properties of greedy search
• Complete? No. It can get stuck in loops, e.g., with going from Iasi to Fagaras: Iasi → Neamt → Iasi → Neamt →…
➢ Complete in finite space with repeated-state checking
• Time? O(bm), but a good heuristic can give dramatic improvement
• Space? O(bm) • Optimal? No
99 Fagaras 80
Bucharest 90
𝑏: max. branching factor
𝑑: depth of the shallowest solution 𝑚: max. depth of the state space
• Idea: avoid expanding paths that are already expensive • Evaluation function f (n) = g(n) + h(n)
– g(n) = cost so far to reach n
– h(n) = estimated cost from n to the closest goal
– f (n) = estimated total cost of path through n to goal
• Admissible heuristic:
– ∀n h(n) ≤ h∗(n) where h∗(n) is the true cost from n – Alsorequireh(n)≥0,soh(G)=0foranygoalG
• E.g., hSLD(n) never overestimates the actual road distance
• When h(n) is admissible, f (n) never overestimates the total cost of the optimal path through n to the goal
• Theorem: if h is admissible, A∗ search finds the optimal solution
start node
f (n) = g(n) + h(n)
Straight-line dist. to Bucharest
Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 244 Mehadia 241 646=280+366
413=220+193
Sibiu 591=338+253
Bucharest 450=450+0
615=455+160
A* Search Example
Sibiu 393=140+253
415=239+176 6677161=7=2129=9121+9+3138+803080
Timisoara 447=118+329
Siibiiu 553=300+253
607=414+193
Zerind 449=75+374
526=366+160 417=317+100
Bucharest 418=418+0
234 Oradea 380 Pitesti 100 193
Arad 366=0+366
Optimality of A* (based on admissibility)
• Suppose some suboptimal goal G2 has been generated and is in the frontier. Let n be a frontier node on an optimal path to an optimal goal G1.
Arai start node Pitesti (f=417) n
Bucharest (f=418) G1 G2 Bucharest (f=450)
optimal goal node
suboptimal goal node
f (G2) = g(G2) > g(G1)
since G2 is a goal node, hence, h(G2) = 0
since G2 is suboptimal
since h is admissible: f (n) = g(n) + h(n) ≤ g(n) + h*(n) = g(G1)
• Since f (G2) > f (n), A*will never select G2 for expansion
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com