CS 188Fall 2019 Exam Prep 1 SolutionsQ1. Search problemsIt is training day for Pacbabies, also known as Hungry Running Maze Games day. Each of k Pacbabies startsin its own assigned start location siin a large maze of size MxN and must return to its own Pacdad who iswaiting patiently but proudly at gi; along the way, the Pacbabies must, between them, eat all the dots in themaze.At each step, all k Pacbabies move one unit to any open adjacent square. The only legal actions are Up, Down,Left, or Right. It is illegal for a Pacbaby to wait in a square, attempt to move into a wall, or attempt to occupythe same square as another Pacbaby. To set a record, the Pacbabies must find an optimal collective solution.(a) Define a minimal state space representation for this problem.The state space is defined by the current locations of k Pacbabies and, for each square, a Boolean variableindicating the presence of food.(b) How large is the state space?(MN)k· 2MN(c) What is the maximum branching factor for this problem? 4k# 8k# 4k2MN# 4k24Each of k Pacbabies has a choice of 4 actions.(d) Let M H(p, q) be the Manhattan distance between positions p and q and F be the set of all positions ofremaining food pellets and pibe the current position of Pacbaby i. Which of the following are admissibleheuristics? hA:Pki=1MH(pi,gi)k hB: max1≤i≤kMH(pi, gi) hC: max1≤i≤k[maxf∈FMH(pi, f)] hD: max1≤i≤k[minf∈FMH(pi, f)] hE: min1≤i≤k[minf∈FMH(pi, f)] hF: minf∈F[max1≤i≤kMH(pi, f)]hAis admissible because the total Pacbaby–Pacdad distance can be reduced by at most k at each timestep.hBis admissible because it will take at least this many teps for the furthest Pacbaby to reach its Pacdad.hCis inadmissible because it looks at the distance from each Pacbaby to its most distant food square; butof course the optimal solution might another Pacbaby going to that square; same problem for hD.hEis admissible because some Pacbaby will have to travel at least this far to eat one piece of food (butit’s not very accurate).hFis inadmissible because it connects each food square to the most distant Pacbaby, which may not bethe one who eats it.1A different heuristic, hG= maxf∈F[min1≤i≤kMH(pi, f)], would be admisible: it connects each foodsquare to its closest Pacbaby and then considers the most difficult square for any Pacbaby to reach.Now suppose that some of the squares are flooded with water. In the flooded squares, it takes two timestepsto travel through the square, rather than one. However, the Pacbabies don’t know which squares are floodedand which aren’t, until they enter them. After a Pacbaby enters a flooded square, its howls of despair instantlyinform all the other Pacbabies of this fact.(e) Define a minimal space of belief states for this problem.The physical states about which the agent is uncertain are configurations of M N wetness bits, of whichthere are 2MN. In general, the space of belief states would be all possible subsets of the physical states,i.e., 22M Nsubsets of the 2MNconfigurations. However, percepts in this world give either no informationabout a location or perfect information, so the reachable belief states are those 3MNbelief states in whicheach square is wet, dry, or unknown. Either answer is OK.(f) How many possible environmental configurations are there in the initial belief state, before the Pacbabiesreceive any wetness percepts?2MN(g) Given the current belief state, how many different belief states can be reached in a single step?# 4k 8k# 4k2MN# 4k24After each of 4kjoint movements of Pacbabies, there are 2kpossible joint percepts, each leading to adistinct belief state.2Q2. Search(a) Rubik’s SearchNote: You do not need to know what a Rubik’s cube is in order to solve this problem.A Rubik’s cube has about 4.3 × 1019possible configurations, but any configuration can be solved in 20moves or less. We pose the problem of solving a Rubik’s cube as a search problem, where the states arethe possible configurations, and there is an edge between two states if we can get from one state to anotherin a single move. Thus, we have 4.3 × 1019states. Each edge has cost 1. Note that the state space graphdoes contain cycles. Since we can make 27 moves from each state, the branching factor is 27. Since anyconfiguration can be solved in 20 moves or less, we have h∗(n) ≤ 20.For each of the following searches, estimate the approximate number of states expanded. Mark the optionthat is closest to the number of states expanded by the search. Assume that the shortest solution for ourstart state takes exactly 20 moves. Note that 2720is much larger than 4.3 × 1019.(i) DFS Tree SearchBest Case: 20 # 4.3 × 1019# 2720# ∞ (never finishes)Worst Case: # 20 # 4.3 × 1019# 2720 ∞ (never finishes)(ii) DFS graph searchBest Case: 20 # 4.3 × 1019# 2720# ∞ (never finishes)Worst Case: # 20 4.3 × 1019# 2720# ∞ (never finishes)(iii) BFS tree searchBest Case: # 20 # 4.3 × 1019 2720# ∞ (never finishes)Worst Case: # 20 # 4.3 × 1019 2720# ∞ (never finishes)(iv) BFS graph searchBest Case: # 20 4.3 × 1019# 2720# ∞ (never finishes)Worst Case: # 20 4.3 × 1019# 2720# ∞ (never finishes)(v) A* tree search with a perfect heuristic, h∗(n), Best Case 20 # 4.3 × 1019# 2720# ∞ (never finishes)(vi) A* tree search with a bad heuristic, h(n) = 20 − h∗(n), Worst Case# 20 # 4.3 × 1019 2720# ∞ (never finishes)(vii) A* graph search with a perfect heuristic, h∗(n), Best Case 20 # 4.3 × 1019# 2720# ∞ (never finishes)(viii) A* graph search with a bad heuristic, h(n) = 20 − h∗(n), Worst Case# 20 4.3 × 1019# 2720# ∞ (never finishes)3(b) Limited A∗Graph SearchConsider a variant of A∗graph search called Limited A∗graph search. It is exactly like the normal algo-rithm, but instead of keeping all of the fringe, at the end of each iteration of the outer loop, the fringe isreduced to just a certain amount of the best paths. I.e. after all children have been inserted, the fringe iscut down to the a certain length. The pseudo-code for normal A∗graph search is reproduced below, theonly modification being an argument W for the limit.1: function A* Graph Search(problem,W )2: fringe ← an empty priority queue3: fringe ← Insert(Make-Node(Initial-State[problem]), fringe)4: closed ← an empty set5: Add Initial-State[problem] to closed6: loop7: if fringe is empty then8: return failure9: end if10: node ← Remove-Front(fringe)11: if