1) Consider the following search problem (also known as LEAST-COST PROOF, which is NP-hard). You have a list KB of clauses F1,...Fk. Each Fi is of the form: l1 or l2 or ... lm where the l's are literals, i.e. a propositional variable or its negation. You need to apply the operators: a) resolution b) simplification in order to prove a propositional statement (by contradiction). Assume that applying resolution costs 2, and simplification costs 1 (simplification means: in a clause that contains 2 or more instances of the same literal - remove one of them. Note that only ONE literal is removed at each step (e.g. reducing 3 copies of the same litral to 1 copy takes 2 steps). The problem is: given clauses KB and a sentence Y, find the proof P that has the least cost. For example, we have the KB consisting of the clauses: C1: ~P or Q C2: ~R or Q C3: ~Q and need to prove the sentence Y: ~P or ~R (hint - before the search, you need to add a transformed Y into your KB) a) Write the above problem as a formal search problem. Note that the path cost has to reflect the proof cost. b) Consider the heuristic h(n) = number of literals in the shortest clause. Is h(n) an admissible heuristic? Prove it. c) Find another another admissible heuristic h1 that performs better than h, for at least SOME cases (and provide an example or prove that it dominates h). d) Find a non-admissible heuristic h2 and an example where it performs better than h and h1. e) Would keeping track of repeated states help in the search algorithm? If so, give an example. f) Can the algorithm be made more efficient in SPACE requirements, if we need to find ANY proof, rather than the shortest proof? How, and how much more efficient, asymptotically? 2) Consider a 3-person complete information game between players A, B, and C, playing in turn (first A, then B, then C, and then the game ends). The game tree is defined as follows: A B C scores ---------------------------- A1 B1 C1 (100, 5, 20) C2 (50, 10, 0) B2 C1 (10, 20, 30) C2 (20, 0, 50) A2 B1 C1 (90, 0, 80) C2 (0, 20, 90) A3 B1 C1 (90, 0, 20) C2 (80, 30, 0) B2 C1 (80, 0, 40) C2 (0, 0, 0) B3 C1 (30, 20, 50) A4 B1 C1 (0, 90, 50) C2 (20, 70, 70) B2 C1 (100, 100, 0) C2 (95, 95, 1) Assume that the scores theoretically achievable by each player are all between 0 and 100. a) What is the best play for A, assuming that each player is out to improve its own score, and there is no communication between players? b) If players can reach agreements, will this make any difference (answer separately for each different type of agreements). c) How will the answer change if A is paranoid (i.e. believe that the other players will act to minimize A's score)? d) Suppose that B always plays randomly with uniform probability. What is the best action by A now? e) Will using alpha-beta pruning above (modified alpha-beta in case d) save any search in the search algorithm for the best move? What will be the savings in each case? Assume (and show) the best-case ordering for the search. f) How would you treat the problem if C could not observe the move made by B? 3) A rational agent has a choice of algorithms to apply for a search problem. Suppose the agent need to minimize total operating costs, which are given as: 1000 * G + S, where G is the cost of the path taken by the agent, and S is the number of search steps used by the search algorithm. a) Assuming that the agent knows the above, and reasons to optimize the cost, what type of agent is this (reactive? goal-based? etc.). b) Assume that the agent has 3 choices: 1) Use default actions without search, and use an immediately available solution with cost 1000. 2) Use A*, where it has an admissible heuristic that is usually wrong by a factor of 2. 3) Use RTA*, with the same heuristic, and a limit of K search steps. We assume that the branching factor is 2, and that the agent knows (correctly) that there exists a solution at depth 10. (Assume operator cost of 1, and that the search space is acyclic). (Note: there may be insufficient information to answer b, but the point is to try to answer, and to figure out what's missing, if anything, and what further assumptions may be necessary). Justify all answers shortly!
Deadline: December 7, 2003, at 11 AM ( strict deadline).