1) Consider the following search problem over first-order logic (also known as
LEAST-COST PROOF, which is NP-hard, even if it is known that a proof with
a given finite n steps exists).
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. an atomic sentence 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 1, and
simplification costs 2 (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(x) or Q(y)
C2: ~R(x) or Q(x)
C3: ~Q(z)
and need to prove the sentence Y: ~P(2) or ~R(M(1))
(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 or disprove 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) For each of the following English sentences, represent them to FOL
using the predicates given. Then, show the steps in converting them
into conjunctive normal form.
a) Every politician is popular in some state.
(predicates: politician(x), popular_in(x, y), state(y))
b) Every dog that has at least three unbroken legs can walk.
(predicates: dog(x), can_walk(x), has(x, y), leg(y), broken(y), equality ("="))
c) Some politicians can fool some of the people all of the time
(predicates: politician(x), can_fool(x, y, t), person(y))
3) We have a search problem where the cost of each operator is 1. The branching
factor is bounded by b. We have a heuristic evaluation function h(n) that
is admissible, and such that h(n) >= h*(n) - 3 (that is, it is never off by more than 3).
We use h(n) as a search heuristic in the A* algorithm.
a) Suppose that there is only one solution to the problem. How many nodes will be
expanded by A* using h(n) above as a heuristic, in the worst case, if
h*(initial_state) = d ?
b) How does the above change if there is more than one solution, but any other solution
has path cost at least 4 greater than d?
c) Same as in (b), but there is also ONE solution with cost d+2.
4) Consider the stochastic game to be implemented in assignment 2: grid based environment,
agents can move forward, turn right or left, and shoot (hitting with probability p/d, where
d is the distance). You may assume a time limit as desired for the length of the game in
each scenario.
a) Show a scenario (with no bullets) where for the first agent to move, under zero-sum scoring,
moving forward loses, but under total flags collected scoring the optimal move is to move forward.
b) In the game with bullets, show a scenario where the the first agent to move loses.
In both cases, you must PROVE the scores by generating the respective game tree, either
to a terminal position or prove that you can prune some branches.
c) Suggest heuristic evaluation functions for the total-flags scoring version of the game:
1) One that is a lower bound, but non-trivial.
2) One that is optimistic an upper bound, but non-trivial
5) Completing the proof from wumpus world done in class, plus a bit more...
a) Write the following domain axioms in FOL:
1. A wumpus stinks up all ajacent squares. ("square" and "location" are used interchangably here)
2. Only at most one square contains a wumpus. (This is a new one, to make it interesting).
3. A stinky square implies a wumpus in an adjacent square.
4. Zero is an integer, and a successor of an integer is an integer.
5. The successor of 0 is 1, ... the successor of 3 is 4...
6. An integer is greater-than-or equal to itself, and a successor of an
integer x is greater-than-or-equal to x.
7. The value of the function first(x) is the first element of x.
8. The value of the function second(x) is the second element of x.
9. Squares (locations) are adjacent if and only if they have one coordinate
equal to the other, and in the other coordinate one is the successor of
another, and both are legal.
10. A square (location) is legal if and only if its first and second
coordinates are between 1 and 4.
11. A location with no wumpus is safe.
The predicates to use are:
Wumpus(loc), Legal(loc), Adjacent(loc1, loc2), Stinky(loc), Safe(loc), x=y, x >= y
Constants to be used are: 0, 1, 2, 3, 4, 5, ...
Functions to be used are: S(x), First(x), Second(x).
b) Convert the above into conjunctive normal form, this is your basic KB.
c) Add the following to the basic KB: not Stinky([2,1])
Prove by refutation (using just reolution) that Safe([2,2]).
d) In addition to the above, add to the KB: Stinky([3,1]) and Stinky([2,2]).
Prove by refutation (using just reolution): Safe([1,2]).
If you need to add an axiom to complete the proofs, add them, but justify why the
proof fails without them!
Justify all answers shortly!
Deadline: Wednesday, April 27, 2005 ( strict deadline).