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 cscodehelp代写 加微信 cscodehelp

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

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!

8-puzzle: parent, action Romania:

State Node

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

2=d b=b 3=d+1 b3 −b = bd+1−b

𝑏: max. branching factor

𝑑: depth of the shallowest solution 𝑚: max. depth of the state space

Example: Romania

146 101 138

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+ 𝐶∗/𝜖

• Time? # of nodes with 𝑔 ≤ 𝐶 ,𝑂(𝑏 )

where 𝐶∗ is the cost of the optimal solution

• Space? # of nodes with 𝑔 ≤ 𝐶 ,𝑂(𝑏 )

• Optimal? Yes—nodes expanded in increasing order of 𝑔(𝑛)

𝑏: max. branching factor

𝑑: depth of the shallowest solution 𝑚: max. depth of the state space

• 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𝑑𝑑

•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

𝑏: max. branching factor

𝑑: depth of the shallowest solution 𝑚: max. depth of the state space

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

Bucharest 90

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

• 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 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374

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

start node

• 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

f (n) = g(n) + h(n)

Straight-line dist. to Bucharest

A* Search Example

Sibiu 393=140+253

Timisoara 447=118+329

Siibiiu 553=300+253

607=414+193

Zerind 449=75+374

646=280+366

Sibiu Bucharest

591=338+253 450=450+0

413=220+193 Craiova

415=239+176 6677161=7=2129=9121+9+3138+803080

Pitesti 526=366+160 417=317+100

Bucharest Craiova 418=418+0 615=455+160

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

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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com