CS188: Artificial Intelligence, Fall 2010Written 1: Search and CSPsDue: Tuesday 9/28 in 283 Soda Drop Box by 11:59pm (no slip days)Policy: Can be solved in groups (acknowledge collaborators) but must be written up individually.1 Hive Minds (10 points)You control one or more insects in a rectangular maze-like environment with dimensions M × N, as shownbelow. At each time step, an insect can move into an adjacent square if that square is currently free, or theinsect may stay in its current location. In the case of multiple insects, this rule means that adjacent insectscannot swap in a single time step. Squares may be blocked by walls. The map is known. Optimality is alwaysin terms of time steps; all actions have cost 1 regardless of the number of insects moving or where they move.For each of the following scenarios, precisely but compactly define the state space and give its size. Then,give a non-trivial admissible heuristic for the problem. Your answers should follow the format in the examplecase below. Full credit requires a minimal state space (i.e. do not include extra information) and a reasonablenon-trivial heuristic.Example: Lonely Bug You control a single insect as shown in the maze above, which must reach a designatedtarget location X. There are no other insects moving around.State space description: A tuple (x, y) encoding the x and ycoordinates of the insect.State space size: M × N .Heuristic: The Manhattan distance from the insect’s loca-tion to the target.(a) (2 pts) Swarm Movement You control K insects, each of which has a specific target ending locationXk. In each time step all insects move simultaneously (or stay in place). An example is shown here:1State space description:State space size:Heuristic:2(b) (2 pts) Patrolling Guards You again control a single insect, but there are G spiders patrolling knownpaths as shown below. Specifically, at time t each guard g will be at position (xg(t), yg(t)) (in general, guardmovements need not be a function of a guard’s current location, but you may assume that the tuple of guardpositions repeats with period T ). Similarly to (a), your insect cannot take an action which moves it into eithera guard’s current location or the location a guard is about to occupy.State space description:State space size:Heuristic:(c) (2 pts) Step on It Your single insect is alone in the maze again. This time, it can speed up as long asit doesn’t change direction. Specifically, after a move of v squares in some direction, it can move up to v + 1squares in that same direction on the next time step. It can move fewer than v + 1 squares in that direction,as well, and it can move one square in any other direction (or stand still). Moving v squares requires that allintermediate squares passed over, as well as the v th square, currently be empty. The cost of a multi-squaremove is still 1 time unit. For example, the dots in the maze below indicate where the insect will be after eachtime step in the optimal (fewest time step) plan:State space description:State space size:Heuristic:3(d) (2 pts) Lost at Night It is night and you control a single insect. You know the maze, but you do notknow what square the insect will start in. You must pose a search problem whose solution is an all-purposesequence of actions such that, after executing those actions, the insect will be on the exit square, regardless ofinitial position. The insect executes the actions mindlessly and does not know whether its moves succeed: if ituses an action which would move it in a blocked direction, it will stay where it is. For example, in the mazebelow, moving left twice and then right twice guarantees that the insect will be at the exit regardless of itsstarting position.State space description:State space size:Heuristic:(e) (2 pts) Escape! Your insect is again alone in a maze, but certain squares are filled with pesticide, shownbelow in green. Those squares are safe to travel through provided the insect does not accumulate more thanL time steps in the pesticide, at which point it would die. You must find a solution where no more than Lpesticide squares are used.State space description:State space size:Heuristic:42 A* (9 points)Consider the following search problem, given as a graph:A B C D F Gh10 0 0 0 0 0h211 7 7 3 0 0h313 9 7 1 0 0h415 10 11 5 0 0Here, A is the start state and G and F are goals.(a) (1 pt) Which heuristics are admissible (or write none)?(b) (1 pt) Which heuristics are consistent (or write none)?(c) (1 pt) For heuristic h3, what order will nodes (paths) be added to the fringe in A∗graph search (breakties however you like)?(d) (1 pt) For heuristic h3, what order will states be added to the closed set in A∗graph search?(e) (1 pt) For heuristic h3, what path will A∗graph search return?(f) (1 pt) For heuristic h3, what path will A∗tree search return?(g) (1 pt) For heuristic h3, what path will greedy / best-first graph search return?(h) (2 pts) Correct this almost true statement: with a perfect heuristic, A∗search will only add to the closedset states which lie along the path it returns.53 Pacman Layout (9 points)You are tasked with designing a new board layout for a Pacman-style game where each square is either emptyor filled with a wall. The layout rules are simple: (i) the border of the board must consist of walls and (ii)the board cannot have dense open spaces or dense walls, defined as a 2x2 blocks of the same value. The entireboard is M × N . Assume there is a variable Sij∈ {e, w} for each square (i, j), whose value indicates whetherthat square is empty or filled with a w all.(a) (1 pt) State the constraints of the problem (implicit statements are ok, but be precise). Don’t forgetabout unary constraints!(b) (1 pt) Draw the constraint graph for this CSP for a 3 × 3 board. Remember that in a general CSP,the graph has both circles (for variables, draw them unshaded) and boxes (for constraints, draw them shaded).Show all constraints, of any order.(c) (2 pts) Imagine that your CSP solver only handles binary constraints. Come up with an alternateformulation which adds a new variable Qijfor each 2-by-2 block with upper left corner at (i, j). This newformulation should use only binary constraints (though the new variable’s domains need not be binary). Stateprecisely what the variables, domains, and constraints are for your formulation.6(d) (1 pt) Draw the constraint graph for this new CSP for a 3 × 3 board. Show all constraints.(e) (2 pts)
View Full Document
Unlocking...