### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Intro CS 3600

GPA 3.81

### View Full Document

## 8

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 3600 at Georgia Institute of Technology - Main Campus taught by Thad Starner in Fall. Since its upload, it has received 8 views. For similar materials see /class/234032/cs-3600-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

## Reviews for Intro

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

PROBLEM SOLVING AND SEARCH CHAPTER 3 Chapter 3 Reminders Assignment 0 due 5pm today Assignment 1 posted due 29 Section 105 will move to 910am starting next week Chapter 3 ltgtltgtltgtltgtltgt Outline Problemsolving agents Problem types Problem formulation Example problems Basic search algorithms Chapter 3 3 Problemsolving agents Restricted form of general agent function SIMPLE PROBLEM SOLVING AGENTpercept returns an action static seq an action sequence initially empty state some description of the current world state goal a goal initially null problem a problem formulation state 9 UPDATE STATEstate percept if seq is empty then goal 9 FORMULATE GOALstate problem 9 FORMULATE PROBLEMstate goal seq 9 S EARCH problem action 9 RECOMMENDATIONseq state seq 9 REMAINDERseq state return action Note this is offline problem solving solution executed eyes closedquot Online problem solving involves acting without complete knowledge Chapter 3 4 Example Romania On holiday in Romania currently in Arad Flight leaves tomorrow from Bucharest Formulate goal be in Bucharest Formulate problem states various cities actions drive between cities Find solution sequence of cities eg Arad Sibiu Fagaras Bucharest Chapter 3 5 Example Romania Neamt Fagaras 99 Dobreta I Eforie Chapter 3 6 Problem types Deterministic fully observable gt singlestate problem Agent knows exactly which state it will be in solution is a sequence Nonobservable gt conformant problem Agent may have no idea where it is solution if any is a sequence Nondeterministic andor partially observable gt contingency problem percepts provide new information about current state solution is a contingent plan or a policy often interleave search execution Unknown state space gt exploration problem online Chapter 3 7 Example vacuum world Singlestate start in 5 Solution 3 5 7 2 4 6 8 Chapter 3 8 Example vacuum world Singlestate start in 5 Solution Wight Suck Conformant start in 12345 6 78 eg Right goes to 24 6 8 Solution 1 3 5 7 Chapter 3 9 Example vacuum world Singlestate start in 5 Solution Wight Suck Conformant start in 12345 6 78 eg Right goes to 24 6 8 Solution Wight Suck Left Suck Contingency start in 5 Murphy s Law Suck can dirty a clean carpet Local sensing dirt location only Solution 3 5 7 Chapter 3 Example vacuum world Singlestate start in 5 Solution Wight Suck Conformant start in 12345 6 78 eg Right goes to 24 6 8 Solution Wight Suck Left Suck Contingency start in 5 Murphy s Law Suck can dirty a clean carpet Local sensing dirt location only Solution Wight if dirt then Suck 1 3 5 7 Chapter 3 Singlestate problem formulation A problem is defined by four items initial state eg at Aradquot successor function 533 set of action state pairs eg SAmd Amd gt Zermd Zermdgt goal test can be explicit eg 1 at Bucharestquot implicit eg NODirtc path cost additive eg sum of distances number of actions executed etc Czc ay is the step cost assumed to be 2 0 A solution is a sequence of actions leading from the initial state to a goal state Chapter 3 12 Selecting a state space Real world is absurdly complex gt state space must be abstracted for problem solving Abstract state set of real states Abstract action complex combination of real actions eg Arad gt Zerindquot represents a complex set of possible routes detours rest stops etc For guaranteed realizability any real state in Aradquot must get to some real state in Zerindquot Abstract solution set of real paths that are solutions in the real world Each abstract action should be easier than the original problem Chapter 3 13 states actions goal test path cost Chapter 3 14 mi integer dirt and robot locations ignore dirt amounts etc actions goal test path cost Chapter 3 15 mi integer dirt and robot locations ignore dirt amounts etc actions Left Right Suck NoOp goal test path cost Chapter 3 Example vacuum world state space graph mi integer dirt and robot locations ignore dirt amounts etc actions Left Right Suck NoOp goal test no dirt path cost Chapter 3 17 mi integer dirt and robot locations ignore dirt amounts etc actions Left Right Suck NoOp goal test no dirt path cost 1 per action 0 for NoOp Chapter 3 18 states actions goal test path cost Example The 8puzzle E E E EE IEI E E E EEE Start State Goal State Chapter 3 19 Example The 8puzzle E E E E E E E E E E E Start State states integer locations of tiles ignore intermediate positions actions goa test path cost Goal State Chapter 3 20 Example The 8puzzle n E E E E E E E E E E E E Start State Goal State MW integer locations of tiles ignore intermediate positions actions move blank left right up down ignore unjamming etc goal test path cost Chapter 3 21 Example The 8puzzle n E E E E E E E E E E E E Start State Goal State MW integer locations of tiles ignore intermediate positions actions move blank left right up down ignore unjamming etc goal test goal state given path cost Chapter 3 22 Example The 8puzzle EE BEE E E EEE EB Start State Goal State MW 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 nPuzzle family is NPhard Chapter 3 23 Example robotic assembly R R A states realvalued coordinates of robot joint angles parts of the object to be assembled actions continuous motions of robot joints goal test complete assembly with no robot included path cost time to execute Chapter 3 24 Tree search algorithms Basic idea offline simulated exploration of state space by generating successors of alreadyexplored states aka expanding states function TREE SEARCHpr0bZem strategy returns a solution or failure initialize the search tree using the initial state of problem loop do if there are no candidates for expansion then return failure choose a leaf node for expansion according to strategy if the node contains a goal state then return the corresponding solution else expand the node and add the resulting nodes to the search tree end Chapter 3 25 Tree search example Q Sibiu 3 Ti isoara3 1 And5 F garasE Oiadea3 f mnicuvncg3 QArad3 590 3 Zerin K 1 aim 123 Chapter 3 26 Tree search example Oijd a 3 mnlcu Vllvg3 red 5 3190113 N 39 Chapter 3 27 Tree search example aired3 EIgoj 39 I 3 JK grad Gladea 1 Chapter 3 28 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 parent children depth path cost 933 States do not have parents children depth or path cost parent action A State E E Node depth 6 g 6 E E E Slaw The EXPAND function creates new nodes filling in the various fields and using the SUCCESSORFN of the problem to create the corresponding states Chapter 3 29 Implementation general tree search function TREE SEARCHproblem fringe returns a solution or failure fringe e INSERTMAKE N0DEINITIAL STATEproblem fringe loop do if fringe is empty then return failure node 9 REMOVE FRONTfringe if GOAL TESTproblem STATEnode then return node fringe H INSERTALLEXPANDnode problem fringe function EXPAND node problem returns a set of nodes successorsethe empty set for each action result in SUCCESSOR FNproblem STATEnode do 8 a new NODE PARENT NODEs 9 node ACTIONs 9 action STATEs 9 result PATH COSTs H PATH COSTnode STEP COSTnode action s DEPTHs e DEPTHnode 1 add s to successors return successors Chapter 3 30 Search strategies A strategy is defined by picking the order of node expansion Strategies are evaluated along the following dimensions completeness does it always find a solution if one exists time complexity number of nodes generatedexpanded space complexity maximum number of nodes in memory optimality does it always find a leastcost solution Time and space complexity are measured in terms of b maximum branching factor of the search tree d depth of the leastcost solution m maximum depth of the state space may be 00 Chapter 3 31 Uninformed search strategies Uninformed strategies use only the information available in the problem definition Breadthfirst search Uniformcost search Depthfirst search Depthlimited search Iterative deepening search Chapter 3 32 Breadth rst search Expand shallowest unexpanded node Implementation fringe is a FIFO queue ie new successors go at end g g g g f 9 Chapter 3 33 Breadth rst search Expand shallowest unexpanded node Implementation fringe is a FIFO queue ie new successors go at end Chapter 3 34 Breadth rst search Expand shallowest unexpanded node Implementation fringe is a FIFO queue ie new successors go at end Chapter 3 35 Breadth rst search Expand shallowest unexpanded node Implementation fringe is a FIFO queue ie new successors go at end 9 9 0 gt 3 6 6 Chapter 3 36 Complete Properties of breadth rst search Chapter 3 Properties of breadth rst search Complete Yes if b is finite Time Chapter 3 38 Properties of breadth rst search Complete Yes if b is finite T7n1e 1 ib4ib24rb34 ibdlibbd 1bd1 Le expin d Space Chapter 3 39 Properties of breadth rst search Complete Yes if b is finite Time 1 b b2 b3 bd bd 1 0de ie exp in d Space 0de keeps every node in memory Optima Chapter 3 40 Properties of breadth rst search Complete Yes if b is finite Time 1 b b2 b3 bd bd 1 0bdll ie exp in d Space 0bdll keeps every node in memory Optimal Yes if cost 1 per step not optimal in general Space is the big problem can easily generate nodes at 100MBsec so 24hrs 8640GB Chapter 3 41 II Uniformcost search Expand leastcost unexpanded node Implementation fringe queue ordered by path cost lowest first Equivalent to breadthfirst if step costs all equal Complete Yes if step cost 2 6 Time of nodes with g 3 cost of optimal solution 0blO l where 0 is the cost of the optimal solution Space of nodes with g 3 cost of optimal solution 0blO l Optimal Yes nodes expanded in increasing order of gn Chapter 3 42 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front 2 QBY KC r r 25 7 lt55 8 gt gt fgt gt J33353QMNWQ Chapter 3 43 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front f r f 1 f 35 5 5 e fgt fgt gt gt ngv vg bwe Chapter 3 44 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front r 5 G3 a gt fgt gt fgt d3d Chapter 3 45 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front r f 9 3 9 r gt QA QD Chapter 3 46 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front e we gt fgt fgt ewmmwmv Chapter 3 47 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front fgt fgt fgt ngDAbwe Chapter 3 48 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front lt55 T9 gt fgt gamma Chapter 3 49 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front fgt fgt Abwev Chapter 3 50 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front 55 T9 C0 Q Chapter 3 51 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front gt gt Abwe Chapter 3 52 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front Chapter 3 53 Depth rst search Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front Chapter 3 54 Complete Properties of depth rst search Chapter 3 55 Properties of depth rst search Complete No fails in infinitedepth spaces spaces with loops Modify to avoid repeated states along path gt complete in finite spaces Time Chapter 3 56 Properties of depth rst search Complete No fails in infinitedepth spaces spaces with loops Modify to avoid repeated states along path gt complete in finite spaces Time 0bm terrible if m is much larger than d but if solutions are dense may be much faster than breadthfirst Space Chapter 3 57 Properties of depth rst search Complete No fails in infinitedepth spaces spaces with loops Modify to avoid repeated states along path gt complete in finite spaces Time 0bm terrible if m is much larger than d but if solutions are dense may be much faster than breadthfirst Space 0bm ie linear space Optimal Chapter 3 58 Properties of depth rst search Complete No fails in infinitedepth spaces spaces with loops Modify to avoid repeated states along path gt complete in finite spaces Time 0bm terrible if m is much larger than d but if solutions are dense may be much faster than breadthfirst Space 0bm ie linear space Optimal No Chapter 3 59 Depthlimited search depthfirst search with depth limit 1 Le nodes at depth l have no successors Recursive implementation function DEPTH LIMITED SEARCHproblem limit returns soInfaiIcutoff RECURSIVE DLSMAKE NODEINITIAL STATEproblem problem limit function RECURSIVE DLSu0de problem limit returns soInfaiIcutoff cuto occurred 9 9 false if GOAL TESTpr0blem STATEu0de then return node else if DEPTHu0de 2 limit then return cuto else for each successor in EXPANDu0depr0blem do resultH RECURSIVE DLSsuccess0r problem limit if result cuto then cuto occurred9true else if result y failure then return result if cuto occurred then return cuto else return failure Chapter 3 6D Iterative deepening search function ITERATIVE DEEPENING SEARCHproblem returns a solution inputs problem a problem for depthlt O to 00 do resulte DEPTH LIMITED SEARCH problem depth if result cutoff then return result end Chapter 3 61 C hapter Limit 1 Q3 Iterative deepening search 1 0 9 r G f A Chapter 3 63 9 9 G gtf r 9D 9 CF Chapter 3 64 Limit 3 gt e r3 rc 9 G W L CD 19 CF CG 35 E G KG 9 9 CF QgtQD QQ 99 523 wrw e9 39 r G ww wag r 9 CF 3 e 55 E9 ffgt fgt QQ Q r4r o9 r CF e rww wag Chapter 3 65 Properties of iterative deepening search Complete Chapter 3 66 Properties of iterative deepening search Complete Yes Time Chapter 3 67 Properties of iterative deepening search Complete Yes Time d 1b0 db1d 1b2 bd 0bd Space Chapter 3 68 Properties of iterative deepening search Complete Yes Time d 1b0 db1d 1b2 bd 0bd Space 0bd Optima Chapter 3 69 Properties of iterative deepening search Complete Yes Time d 1b0 db1d 1b2 bd 0bd Space 0bd Optimal Yes if step cost 1 Can be modified to explore uniformcost tree Numerical comparison for b 10 and d 5 solution at far right leaf NIDS 50 400 3000 20000 100000 123 450 NBFS 10 100 1000 10 000 100000 999 990 1111100 IDS does better because other nodes at depth d are not expanded BFS can be modified to apply goal test when a node is generated Chapter 3 7D Summary of algorithms Criterion Breadth Uniform Depth Depth Iterative First Cost First Limited Deepening Complete Yes Yes No Yes if l 2 d Yes Time bd1 NOW bm bl bd Space bd1 NOW bm bl bd Optimal Yes Yes No No Yes Chapter 3 71 Repeated states Failure to detect repeated states can turn a linear problem into an exponential one Chapter 3 72 Graph search function GRAPH SEARCHpr0bZem fringe returns a solution or failure ClOSGdH an empty set fringe H INSERTMAKE NODEINITIAL STATEproblem fringe loop do if fringe is empty then return failure node 9 REMOVE FRONTfringe if GOAL TESTpr0blem STATEn0de then return node if STATEn0de is not in closed then add STATEn0de to closed fringe H INSERTALLEXPANDn0de problem fringe end Chapter 3 73

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.