### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Res Fellow Post 000 999

UI

GPA 3.91

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Graduate College Post Comp, Etc

This 23 page Class Notes was uploaded by Cathryn Yost DDS on Friday October 23, 2015. The Class Notes belongs to 000 999 at University of Iowa taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/228003/000-999-university-of-iowa in Graduate College Post Comp, Etc at University of Iowa.

## Reviews for Res Fellow Post

### 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: 10/23/15

I b Example Romania Problem On holiday in Romania currently in Arad Flight leaves tomorrow from Bucharest Find a short route to drive to Bucharest Formulate problem 0 states various cities actions drive between cities solution sequence of cities eg Arad Sibiu Fagaras Bucharest Annual lnlalllaanua a P m Arti cial Intelligence Problem Solving and Search Readings Chapter 3 of Russell amp Norvig J Annual lmelllgencerp 159 b b b Problem types Deterministic fully observable gt singlestate problem 1 Agent knows exactly which state it will be in solution is a sequence Nonobservable gt conformantproblem p Agent may have no idea where it is solution ifany is a sequence Nondeterministic andor partially observable gt contingency problem percepts provide new information about current state 1 solution is a tree or policy 1 often interleave search execution Unknown state space gt exploration problem online Annual lnlalllaanua a P was Example Romania 7 J Annual lnlalllaanua a F 359 Example Vacuum World Problem Solving 1 a 2 a geovxiggt gtlgg considering the simpler cases in which the 3 I 4 5 E 6 I b The agent s world environment is representable by a discrete set of states mm 7 Ago 8 0 The agent s actions are representable by a discrete set of Singlestate I operators start in 5 Solution The world is static and deterministic b L J Mrtual lmelltgence 7 p 559 Mrtual lnlelhgence 7 p 559 Example Vacuum World Example Vacuum World r 7 r T 4 3 4 4 an 5 e 5 e do a m it El H mm nil I we 8 E s A Singlestate start in 5 Singlestate start in 5 Solution Right Suck Solution Right Suck Conformant start in Conformant start in 17 2737475767 77 8 17 27374757 67 77 8 eg Right goes to 24 6 8 eg Right goes to L Solution might Suck Left Suck Contingency start in 5 2 4 6 8 L Solution J Mrtual lmelltgence 7 p 559 Mrtual lmelhgence 7 p 759 Singlestate problem formulation Example Vacuum World l A problem is defined by four items 1 initial state eg at Arad 1 successor function Sx set of action state pairs eg SArad Arad gt Zerind Zerind 3 goal test can be explicit eg x at Bucharest implicit eg NoDz rtx I n lulu Iiiu moon 0 path cost additive eg sum of distances number of 7 0 s actions executed etc Usually given as 01 1 y the Singlestate start in 5 step cost from x to y by action a assumed to be 2 0 Solution Right Suck A solution is a sequence of actions leading from the Conformant start in initial state to a goal state 17273747576718 eg Right goes to 24 6 8 L L Solution Right Suck Left Suck Ammal lmelllgencerp was Mltual lmelhgencerp 959 Contingency start in 5 State space graph of vacuum world Selecting a State Space 77 7 1 Real world is absurdly complex a state space must be abstracted for problem solving Abstract state set of real states J Abstract action complex combination of real actions eg Arad gt Zerind represents a complex set of possible routes detours rest stops etc 3 For guaranteed realizability any real state in Arad states must get to some real state in Zerind aCt39onST p Each abstract action should be easier than the goal tesn original problem 3927 M39 39 1 Abstract solution set ofreal paths that are solutions in the real world L Ammal lmelllgencerp was Annual lmelhgencerp was Formulating Problem as a Graph In the graph each node represents a possible state b a node is designated as the initial state b the agent s goal is considered accomplished h each edge represents a state transition caused by specific agent action b transition one or more nodes represent goal states states in which a associated to each edge is the cost of performing that Annual lmelllgencerp was State space graph of vacuum world states integer dirt and robot locations ignore dirt amounts actions Left Right Suck NaOp goal test no dirt path cost 1 per action 0 for NOOp Mllual lnlalllaanua a p was Problem Solving as Search r 7 Search space set of states reachable from an initial state SO via a possibly emptyfiniteinfinite sequence of state transitions To achieve the problem s goal 9 search the space for a possibly optimal sequenc eof transitions starting from S0 and leading to a goal state execute in order the actions associated to each transition in the identified sequence Depending on the features ofthe agent s world the two steps above can be interleaved Annual lmelllgencerp 1559 Search Graph r How do we reach a goal state 7 mmal state goal states There may be several possible ways Or none Factors to consider 1 cost of nding a path 0 cost of traversing a path L Mllual lnlalllaanua a p 1559 Example The 8puzzle Problem Solving as Search 1 Reduce the original problem to a search problem 1 A solution for the search problem is a path initial state goal state I The solution for the original problem is either p the sequence of actions associated with the path or 0 the description ofthe goal state It can be generalized to 15puzzle 24puzzle or n2 i 1puzze for n 2 6 L Annual lmelllgencerp was Mllual lnlelllgencerp was Example The 8puzzle Example The 8puzzle T 77 7 states configurations oftiles G0 from State S to state G nun nan Operators move one tIIe UpDownLeftnght an gt a In HE S G 3 There are 9 362 880 possible states all permutations ofD 1 234 5 6 7 8 0 There are 16 possible states for 15puzzle Not all states are directly reachable from a given state In fact exactly half ofthem are reachable from a given state How can an artificial agent represent the states and the state space for this problem Annual lnlalllaanua a p was Mllual lnlelllgence a A 1959 Formulating the 8puzzle Problem states each represented by a 3 X 3 array of numbers in 0 8 where value 0 is for the empty cell 2 8 3 becomes A 1 6 4 7 0 5 Anlluel lmelllgence e p 2259 L Problem Formulation world states N where the Choose an appropriate data structure to represent the Define each operator as a preconditioneffects pair precondition holds exactly in the states the operator applies to effects describe how a state changes into a b successor state by the application ofthe operator 00 Specify an initial state reached state is a goal state Provide a description ofthe goal used to check if a Mllual lntelllgence e p 2169 Preconditions and Effects 7 Example 0193727R 2 8 3 Op 2 8 3 1 6 4 s 1 6 4 7 0 5 7 5 0 Preconditions AB 2 0 A32 lt A33 Effects A33 lt 0 We have 24 operators in this problem formulation L20 too many Anlluel lmelllgence e p was r Formulating the 8puzzle Problem 1 Operators 24 operators ofthe form Op C d where no 6 1 23 d E L R U D 7 n Opmad movesthe empty space at position no in the direction d 2830 283 164 9164 705 075 Mllual lntelllgence e p 2369 A Better Formulation A Better Formulation Operators 4 operators ofthe form Opd where States eaeh represented by a Pair 1472397139 Where d E L R U7 D n A is a 3 X 3 array ofnumbers in 0 8 m39 isthe position of the empty space 0 in the array Opd moves the empty space in the direction d 2 8 3 2 8 3 1 6 4 04 1 6 4 2 8 7 0 5 0 7 5 becomes 16 432 7 0 Half states are not reachable Preconditions and Effects liCanthis be done j rExample OpL j 1 2 3 1 2 3 an stes 456 ygtp 456 164320p16431 7 8 8 7 Let 7000 be the position ofO in A 1000 award for anyone who can do it Precondltlons co gt 1 A7 07 00 lt A7 0CO 1 Effects AM 00 7 1 e 0 L 7000 lt T0700 1 Amtuai imeiitgencerp 2mg Mnuai inteihgencerp 2769 The Water Jugs Problem Half states are not reachable Let the 8puzzle be represented by111112113a4a5a6a7agag We say 12311 is an inversion if neither 1 nor aj is blank 2 lt j and a gt 1 Get exactly 2 gallons ofwater into the 4g jug The first one has 0 inversions and the second has 1 Claim of inversions modulo two remains the same after each move Annual lmelllgencerp swag Mllual intelligencerp 2959 The Water Jugs Problem Operators The Water Jugs Problem n 7 VS F4 fill jug4 from the pump tates Determined by the amount of water in each jug 7 precond J4 lt 4 effect J41 E4 emptyjug4 on the ground State Representation Two realvalued variables J3 J4 precond J4 gt 0 effect 0 indicating the amount of water in the two jugs with the E43 pour waterfrom jug4 intojug3 until qu3 is full conStraint53 precond J3 lt 3 effect Jg 3 0 S J3 lt 37 0 S J4 lt 4 1423713 J J4737J3 P34 pourwaterfrom jug3 intojug4 untiljug4 is full Initial State Description precond J4 lt 4 effect J41 4 J3 07 J4 0 24714 J Jgi4iJ4 E34 pour waterfrom jug3 intojug4 until qu3 is empty Goal State Description prawn J3 74 lt 4 we J4 J3 J4 J4 2 lt non exhaustive description L J3gt0 J 7 L 7 Annual lnlallluanua a a 3259 Mllual intelligence 7 p al lag RealWorld Search Problems 0 Route Finding computer networks airline travel planning system Travelling Salesman Optimization Problem package delivery automatic drills 9 Layout Problems VLSI layout furniture layout packaging 0 Assembly Sequencing assembly of electric motors 0 Task Scheduling manufacturing timetables Anlluel intelligence e p was The Water Jugs Problem Problem Search Graph Mllual lmellleenee e p 3359 More on Graphs r A graph is a set of notes and edges arcs between them 9 G A graph is directed if an edge can be traversed only in a specified direction When an edge is directed from m to nj it is univocally identified by the pair mlnj 9 m is a parent or predecessor of nj L 0 nj is a child or successor of n 7 Anlluel intelligence e p 3559 r Problem Solution 0 Problems whose solution is a description of how to reach a goal state from the initial state npuzzle routefinding problem assembly sequencing 7 0 Problems whose solution is simply a description of the goal state itself 8queen problem 3 scheduling problems 1 layout problems Mllual lmellleenee e p 3559 From Search Graphs to Search Trees The set of all possible paths ofa graph can be represented as a tree 0 A tree is a directed acyclic graph all of whose nodes have at most one parent A root ofa tree is a node with no parents 9 A leaf is a node with no children 0 The branching factor ofa node is the number of its children Graphs can be turned into trees by duplicating nodes and Lbreaking cyclic paths ifany Annual lnlelllaenee e in 3559 Directed Graphs A path oflength k 2 0 is a sequence 711712 712713 nknk1gt ofk successive edges a X1 07 51 Dgt7 51 D7DlElEl 13 For1 ltjk1 n N is a ancestor of N Nj is a descendant of N A graph is cyclic if it has a path starting from and ending nto the same node Ex A D DE E 14 a Note that a path of length k gt 0 contains k 1 nodes Mltual lnlelllaenee e in 3759 Tree Search Algorithms Basic idea offline simulated exploration of state space by generating successors of alreadyexplored states aka expanding states function TREESEARCHprobem 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 solution else expand the node and add the resulting nodes to the search tree and Annual lnlelllaenee e p was From Graphs to Trees To unravel a graph into a tree choose a root node and trace every path from that node until you reach a leaf node or a node already in that path must remember which nodes have been visited a node may get duplicated several times in the tree 0 the tree has infinite paths only ifthe graph has infinite noncyclic paths Mltual lnlelllaenee e in 3959 Tree search example Tree Search Example r r X L s bmw mlsoago 7 77 4 J g A 1 7 71 L Q madU F g f E7 Q radenr mmwcea Nad lllg g7 1mm 3 Oradea o lt V Ammal lmelltgence 7 p was Mitual intelligence 7 p 6159 Implementation states vs nodes Tree Search Example 77 7 A state is a representation of a physical configuration A node is a data structure constituting part ofa search tree includes parent children depth path cost 91 States do not have parents children depth or path cost pallent action State I Node depth 6 on m lt la F m The EXPAND function creates new nodes filling in the various fields and using the SUCCESSORFN ofthe problem to create Lthe corresponding states Ammal lmelltgencerp was Mitual lmelhgencerp was Uninformed Search Strategies Uninformed strategies use only the information available in the problem definition Breadthfirst search 9 Uniformcost search 1 Depthfirst search DepthIimited search 0 Iterative deepening search L Annual lnlalllaanua a p was Search Strategies A strategy is defined by picking the order ofnode expansion Strategies are evaluated along the following dimensions completeness does it always find a solution ifone exists 1 time complexity number of nodes generatedexpanded space complexity maximum number of nodes in memory optimality does it always find a leastcost solution J Time and space complexity are measured in terms of b maximum branching factor ofthe search tree L 3 d depth of the leastcost solution 9 m maximum depth ofthe state space may be 00 l ual Intelllgencerp was BreadthFirst Search r Expand shallowest unexpanded node Implementation fringe is a FIFO queue ie new successors go at end 7 Annual lnlalllaanua a p was BreadthFirst Search r 7 Expand shallowest unexpanded node Implementation fringe is a FIFO queue ie new successors go at end gt 35 CC L u Mllual lnlalllaanua a p was BreadthFirst Search Expand shallowest unexpanded node Implementation fringe is a FIFO queue ie new successors go at end Q 9 G gt 9 G G BreadthFirst Search Expand shallowest unexpanded node Implementation fringe is a FIFO queue ie new successors go at end L J J Properties of BreadthFirst Search Properties of BreadthFirst Search 7 j rComplete W Complete Yes if b is finite m L J L J Properties of BreadthFirst Search Properties of BreadthFirst Search T 7 V l Complete Yes if b is finite Complete Yes if b is finite M1bb2 193 bd bbdi 1 Obd1 ie M1bb2 193 bdbbdi 1 Obd1 ie exp in d exp in d Space Obd1 keeps every node in memory Space Optimal L JL J Annual lmelllgencerp swag Mltual lntelllgencerp 5359 Properties of BreadthFirst Search Properties of BreadthFirst Search T 7 V 7 Complete Yes if b is finite Complete Yes if b is finite M1bb2 123 bd bbd71 Obd1 ie M1bb2 123 bdbbdi 1 Obd1 ie exp in d exp in d Space Obd1 keeps every node in memory Space Obd1 keeps every node in memory Optimal Yes if cost 1 per step not optimal in general Optimal Yes if cost 1 per step not optimal in general Space It is the big problem can easily generate nodes at Space 10MBsec so 24hrs 860GB L JL J Annual lmelllgencerp 5m Mltual lntelllgencerp 5559 DepthFirst Search UniformCost Search Expand deepest unexpanded node Expand leastcost unexpanded node Implementation fringe LIFO queue ie put successors at Implementation fringe queue ordered by path cost front Equivalent to breadthfirst if step costs all equal gt Complete Yes if step cost 2 e Time of nodes with g 3 cost of optimal solution BY OblC I where 0 is the cost of the optimal solution gt Space of nodes with g 3 cost of optimal solution 0bIC6l D3 Optimal Yes nodes expanded in increasing order ofgn L JL J Annual Imelligenceip 5559 Mltual Intelligencerp 5759 DepthFirst Search DepthFirst Search Expand deepest unexpanded node Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at Implementation fringe LIFO queue ie put successors at front front r r f e a c 9 xgtxgtxgtrgt 3J JL J Annual Imelligenceip auras Mltual Intelligencerp 5959 DepthFirst Search DepthFirst Search Expand deepest unexpanded node Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at Implementation fringe LIFO queue ie put successors at front front DepthFirst Search DepthFirst Search 7 7 r 7 Expand deepest unexpanded node Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at Implementation fringe LIFO queue ie put successors at front front DepthFirst Search DepthFirst Search Expand deepest unexpanded node Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at Implementation fringe LIFO queue ie put successors at front front r 5 9 flgt gt good DepthFirst Search DepthFirst Search r 7 r 7 Expand deepest unexpanded node Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at Implementation fringe LIFO queue ie put successors at front front Properties of depth rst search DepthFirst Search l7 l l Complete Expand deepest unexpanded node Implementation fringe LIFO queue ie put successors at front Ammal lmelllgencerp was Mllual lmelllgencerp 5959 Propertles of depth rst search Propertles of depth rst search Complete No fails in infinitedepth spaces spaces with j rComplete No fails in infinitedepth spaces spaces with loops Modify to avoid repeated states along path loops Modify to avoid repeated states along path a complete in finite spaces complete in finite spaces MW 0bm terrible ifm is much larger than d but if M solutions are dense may be much faster than breadthfirst Space L J Ammal lmelllgencerp 7259 Annual lmelllgencerp 71 m9 Properties of depth rst search Complete No fails in infinitedepth spaces spaces with loops Modify to avoid repeated states along path a complete in finite spaces MW 0bm terrible ifm is much larger than d but if solutions are dense may be much faster than breadthfirst Space 0bm ie linear space Optimal No L l Annual lnlalllaanua a p was L J Properties of depth rst search Complete No fails in infinitedepth spaces spaces with loops Modify to avoid repeated states along path a complete in finite spaces MW 0bm terrible ifm is much larger than d but if solutions are dense may be much faster than breadthfirst Space 0bm ie linear space Optimal Mltual lnlalllaanua a p 7359 Iterative Deepening Search T 7 function IteratiVeeDeepeningeSearch for depth from O to MAXeINT do problem re turn soln result DeptheLimitedesearchproblem depth if result 1 cutoff then return result end for end function Annual lnlalllaanua a p was 7 end function DepthLimited Search depthfirst search with depth limit 1 Le nodes at depth 1 W have no successors function DeptheLimitedesearch problem limit return solnfailcutoff return RecursiveeDLS MakeeNode Initialestate problem end function problem limit function RecursiVeeDLS node problem limit return solnfailcutoff cutoffeoccurred false if Goalestateproblem Statenode then return node else if Depthnode limit then return cutoff else for each successor in Expandnode problem do result RecursiVeeDLSsuccessor problem limit if result cutoff then cutoffeoccurred true else if result 1 fail then return result end for if cutoffeoccurred then return cutoff else return fail Mltual lnlalllaanua a p 7559 Iterative deepening search l 1 Iterative deepening search l 0 7 I may am A Iterative deepening search l 3 Iterative deepening search l 2 r 7 r mingt37 152 756 gt 339 L J L Properties of iterative deepening search Complete Yes j m L 4 Properties of iterative deepening search Properties of iterative deepening search 7 Complete Yes m7 d 1b0 db1 d7 1b2 bd 00 Space Obd Optimal rCompleteW W Properties of iterative deepening search Complete Yes W Time d 1b0 dbl d 71 bd 00 Space Summary of Algorithms Properties of iterative deepening search Complete Yes Criterion Breadth Uniform Depth Depth Iterative Time d 1bO dbl d 7 up t t t bd 0bd First Cost First Limited Deepening Space Obd Complete Yes Yes No Yes if 2 d Yes Optimal Yes if step cost 1 Can be modified to explore Time bd1 bierei bm bl bd uniformcost tree Space W1 bide1 bm bl bd Optimal Yes Yes No No Yes Numerical comparison for b 10 and d 5 solution at far right NDS 50 l 400 3000 20000 100000 123450 NBFS 10 100 1000 10000 100000 999990 1111100 L Ammai lmelllgencerp ma Mitual intelligencerp 5559 Summary Repeated states T 77 7 0 Problem formulation usually requires abstracting away real world details to define a state space that can Failure to detect repeated states can turn a linear problem feasibly be explored into an exponential one 0 Variety of uninformed search strategies A 1 Iterative deepening search uses only linear space and not much more time than other uninformed algorithms B c D Ammai lmelllgencerp ma Mitual intelligencerp ma Example Romania For a given strategy what is the order of nodes to be generated or stored and expanded Mth or without checking duplicated nodes bbbbb Breadthfirst Depthfirst Uniformcost DepthIim ited Iterativedeepening Mnuat ntewgence 7 p 5959

### 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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "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.