Compulsory assignments AI -04


Assignments 1 - 3 should be done individually, 4 could be done by groups of two.

Solutions to the assignments should contain the following:


Assignment 1

To be completed by the lecture 21/4

Write a short review of one of the three articles, and give also your personal view on the problems that are raised in the articles. Note that all three articles are compulsary to read, and you can use material from all in your discussion. You can borrow the articles if you write your name on the list.

Assignment 2

To be completed by the lecture 28/4

Write the lisp functions get-rid-of-imp and move-neg-inwards which perform the first two steps in the algorithm of tranforming logical expressions into clause form.
E.g. 

(get-rid-of-imp '(for-all x (for-all y (imp (and (p x) (q y)) (r x y)))))
should give 
(for-all x (for-all y (or (not (and (p x) (q y))) (r x y)))))
and 
(move-neg-inwards (get-rid-of-imp
   '(for-all x (for-all y (imp (and (p x) (q y)) (r x y))))))
should give 
(for-all x (for-all y (or (or (not (p x))(not (q y))) (r x y)))))
You can use the following rules which you can find in points 1 and 2 in section 12.2.2 on page 520.: 
(imp a b) => (or (not a) b)

(not (not a)) => a
(not (and a b)) => (or (not a)(not b))
(not (or a b)) => (and (not a)(not b))
(not (forall x a)) => (exists x (not a))
(not (exists x a) => (for-all x (not a))
The documentation should include test of the examples above, and (not (not (or (not (not a)) (not b)))) plus some other.

Assignment 3

To be completed by the lecture 12/5

Write rules for an expert system for the shell which is described in the book, pp. 736 -743. You can get the code from the net: exp.lsp
Here is an example how it works.
Find a suitable application, e.g. determination of species for dogs, trees or flowers, diagnosis of illness, or trouble shooting in some area. The system must contain at least 20 rules, which can form a chain of at least 4 rules. The documentation should include a description of the domain, preferably as a diagram.

Assignment 4

To be completed by the lecture 27/5. You may work together two and two with this task. Three missionaries and three cannibals come to a river and find a boat that holds two. If the cannibals ever outnumber the missionaries on either bank, the missionaries will be eaten.

How shall they cross? The following is an exerpt from a web site by John McCarthy. We call this original version of the problem MCP0.

Saul Amarel proposed [Ama71]: Let a state (mcb) be given by the numbers of missionaries, can nibals and boats on the initial bank of the river. The initial situation is represented by 331 and the goal situation by 000.

Most AI texts that mention the problem accept this formulation and give us the solution:

331 - 310 - 321 - 300 - 311 - 110 - 221 - 020 - 031 - 010 - 021 - 000

If one indeed begins with the Amarel representation, the problem is indeed trivial. However, suppose we want a program that begins, as people do, with a natural language presentation of the problem. It is still trivial if the program need only solve the missionaries and cannibals prob lem. The programmer can then cheat as much as he likes by making his program exactly suited to the MCP. The extreme of cheating is to make a program that merely prints

331 - 310 - 321 - 300 - 311 - 110 - 221 - 020 - 031 - 010 - 021 - 000

We begin a few examples of English language elaboration tolerance.

Here ends the exerpt.

Your task is to write a lisp function which can solve the problem for 3 missionaries and 3 cannibals. The same program (but with other input) shall also show that there is no solution for 4 missionaries and 4 cannibals. The other versions are optional.

The execution with 4+4 shall contain a trace that shows all states which are tried.

Last modified: Mon Mar 22 11:28:14 MET 2004