CS 188Fall 2019 Exam Prep 2 SolutionsNote: we have provided more material than can be covered in discussion that can be used as practice at home.Q1. Formulation: Holiday ShoppingYou are programming a holiday shopping robot that will drive from store to store in order to buy all the giftson your shopping list. You have a set of N gifts G = {g1, g2, . . . gN} that must be purchased. There are Mstores, S = {s1, s2, . . . sM} each of which stocks a known inventory of items: we write gk∈ siif store sistocksgift gk. Shops may cover more than one gift on your list and will never be out of the items they stock. Yourhome is the store s1, which stocks no items.The actions you will consider are travel-and-buy actions in which the robot travels from its current location sito another store sjin the fastest possible way and buys whatever items remaining on the shopping list that aresold at sj. The time to travel-and-buy from sito sjis t(si, sj). You may assume all travel-and-buy actionsrepresent shortest paths, so there is no faster way to get between siand sjvia some other store. The robotbegins at your home with no gifts purchased. You want it to buy all the items in as short a time as possibleand return home.For this planning problem, you use a state space where each state is a pair (s, u) where s is the current locationand u is the set of unpurchased gifts on your list (so g ∈ u indicates that gift g has not yet been purchased).(a) How large is the state space in terms of the quantities defined above?M × 2N. You are in one of M places (simple index from 1 to M ), and have not purchased some subset ofN items (binary vector of size N ).(b) For each of the following heuristics, which apply to states (s, u), circle whether it is admissible, consistent,neither, or both. Assume that the minimum of an empty set is zero.([neither] / admissible / consistent / both)The shortest time from the current location to any other store:mins06=st(s, s0)(neither / admissible / consistent / [both])The time to get home from the current location:t(s, s1)(neither / admissible / consistent / [both])The shortest time to get to any store selling any unpurchased gift:ming ∈u(mins0:g ∈s0t(s, s0))(neither / [admissible] / consistent / both)The shortest time to get home from any store selling any unpurchased gift:ming ∈u(mins0:g ∈s0t(s0, s1))([neither] / admissible / consistent / both)The total time to get each unpurchased gift individually:Pg ∈u(mins0:g ∈s0t(s, s0))([neither] / admissible / consistent / both)The number of unpurchased gifts times the shortest store-to-store time:|u|(minsi,sj6=sit(si, sj))Remember, a consistent heuristic doesn’t decrease from state to state by more than it actually costs toget from state to state. And of course, a heuristic is admissible if it is consistent. If you’re confused,remember: the problem defines the minimum of an empty set as 0.1. This heuristic does not return 0 in the goal state (s1, ∅), since it gives the minimum distance to anystore other than the current one.2. We’ll always need to get home from any state; the distance to home from home is 0; and this heuristic1does not decrease by more than it costs to get from state to state.3. We’ll always need to get that last unpurchased item, and taking the min distance store guaranteesthat we underestimate how much distance we actually have to travel. It is consistent because theheuristic never diminishes by more than what is travelled.4. We’ll always need to get home from getting the last unpurchased item, and taking the min under-estimates the actual requirement. What makes this heuristic inconsistent is that when we visit thelast store to pick up the last unfinished item, the value of the heuristic goes to 0. Let’s say thegraph looks like this: s3--1--> s2----5----> s1, with s2containing the last item. From s3, theheuristic is 5, but from s2, the heuristic is now 0, meaning that traveling from s3to s2decreases theheuristic by 5 but the actual cost is only 1.5. This can overestimate the actual amount of work required.6. Same.2You have waited until very late to do your shopping, so you decide to send an swarm of R robot minions toshop in parallel. Each robot moves at the same speed, so the same store-to-store times apply. The problem isnow to have all robots start at home, end at home, and for each item to have been bought by at least one robot(you don’t have to worry about whether duplicates get bought). Hint: consider that robots may not all arriveat stores in sync.(c) Give a minimal state space for this search problem (be formal and precise!)We need the location of each robot at each time. At a given time, a robot can either be at one ofM stores, or in any of (T − 1)M transition locations, where T is the maximum travel distance betweentwo stores. Thus, the location of each robot takes (M T )R. We also need the set of items purchased (2N).Therefore, the size of each state is: (MT )R× 2N.One final task remains: you still must find your younger brother a stuffed Woozle, the hot new children’s toy.Unfortunately, no store is guaranteed to stock one. Instead, each store sihas an initial probability piof stillhaving a Woozle available. Moreover, that probability drops exponentially as other buyers scoop them up, soafter t time has passed, si’s probability has dropped to βtpi. You cannot simply try a store repeatedly; once itis out of stock, that store will stay out of stock. Worse, you only have a single robot that can handle this kindof uncertainty! Phrase the problem as a single-agent MDP for planning a search policy for just this one gift (noshopping lists). You receive a single reward of +1 upon successfully buying a Woozle, at which point the MDPends (don’t worry about getting home); all other rewards are zeros. You may assume a discount of 1.(d) Give a minimal state space for this MDP (be formal and precise!)Which stores have been checked: 2MWhether Woozle has been bought: 2Current time: T .We may also want to keep track of the current location (M ), but since there is no reward for traveling,we don’t have to model that aspect of the problem.3Q2. CSPs: Properties(a) When enforcing arc consistency in a CSP, the set of values which remain when the algorithm terminatesdoes not depend on the order in which arcs are processed from the queue.True False(b) In a general CSP with n variables, each taking d possible values, what is the maximum number of timesa backtracking search algorithm