CS 188 Introduction to AISpring 2004 Stuart Russell Midterm Solution1. (12) Agents and Environments(a) (3) True/False There exist task environments (PEAS) in which some pure reflex agents behave rationally.TRUE: For assignment A1 you examined a pure reflex vacuum-cleaner agent that was rational for its two-squaretask environment. In principle, any fully observable environment can be handled by a pure reflex agent.(b) (3) True/False There exist task environments (PEAS) in which all pure reflex agents behave irrationally.TRUE: See examples on p.48 of AIMA2e.(c) (3) True/False The input to an agent program is the same as the input to the corresponding agent function.FALSE: the agent program takes the current percept, whereas the agent function takes the percept history.(d) (3) True/False Every agent function is implementable by some program/machine combinationFALSE: In lecture, the example of the halting problem was given.1There may also be functions that arecomputable but cannot be computed in any practical amount of time on any feasible computer, but as yet wehave no logically necessary bounds on what “feasible” means.2. (15) SearchConsider the problem of moving k knights from k starting squares s1, . . . , skto k goal squares g1, . . . , gk, onan unbounded chessboard, subject to the rule that no two knights can land on the same square at the sametime. Each action consists of moving up to k knights simultaneously. We would like to complete the maneuverin the smallest number of actions.(a) (5) What is the maximum branching factor b in this state space?(i) 8k (ii) 9k (iii) 8k(iv) 9k(iv). For each of k knights, we have one of 8 moves in addition to the possibility of not moving at all; eachaction executes one of these 9 choices for each knight (unless some choices conflict by landing on the samesquare), so there are 9kactions. We gave partial credit for choosing (ii) or (iii).(b) (6) Suppose hiis an admissible heuristic for the problem of moving knight i to goal giby itself. Which ofthe following heuristics are admissible for the k-knight problem?(i) min{h1, . . . , hk} (ii) max{h1, . . . , hk} (iii)Pki=1hi(i) and (ii). If the hiwere exact, (ii) would be exact for the relaxed problem where knights can land on thesame square. The hiare admissible and hence no larger than the exact values, so (ii) is admissible. (i) is nolarger than (ii), so (i) is admissible. (iii) is not admissible. For example, if each giis one move from its si,then (iii) returns k whereas the optimal solution cost is 1.(c) (4) Which of these is the best heuristic?(i) min{h1, . . . , hk} (ii) max{h1, . . . , hk} (iii)Pki=1hi(ii) dominates (i) so it must be as good or better. (iii) is probably of little value since it isn’t admissible andcompletely ignores the capability for parallel moves.1Imagine a lisp function HALT that takes two inputs, a lisp function FUN and the arguments for that lisp function ARGS, and (HALTFUN ARGS) returns T if (FUN ARGS) terminates after some finite time and NIL otherwise. Turing showed that while such a functionis easy to describe, there is no way to compute it, that is, no agent program can implement the HALT function.Here is an outline that gives some intuition as to why HALT can’t be computed. Suppose HALT does exist, we can then define asecond lisp function (DEFUN PARADOX (S) (IF (HALT S S) (PARADOX S) T)). The function PARADOX returns if (S S) terminatesand goes into infinite recursion when (S S) doesn’t terminate.Now we ask ourselves, what does (HALT #’PARADOX #’PARADOX) return, T or NIL? Suppose it returns T, then the IF conditionalin PARADOX is true so PARADOX goes into infinite recursion. This means that PARADOX actually doesn’t halt when fed itself asinput, contradicting our assumption that (HALT #’PARADOX #’PARADOX) returns T. Suppose instead that (HALT #’PARADOX#’PARADOX) returns NIL, then PARADOX called on itself would terminate, returning T, so in fact HALT can’t return T either. SincePARADOX is a well defined function, it must be that HALT cannot exist.13. (25) CSPs and local searchConsider the problem of placing k knights on an n × n chessboard such that no two knights are attacking eachother, where k is given and k ≤ n2.(a) (5) Choose a CSP formulation. In your formulation, what are the variables?Solution A: There is a variable corresponding to each of the n2positions on the board.Solution B: There is a variable corresponding to each knight.(b) (5) What are the values of each variable?Solution A: Each variable can take one of two values, {occupied,vacant}Solution B: Each variable’s domain is the set of squares.(c) (5) What sets of variables are constrained, and how?Solution A: every pair of squares separated by a knight’s move is constrained, such that both cannot beoccupied. Furthermore, the entire set of squares is constrained, such that the total number of occupied squaresshould be k.Solution B: every pair of knights is constrained, such that no two knights can be on the same square or onsquares separated by a knight’s move. Solution B may be preferable because there is no global constraint,although Solution A has the smaller state space when k is large.(d) (5) Now consider the problem of putting as many knights as possible on the board without any attacks.We will solve this using local search. Briefly describe in English a sensible successor function.Any solution must describe a complete-state formulation because we are using a local search algorithm. Forsimulated annealing, the successor function must completely connect the space; for random-restart, the goalstate must be reachable by hillclimbing from some initial state. Two basic classes of solutions are:Solution C: ensure no attacks at any time. Actions are to remove any knight, add a knight in any unattackedsquare, or move a knight to any unattacked square.Solution D: allow attacks but try to get rid of them. Actions are to remove any knight, add a knight in anysquare, or move a knight to any square.(e) (5) Briefly describe in English a sensible objective function.An objective function returns a number describing the desirability of the state. The key requirement is thatthe objective function must have its global optimum at the optimal solution (here, we are maximizing):Solution C: the number of knights placed on the board. Since all states have no attacks, the global optimumof this function is in fact the optimal solution.Solution D: Here we need to penalize for attacks. One
View Full Document
Unlocking...