CS 453: Artificial Intelligence, Spring 2005
Assignment 5

This assignment is due on Wednesday, March 30. For the assignment, you will work with a small knowledge base of facts. You will write some Lisp functions for making deductions based on the facts in the database, and you will provide a simple conversational interface to the data. Your work will be based on the sample program isa.lisp, which already handles "isa" facts such as "(isa dog mammal)." The program can make deductions such as using the fact (isa dog mammal) together with the fact (isa mammal animal) to conclude that (isa dog animal). Your task is to handle certain other types of facts. You should one of the following two kinds of facts, or both if you would like to get an A:

1. can and cannot facts. These are facts such as "(can bird fly)," meaning that birds can fly, and "(cannot penguin fly)," meaning that penguins can not fly.

2. has and hasnot facts. These are facts such as "(has mammal tail)," meaning that mammals have tails, and "(hasnot ape tail)," meaning that apes do not have tails.

Your program should be able to make several types of deductions. For example, from the facts that a bird can fly and that a robin is a bird, it should deduce that a robin can fly. From the facts that an animal has legs and that a human is (indirectly) an animal, it should deduce that a human has legs. From the fact that a human is an ape and apes do not have tails, it should deduce that humans do not have tails. Note that these deductions are based on the isa hierarchy that is already implemented in the sample isa.lisp program. The rule is that "A" can have properties of its own, and it can also inherit properties from "B" if "A isa B." We will discuss this type of inheritance and the deductions that can be based on it in class.

You should add some facts about can/cannot and/or has/hasnot to the database of facts that is built into the isa.lisp program. You should then start writing functions for making deductions and for adding new facts of the same sort to the database. You should write each function separately and test it by calling it by hand from the interactive Lisp interface. Once your functions are working, you can provide the conversational interface by extending the respond function in isa.lisp. This is Lisp -- you should take advantage of its interactive development style. Do not just try to type in a big program and then test it at the end!

Some notes: As an alternative to using both has and hasnot facts, you might consider using a single type of fact such as "(has animal tail yes)" or "(has ape tail no)" where the fourth item in the list tells whether the property is being asserted or denied. You can do the same with can. When you are working with the conversational interface for has, you will have to decide on a way to deal with English plurals. It is natural to say both "A mammal has legs" and "A mammal has a tail." It is not very natural to say "A mammal has a leg". You should probably allow both forms.

This is an individual assignment. You should not work with other people, show them your work, or discuss your work with them.

David Eck