CSPs: Trapped Pacman Pacman Is Trapped! He Is Surrounded By Mysterious Corridors, Each Of Which Leads To Either A Pit (P), A Ghost (G), Or An Exit (E). In Order To Escape, He Needs To Figure S $ 2 S W 5 S W Out Which Corridors, If Any, Lead To An Exit And Freedom, Rather Than The Certain Doom 1 Of A Pit Or A Ghost. The One Sign Of What Lies Behind The

 

 

2. CSPs: Trapped Pacman Pacman is trapped! He is surrounded by mysterious corridors, each of which leads to either a pit (P), a ghost (G), or an exit (E). In order to escape, he needs to figure out which corridors, if any, lead to an exit and freedom, rather than the certain doom a pit or a ghost. The one sign of what lies behind the corridors is the wind: a pit produces a strong breeze (S) and an exit produces a weak breeze (W), while a ghost doesn't produce any breeze at all. Unfortunately, Pacman cannot measure the strength of the breeze at a specific corridor. Instead, he can stand between two adjacent corridors and feel the max of the two breezes. For example, if he stands between 1 2 S W S S 3 W 4 a of pit and an exit he will sense a strong (S) breeze, while if he stands between an exit and a ghost, he will sense a weak (W) breeze. The measurements for all intersections are shown in the figure below. Also, while the total number of exits might be zero, one, or more, Pacman knows that two neighboring squares will not both be exits. Pacman models this problem using variables X/ for each corridor i and domains P, G, and E. 1. State the binary and/or unary for this CSP (either implicitly or explicitly). 2. Cross out the values from the domains of the variables that will be deleted in enforcing arc consistency. X P G E X2 G E X3 P G E X4 P G E X5 P G E X6 P G E 3. According to MRV, which variable or variables could the solver assign first? 4. Assume that Pacman knows that X6 = G. List all the solutions of this CSP or write none if no solutions exist.