1) For each of the following domains, which type of agent is appropriate (table lookup, reflex, goal based, or utility based): a) An agent that solves the cannibals and missionaries problem. Goal based is OK. Since this is a VERY SMALL problem, however, a reflex agent or even table lookup are sufficient! b) An agent that plays chess. Table lookup is out for practical reasons. Reflex is reasonable, since only the current state matters. Goal based or utility is probably the RIGHT way to do this, especially if we want to consider MULTIPLE games of chess, but then this is NOT the way Deep Blue was implemented! c) An agent that can pass the Turing test. It is unlikely that an agent that is not utility-based can pass such a test. Of course, under the current state of the art, this is also true for utility-based agents... d) An autonomous robot for exploring Mars Either planning agent, and even better would be a utility-based agent. A pure reflex agent is unlikely to be very useful. Obviously, table-driven is out. EXPLAIN each choice in about 2 sentences. 2) We are given a search problem that has a path cost equal to the number of operators applied on the path to reach the goal (i.e. the path length, as in, e.g. the 8 puzzle). The branching factor is bounded by b (i.e. is never more than b). We are given an admissible heuristic h, that is never wrong by more than 2. There is exactly ONE optimal solution. How many expansion steps are needed in A* to find an optimal solution of length d, in the worst case, if there is NO other solution of length less than d+3. The right answer is: number of expansions is d+1. Proof: consider a node n that is not on the optimal solution path. Any solution that has n in the path has path cost at least d+3, and thus f*(n) = g(n) + h*(n) >= d + 3, (where f* and h* are the exact total cost and heuristic, respectively). Since we have h*(n) - h(n) <= 2 we get f(n) = g(n) + h(n) >= g(n) + h*(n) - 2 >= d+1 For the optimal goal node g, we have f(g) = d, since h is admissible, and because f is monotonic g is expanded before n. Thus, only nodes on the optimal path are expanded. SORRY, earlier solution was an answer to some OTHER question... 3) Invent a heuristic function for the travelling sales-person problem (TSP) and show a case where it can lead to a sub-optimal solution where the path cost is the total tour length (or argue that such a case does NOT exist DESPITE the over-estimate)! (Recall that TSP is the problem of finding a minimal-weight complete (i.e. visit every node once) tour in a weighted graph). Obviously, we mean an INADMISSIBLE heuristic, or with A* we will not get a sub-optimal solution. It is interesting to find a such a heuristic that is also USEFUL (as shown below), but that was NOT a strict requirement of the exercise. Assuming the search problem definition uses a state thet is a partial solution, and an operator adds an arc to the tour (initial state being the empty tour), we now define a heuristic as follows, based on an ADDMISSIBLE heuristic... (Alternate definition of TSP as a search problem is ALSO possible, e.g. start from a complete graph and remove edges, etc.) The heuristic for node n in the search space will be: number of missing arcs (= number of unvisited cities, if we need the version of TSP that is also Hamiltonian), multiplied by some weight. Now, if we use a weight that is the MINIMAL COST of all remaining arcs, we get an ADDMISSIBLE heuristic. However, if we take a LARGER weight, we can get an INADDMISSIBLE heuristic. We will use heuristic where we take cost of the MOST EXPENSIVE arc as a weight. This heuristic is useful, but can lead to a suboptimal solution in the following graph (assume we want a CYCLIC HAMILTONIAN tour for this example, and that the arcs are UNDIRECTED). Nodes in graph: a, b, c, d arc cost ---------------------- a - b 1 b - c 1 b - c 5 a - c 100 a - d 5 c - d 2 There are 3 possible cycles: a-b-c-d-a (cost 13) a-b-d-c-a (cost 104) a-d-b-c-a (cost 111) What will happen is that the partial tour a-b-d which has an f cost of 202 (g is 2, and 2*100 is the heuristic evaluation here) is expanded next as it is beeter than all the rest. The node leading to the optimal solution, (a-b-c) will have an f-cost of 1+5+2+100 = 108, and before it is visited, node a-b-d-c-a (cost 108) will be expanded and returned! 4) Give an example of a 3-person game tree where the best choice of move made by player A will be DIFFERENT for all of the following assumptions: a) Paranoid assumption: all that players B and C want is to make it bad for player A. b) Each player out to help itself, with no communication. c) Same as b, but player B and C can make deals. d) Same as c, but A can also make deals. Th following tree. We denote by tuples (a b c) the score for a, b, c respectively. Also, as we can't draw very easily in ASCII, we will denote choices by "i" where i is a number, for each player. Tree is: A B C scores 0 0 0 (9 0 10) 0 0 1 (-10 3 0) 0 1 0 (-10 -10 3) 0 1 1 (-10 2 2) 1 0 0 (1 -10 -10) (moves for B, C forced - no choice) 2 0 0 (-1 2 1) 2 0 1 (-10 1 -10) 2 1 0 (3 3 3) 2 1 1 (-5 0 4) 3 0 0 (-10 10 5) 3 0 1 (-5 5 5) 3 1 0 (10 4 0) Now, consider the options: a) Under the paranoid assumption, the only move that will guarantee a positive score for A is choice 1. b) If each player is out to improve his own score with no communication, optimal choice for A is 0 - in order to get 9, since B will choose 0 (to avoid -10 due to C choosing C's optimum, 0 - leading to a score of 2 for C). Note choice 2 will result in a score < 10 for A, and choice 3 will result in B choosing 0 (guaranteeing 4 for B), and a bad score for A. c) If B and C can deal, choice 0 is bad because then B, C will deal to get 2 each (option 0 1 1 - a score of -10 for A). In choice 2, B and C will make a deal to get 3 each and 3 for A. If A chooses 3, B will move 0 and A will get a negative score. Optimal move for A is 2. d) If A can deal with B only, then A should choose 3 if B agrees to move 1 (benefits B because A can always move 1) - resulting in 10 for A. This good score is not avaiable elsewhere. 5) Which of the following are valid, satisfiable, or neither: a) Good => Good VALID (since this is like ~Good v Good, which holds if Good is T and also if it is F) b) Good => Bad SATISFIABLE (Good = F, Bad = F is a model, but Good = T, Bad = F is not) c) (Bad => ~Good) => (Good => ~Bad) VALID. In fact, both sides of the main implication have the same models, so this is like the tautology a => a. d) (Good => ~Good) SATISFIABLE (Good = F is a model, but Good = T is not) e) Big v Dumb v (Big => Dumb) VALID (the first 2 disjuncts are satisfied for every assignment, except F, F. But the last disjunct is satisfied in that case, since F => F is true.) f) Good v Bad v Ugly SATISFIABLE (but not valid - all propositions F is not a model) g) (P <=> Q) <=> ((~P v Q) ^ (P v ~Q)) Consider the truth table below: P Q P<=>Q ~PvQ Pv~Q (~PvQ)^(Pv~Q) --------------------------------------------------- F F T T T T F T F T F F T F F F T F T T T T T T We can see that under all possible assignments ("worlds"), the left hand side is the same as the right-hand side of the equivalence statament. Thus, the sentence is VALID.