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 8 puzzle. We can use any search-based agent, but all it needs is the initial situation, so reflex is OK. In fact, the problem size is such that TABLE LOOKUP is possible. b) An agent that plays chess. Again, a search-based agent, but in this case table lookup is NOT reasonable. Reflex is possible, but goal-based is better. Taking into account the TIMING issue, you will need a UTILITY-BASED agent! c) An agent that can pass the Turing test. Will probably need to be utility-based. Anything less will not be able to remember past actions correctly, and there are no clear goals that can be formalized for this agent. d) An autonomous robot for exploring Mars Also, utility-based. If intermitent human-intervension is the mode of operation, goal-based will suffice. 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 1. 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: 1) There is NO other solution of length less than d+2 2) There are k other solutions of length d+1 You need to PROVE your answer! As defined above, the heuristic is either exact or underestimates the number of required steps by 1. Thus: 1) In case 1, the number of expansion steps is exactly d - that is, a node not on the optimal solution path is never expanded. Proof: suppose n is the a node expanded that is not on the optimal solution path, that has been expanded by A*. Denote the depth of n by g(n). Now clearly there is a path from n to the goal of length <= h(n)+1. There is thus a path to the goal through n of length l(n) <= h(n)+g(n)+1 which is not the optimal solution, and thus l(n) >= d+2, and f(n) >= d+1 But for every node n' on the optimal path, we have f(n')= h(n')+g(n') <= d since h(n') is off by 1 at most. We thus have f(n') < f(n), which means n could NOT have been expanded before all the nodes on the optimal have been expanded (including the goal!) - a contradiction. 2) In case 2, likewise, every node n expanded not on the optimal solution path must have f(n) <= d. Now, every such node must also lead to a solution of length d+1. Nodes leading to solutions with length d+2 are never expanded - so each such node n creates a trail with no additional "false trails" to a solution. At worst, all these nodes are at the top level of the tree, and there cannot be more than k of them. Thus, the total number of expanded nodes is at most (k+1)*d. 3) Invent a heuristic function for the cannibals and missionaries problem that sometimes over-estimates, and show a case where it can lead to a sub-optimal solution where the path cost is the number of moves (or argue that such a case does NOT exist DESPITE the over-estimate)! Assuming tha the path cost is number of boat trips, clearly the number of people on the wrong shore is not admissible - it overestimates the number of required trips when e.g. the boat and 2 cannibals are on the wrong shore (heuristic function returns 2, actual required is 1). In this case, the inadmissible heuristic does not cause an unoptimal solution. This can be seen by mapping the entire problem space - it has 32 states (i, j, l) with 0 <= i, j <= 3 and l is left or right. Of these, 12 states are on an optimal solution path, 12 are illegal, and 4 ((3c, 3m, L), (3c, 0m, R) and their symmetric states) are unreachable. Of the remaining 4, 2 are on alternate optimal solution paths: (2c 2m R) is an alternate for (1c 3m R), and symetrically (1c 1m L) is an alternate for (2c 0m L). The last 2 ((2c 3m R) and its symmetric state) are dead ends. Since loops will not emerge as optimal in A*, we still get the optimal solution. 4) Give an example of a 4-ply game tree (branching factor 2) where alpha-beta pruning saves NOTHING, and another where the savings is maximal. How many nodes are pruned in each case? The following tree is already sorted, thus has optimal pruning (lying on is side, for representability in ASCII). Visited nodes are shown as 0, pruned nodes as X. MAX MIN MAX MIN 0----------0-----0--0-0 11 \ 11 11 \ 11\ \0 12 \ \ \ \ \ 0-0 9 \ \ \X 10 \ \ \ 0--0-0 15 \ >=15 \ \0 16 \ \ \ X-X 13 \ \X 14 0-----0--0-0 3 <=3\ <=3\ \X 4 \ \ \ 0-0 1 \ \X 2 \ X--X-X 7 \ \X 8 \ X-X 5 \X 6 If the tree were in REVERSE order, nothing is pruned - need to look at ALL nodes. 5) Use truth tables to show that the following sentences are valid: a) (P <=> Q) <=> ((~P v Q) ^ (P v ~Q)) 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 b) ~(P v Q) <=> (~P ^ ~Q) P Q PvQ ~P^~Q ----------------------------- F F F T F T T F T F T F T T T F c) (P => Q) <=> ~(P ^ ~Q) P Q P=>Q P^~Q ----------------------------- F F T F F T T F T F F T T T T F 6) Which of the following are valid, satisfiable, or neither: a) Good => Good VALID (equal to ~Good v Good) b) Good => Bad SATISFIABLE (e.g. Bad is true) b) Bad => Good SATISFIABLE c) (Bad => ~Good) => (Good => ~Bad) VALID d) (Good => ~Good) SATISFIABLE e) Big v Dumb v (Big => Dumb) VALID f) Good v Bad v Ugly SATISFIABLE 7) Represent the following sentences in FOPC - define the vocabulary first. a) Not all students who pass algorithms pass compilers. Use predicate: pass(student, course), constants: algorithms, compilers ~ forall x pass(x, algorithms) -> pass(x, compilers) b) Only one student passed Algorithms. (Assuming at least one DID pass!) Using same predicates and constants: Exists x pass(x, algorithms) ^ (forall y pass(y, algorithms) -> x=y) c) Some polititians can fool all of the people all of the time. Predicates: politician(x), person(x), can_fool(x, y, time), time(t) exists x politician(x) ^ forall y, t (person(y) ^ time(t)) -> can_fool(x, y, t) d) Every bird has 2 wings. Predicates: has_part(object, part), bird(object), wing(object) forall x bird(x) -> exists y, z has_part(x, y) ^ wing(y) ^ has_part(x, z) ^ wing(z) ^ ~(y=z) ^ forall w (has_part(x, w) ^ wing(w)) -> (w=y v w=z) e) There is a barber who shaves all men in town who do not shave their barber. Predicates: barber(x), shaves(x, y), in_town(x) Function: barber_of(x) exists x barber(x) ^ forall y (in_town(y) ^ ~shaves(y,barber_of(y)) -> shaves(x,y) 8) Write FOL sentences that define the effects of the "grab" action in the wumpus world. forall x, y, s holding(agent, gold, result(grab, s)) <- at(agent, x, y, s) ^ at(gold, x, y, s) 9) In situation S0, The robot is in room R1, which has box B1, The move action moves the robot. If the robot has the box, the box moves with the robot. The pickup action results in the robot holding the box (has_box), if the box is in the same room as the robot. a) Write down the axioms for this mini-domain. b) Can you prove that in_room(B1, R2, result(move, result(pickup, S0))) with your axioms? If yes, do so. If not, what is missing? c) Can you prove that in_room(B1, R2, result(move, result(wait, result(pickup, S0)))) with your axioms? If yes, do so. If not, what is missing? Predicates are: has_box(situation), in_room(object, room, situation). Actions are: pickup, move, wait. a) Axiom 1: picking up the box whwn in same room forall x, s has_box(result(pickup, s)) <- in_room(B1, x, s) ^ in_room(robot, x, s) Axiom 2: move results in moving the robot to room R2 forall s in_room(robot, R2, result(move, s)) Axiom 3: move does not affect the robot's holding the box forall s has_box(result(move, s)) <-> has_box(s) Axiom 4: if the robot is holding the box, the box is in the same room as the robot. forall s, r has_box(s) ^ in_room(robot, r, s) -> in_room(B1, r, s) For situation S0 we have: in_room(robot, R1, S0) ^ in_room(B1, R1, S0) b) Yes, because from the initial conditions and axiom 1 we get has_box(result(pickup, S0)) using axiom 2 with the above we get: in_room(robot, R2, result(move, result(pickup, S0))) and using axiom 3 we get that the robot still has the box has_box(result(move, result(pickup, So)) Now, with axiom 4 and the last 2 facts we get: in_room(B1, R2, result(move, result(pickup, S0))) c) The extra action wait is has no axioms, so we can say NOTHING about what is true in the resulting situation. We need to add the axiom that wait does not change has_box(): forall s has_box(s) -> has_box(result(wait, s)) Also, if the action sequence were pickup, move, wait, then we would also need to say that wait does not move the robot! In general, we will need to have axioms about what all actions do NOT do, as well as what they do - and the representation in FOL is not very compact as a result! (The FRAME PROBLEM).