CS 416 Artificial Intelligence Lecture Lecture 44 Uninformed Uninformed Searches Searches cont cont Chess Kasparov Kasparov won won the the first first chess chess game game Cost of Breadth first Search BFS bb max max branching branching factor factor infinite infinite dd depth depth to to shallowest shallowest goal goal node node m m max max length length of of any any path path infinite infinite Analysis Analysis of of space space and and time time performance performance see see example example on on blackboard blackboard big big Oh Oh O f n O f n is is the the asymptotic asymptotic upper upper bound bound means means that that there there are are positive positive constants constants cc and and nn00 such such that that 00 f n f n cf n cf n for for all all nn nn00 Read Read algorithms algorithms textbook textbook ifif this this is is new new to to you you BFS Space Requirements What s What s important important is is the the path path not not just just the the existence existence of of the the goal goal in in the the tree tree We We must must be be able able to to reconstruct reconstruct the the path path to to the the goal goal We ve We ve got got to to store store the the tree tree for for reconstruction reconstruction Cost of Uniform Search See See example example on on blackboard blackboard Cost of Depth first Search time time complexity complexity O O b bmm length length of of longest longest path path anchors anchors upper upper bound bound space space complexity complexity O O bm bm What s What s an an example example that that highlights highlights difference difference in in performance performance between between BFS BFS and and DFS DFS Iterative Deepening Essentially Essentially DFS DFS with with aa depth depth limit limit Why Why Remember Remember the the space space complexity complexity O bm O bm and and time time complexity complexity O b O bmm of of DFS DFS So So limit limit m m to to be be small small But But what what ifif m m is is smaller smaller than than d d we ll we ll never never find find solution solution So So increment increment depth depth limit limit starting starting from from 00 Cost of Iterative Deepening See See example example on on blackboard blackboard Preferred Preferred uninformed uninformed search search method method when when search search space space is is large large and and depth depth of of solution solution is is not not known known Bidirectional Search Search Search from from goal goal to to start start Search Search from from start start to to goal goal See See example example on on blackboard blackboard Bidirectional Search Do Do you you always always know know the the predecessors predecessors of of aa goal goal state state Do Do you you always always know know the the goal goal state state 8 puzzle 8 puzzle Path Path planning planning Chess Chess Avoid Repeated States How How might might you you create create repeated repeated states states in in 8 puzzle 8 puzzle How How can can you you detect detect repeated repeated states states What What about about preserving preserving lowest lowest cost cost path path among among repeated repeated states states uniform cost uniform cost search search and and BFS BFS w w constant constant step step costs costs Interesting problems Exercise Exercise 3 9 3 9 33 cannibals cannibals and and 33 missionaries missionaries and and aa boat boat that that can can hold hold one one or or two two people people are are on on one one side side of of the the river river Get Get everyone everyone across across the the river river 8 puzzle 8 puzzle and and 15 puzzle 15 puzzle invented invented by by Sam Sam Loyd Loyd in in good good ol ol USA USA in in 1870s 1870s Think Think about about search search space space Rubik s Rubik s cube cube Traveling Traveling Salesman Salesman Problem Problem TSP TSP Chapter 4 Informed Search INFORMED INFORMED Uses Uses problem specific problem specific knowledge knowledge beyond beyond the the definition definition of of the the problem problem itself itself selecting selecting best best lane lane in in traffic traffic playing playing aa sport sport what s what s the the heuristic heuristic or or evaluation evaluation function function www curling ca Best first Search Use Use an an evaluation evaluation function function to to select select node node to to expand expand f n f n evaluation evaluation function function expected expected distance distance to to goal goal select select the the node node that that minimizes minimizes f n f n but but ifif we we knew knew the the best best node node to to explore explore itit wouldn t wouldn t be be search search Let s Let s use use heuristics heuristics for for our our evaluation evaluation functions functions Heuristics A A function function h n h n that that estimates estimates cost cost of of cheapest cheapest path path from from node node nn to to the the goal goal h n h n 00 ifif nn goal goal node node Greedy Best first Search Trust Trust your your heuristic heuristic evaluate evaluate node node that that minimizes minimizes h n h n f n f n h n h n Example Example getting getting from from A A to to B B Explore Explore nodes nodes with with shortest shortest straight straight distance distance to to B B Shortcomings Shortcomings of of heuristic heuristic slow slow route route traffic traffic long long route route dead dead end end A A star Search Combine Combine two two costs costs f n f n g n g n h n h n g n g n cost cost to to get get to to nn h n h n cost cost to to get get to to goal goal from from nn Minimize Minimize f n f n A is Optimal A A can can be be optimal optimal ifif h n h n satisfies satisfies conditions conditions h n h n never never overestimates overestimates cost cost to to reach reach the the goal goal admissible admissible heurisitic heurisitic h n h n is is optimistic optimistic f n f n never never overestimates overestimates cost cost of of aa solution solution through through nn Proof Proof of of optimality optimality A is Optimal We We must must prove prove that that A A will will not not return return aa suboptimal suboptimal goal goal or or aa suboptimal suboptimal path path to to aa goal goal Let Let G G be be aa suboptimal suboptimal goal goal node node f G f G g G g G h G h G h G h G 00 because because G G is is aa goal goal node node f G f G g G g G C C because because G G is is suboptimal suboptimal A is Optimal …