# Search - Inst.eecs.berkeley.edu

1y ago
3 Views
4.00 MB
46 Pages
Last View : 7m ago
Transcription

CS 188: Artificial IntelligenceSearchInstructors: Stuart Russell and Dawn SongUniversity of California, Berkeley[slides adapted from Dan Klein, Pieter Abbeel]

Today§ Agents that Plan Ahead§ Search Problems§ Uninformed Search Methods§ Depth-First Search§ Breadth-First Search§ Uniform-Cost Search

Planning Agents§ Planning agents decide based on evaluatingfuture action sequences§ Search algorithms typically assume§§§§Known, deterministic transition modelDiscrete states and actionsFully observableAtomic representation§ Usually have a definite goal§ Optimal: Achieve goal at least cost

Move to nearest dot and eat it

Precompute optimal plan, execute it

Search Problems

Search Problems§ A search problem consists of:§§§§§A state space SAn initial state s0Actions A(s) in each stateTransition model Result(s,a)A goal test G(s)N -9E -9§ s has no dots left§ Action cost c(s,a,s’)§ 1 per step; -10 food; -500 win; 500 die; -200 eat ghost§ A solution is an action sequence that reaches a goal state§ An optimal solution has least cost among all solutions

Search Problems Are Models

Example: Traveling in Romania

But then

Example: Traveling in RomaniaOradea7175§ State space:NeamtZerind§ Cities87151§ Initial state:IasiArad140Sibiu11899§ Arad92Fagaras§ Actions:Vaslui80§ Go to adjacent cityRimnicu 1138120Bucharest90Craiova§ Transition model:142211PitestiGiurgiu98UrziceniHirsova86§ Reach adjacent city§ Goal test:§ s Bucharest?Eforie§ Action cost:§ Road distance from s to s’§ Solution?

Models are almost always wrong

State Space Sizes§ World state:§§§§Agent positions: 120Food count: 30Ghost positions: 12Agent facing: NSEW§ How many§ World states?120x(230)x(122)x4§ States for pathing?120§ States for eat-all-dots?120x(230)

State Space Graphs and Search Trees

State Space Graphs§ State space graph: A mathematicalrepresentation of a search problem§ Nodes are (abstracted) world configurations§ Arcs represent transitions (labeled with actions)§ The goal test is a set of goal nodes (maybe only one)§ In a state space graph, each state occurs onlyonce!§ We can rarely build this full graph in memory(it’s too big), but it’s a useful idea

State Space Graphs§ State space graph: A mathematicalrepresentation of a search problemGacb§ Nodes are (abstracted) world configurations§ Arcs represent successors (action results)§ The goal test is a set of goal nodes (maybe only one)edfS§ In a state space graph, each state occurs onlyonce!§ We can rarely build this full graph in memory(it’s too big), but it’s a useful ideahpqTiny state space graph for a tinysearch problemr

State Space Graphs vs. Search TreesState Space GraphGaEach NODE in inthe search tree isan entire PATH inthe state spacegraph.cbedSfhpqrWe construct thetree on demand –and we construct aslittle as possible.Search TreeSedbcaaehpqqcaphrpfqGqrqfcaG

Quiz: State Space Graphs vs. Search TreesConsider this 4-state graph:aGSbHow big is its search tree (from S)?

Quiz: State Space Graphs vs. Search TreesConsider this 4-state graph:How big is its search tree (from S)?saaGSbba bG aGbGG Important: Those who don’t know history are doomed to repeat it!

Quiz: State Space Graphs vs. Search TreesConsider a rectangular grid:How many states within d steps of start?How many states in search tree of depth d?(a)(b)

Tree Search

Search Example: 189992FagarasVaslui80Rimnicu iceniHirsova86Eforie

General Tree Search§ Main variations:§ Which leaf node to expand next§ Whether to check for repeated states§ Data structures for frontier, expanded nodes

Systematic searchfrontierunexploredexpandedreached expanded U frontier1. Frontier separates expanded from unexplored region of state-space graph2. Expanding a frontier node:a. Moves a node from frontier into expandedb. Adds nodes from unexplored into frontier, maintaining property 1

Depth-First Search

Depth-First SearchStrategy: expand adeepest node firstGacbImplementation:Frontier is a LIFO stackedSfhprqSedbcaaehpqqcahrpfqGpqrqfcaG

Search Algorithm Properties

Search Algorithm Properties§§§§Complete: Guaranteed to find a solution if one exists?Optimal: Guaranteed to find the least cost path?Time complexity?Space complexity? § Cartoon of search tree:§ b is the branching factor§ m is the maximum depth§ solutions at various depthsb1 nodeb nodesb2 nodesm tiersbm nodes§ Number of nodes in entire tree?§ 1 b b2 . bm O(bm)

Depth-First Search (DFS) Properties§ What nodes does DFS expand?§ Some left prefix of the tree down to depth m.§ Could process the whole tree!§ If m is finite, takes time O(bm)§ How much space does the frontier take? b1 nodeb nodesb2 nodesm tiers§ Only has siblings on path to root, so O(bm)§ Is it complete?§ m could be infinite§ preventing cycles may help (more later)§ Is it optimal?§ No, it finds the “leftmost” solution, regardlessof depth or costbm nodes

Breadth-First SearchStrategy: expand ashallowest node firstGacbImplementation:Frontier is a FIFO aG

Breadth-First Search (BFS) Properties§ What nodes does BFS expand?§ Processes all nodes above shallowest solution§ Let depth of shallowest solution be ss tiers§ Search takes time O(bs)§ How much space does the frontier take? b1 nodeb nodesb2 nodesbs nodes§ Has roughly the last tier, so O(bs)§ Is it complete?§ s must be finite if a solution exists, so yes!§ Is it optimal?§ If costs are equal (e.g., 1)bm nodes

