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).