Quiz: DFS vs BFS

Quiz: DFS vs BFS§ When will BFS outperform DFS?§ When will DFS outperform BFS?[Demo: dfs/bfs maze water (L2D6)]

Example: Maze Water DFS/BFS (part 1)

Example: Maze Water DFS/BFS (part 2)

Iterative Deepening§ Idea: get DFS’s space advantage with BFS’stime / shallow-solution advantages§ Run a DFS with depth limit 1. If no solution § Run a DFS with depth limit 2. If no solution § Run a DFS with depth limit 3. .§ Isn’t that wastefully redundant?§ Generally most work happens in the lowestlevel searched, so not so bad! b

Uniform Cost Search

Uniform Cost Search2g(n) cost from root to nbStrategy: expand lowest g(n)1dS1c83Frontier is a priority queuesorted by g(n)Ga29p152eh 8f21rqS 0Costcontoursb 4ca 6ah 17 r 11e 511p9e3dh 13 r 7pf 8qqq 11 caG 10qfcaGp1q16

Uniform Cost Search (UCS) Properties§ What nodes does UCS expand?§ Expands all nodes with cost less than cheapest solution!§ If that solution costs C* and arcs cost at least e , then the“effective depth” is roughly C*/eC*/e “tiers”C*/e§ Takes time O(b ) (exponential in effective depth)§ How much space does the frontier take?§ Has roughly the last tier, so O(bC*/e)§ Is it complete?§ Assuming C* is finite and e 0, yes!§ Is it optimal?§ Yes! (Proof next lecture via A*)b g 1g 2g 3

Video of Demo Maze with Deep/Shallow Water --- BFS or UCS? (part 1)

Video of Demo Maze with Deep/Shallow Water --- BFS or UCS? (part 2)

Summary§ Assume known, discrete, observable, deterministic, atomic§ Search problems defined by S, s0, A(s), Result(s,a), G(s), c(s,a,s’)§ Search algorithms find action sequences that reach goal states§ Optimal minimum-cost§ Search algorithm properties:§§§§Depth-first: incomplete, suboptimal, space-efficientBreadth-first: complete, (sub)optimal, space-prohibitiveIterative deepening: complete, (sub)optimal, space-efficientUniform-cost: complete, optimal, space-prohibitive

Depth-First Search (DFS) Properties b 1node bnodes b2nodes bmnodes mtiers §What nodes does DFS expand? §Some left prefix of the tree down to depth m. §Could process the whole tree! §If m is finite, takes time O(bm) §How much space does the frontier take? §Only has siblings on path to root, so O(bm) §Is it complete? §mcould be infinite

Related Documents:

Byung-Gon Chun bgchun@cs.berkeley.edu Kamalika Chaudhuri y kamalika@cs.berkeley.edu Hoeteck Wee z hoeteck@cs.berkeley.edu Marco Barreno x barreno@cs.berkeley.edu Christos H. Papadimitriou y christos@cs.berkeley.edu John Kubiatowicz kubitron@cs.berkeley.edu Computer Science Division University of California, Berkeley ABSTRACT

Berkeley Haas is published three times a year by the Haas School of Business, University of California, Berkeley. Address changes: alumni@haas.berkeley.edu Contact: letters@haas.berkeley.edu Berkeley Haas Magazine, UC Berkeley 2001 Addison St., Ste. 240 Berkeley, CA 94704 SUMMER 2020 How does your salary compare to salaries of fellow alums? PAGE 55

sport program teaching & learning basic mental . special olympics speedskating squash. as of may 8/12. module. med. plan a practice. nutrition. design a basic sport program teaching & learning basic mental skills context inst-beg inst-beg inst-beg inst-beg inst-beg inst-beg sports. context

Task Response Time Optimization Using Cost-Based Operation Motion Bassam Tabbara EECS Department University of California at Berkeley Berkeley, CA 94720 1-510-643-5187 tbassam@eecs.berkeley.edu Abdallah Tabbara EECS Department . Our operation motion step itself is also fast; it has a time complexity of O(n) in the number of statements in the

EECS Department, UC Berkeley September 2, 2021 Ma (EECS Department, UC Berkeley) EECS208, Fall 2021 September 2, 20211/25. Relaxing the Sparse Recovery Problem 1 Convex Functions and Convexi cation 2 .

berkeley berkeley lab 15 47 8/11/1994 cl berkeley bldg. 64 25 4/8/1997 gp/cl berkeley lbl 60 60 7/23/1997 berkeley near university 7 21.5 7/1/1999 land fill berkeley san pablo 20 30 03/27/92 cl sw berkeley uclbnl 23 25 12/30/1998 cl berkeley uclbnl 15 16 11/21/91 cl

Gilad Katz Eui Chul Richard Shin Dawn Song University of California, Berkeley University of California, Berkeley University of California, Berkeley giladk@berkeley.edu ricshin@berkeley.edu dawnsong@cs.berkeley.edu Abstract—Feature generation is one of the challenging aspects of

Byung-Gon Chun ‡ bgchun@cs.berkeley.edu Andrey Ermolinskiy ‡ andreye@cs.berkeley.edu Kye Hyun Kim ‡ kyekim@cs.berkeley.edu Scott Shenker ‡ shenker@icsi.berkeley.edu Ion Stoica ‡ istoica@cs.berkeley.edu ABSTRACT The Internet has evolved greatly from its original incarnation. For instance, the vast majority of current Internet usage .