Assignment 3: Extensions to ISA Hierarchies
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Winter 2005
Create a new version of the Linneus program called NewLinneus.py that implements the features listed below. Note that the first two features are required and the last three are optional.
Due Friday, January 27 at the beginning of lab. Turn in your source code by 12:00 noon using the turnin server. At the beginning of lab, turn in a printout of a session with your program that starts with the test cases given and then goes into your own cases.
 
Basic Redundancy Detection.(50 points) Extend the Linneus program to automatically maintain its inclusion hierarchy in transitive reduction (Hasse diagram) form. (That means that no link is stored if it can be inferred by transitivity or reflexiveness.) In connection with this, the conversational front end should handle the following new kinds of responses: 
I already know that by inference.
I have been told that before.
Name your program NewLinneus. If you tell NewLinneus that "A dog is a mammal." and then later tell it exactly the same thing, it should respond "I have been told that before.". If you tell it something that it can already deduce, it should respond "I already know that by inference.", 
A lion is a carnivore.
A lion is a carnivore.
A carnivore is an animal.
A lion is an animal.
A lion is a thing.
HAS links. (50 points). Let us assume that "A house has a roof." means that a house has a roof as a part. Suppose we want to extend Linneus to know about and reason with HAS links as well as ISA links.
  1. Let Isa(x, y) mean "an x is a y," and let Has(x, y) mean "an x has a y as a part." New HAS links may be inferred from combinations of existing ISA and HAS links. For example, 
    Has(x, y) ^ Isa(y, z) --> Has(x, z).
    Summarize (in English) the rules for inferring HAS relationships from other HAS relationships and ISA relationships. Then describe the rules using logic (ideally, predicate calculus). Put this in a comment near the beginning of the NewLinneus.py file.
  2. Just as isa_test(x, y, n) succeeds if there is a path from x to y of length n or less, following only ISA links, one can imagine a function hasatest(x, y, n) that tests for an implied HAS relationship between x and y. Exactly what kind of path between x and y implies that the test should succeed? Put your answer to this question into the comments, following your logical description.
  3. Extend the Linneus program to properly handle HAS links. Allowable inputs should include expressions such as 
    A dog has a snout.
    which expresses the fact that a dog has a snout, 
    A dog has a leg.
    which says a dog has a (at least one) leg, and 
    Has a dog a paw?
    which asks, "Does a dog have a paw?" or equivalently, "Do dogs have paws?"
Advanced Redundancy Detection (Extra credit: worth 15 points) Add the capability to automatically detect the superfluousness of earlier user statements, in the light of the most recent statement. For example, suppose the following sequence of facts is entered. 
A dog is a thing.
A dog is an animal.
An animal is a thing.
A dog is a mammal.
A mammal is an animal.
After this last fact, the NewLinneus program should report 
Your earlier statements that a dog is a thing and that 
a dog is an animal are now redundant.
Thus if you tell NewLinneus something new (not already implied) that makes a previously input fact redundant, NewLinneus should reply with a statement such as "Your earlier statement that a mouse is an animal is now redundant.". Furthermore, the redundant link should then be removed, so that the internal data structure is kept nonredundant. Test your program on the sequence of facts given above plus another sequence of your own creation.
Basic HAS Links Redundancy Detection (Extra credit: worth 5 points) Extend the basic ISA redundancy detection so that it works also for HAS relationships.
Advanced HAS Links Redundancy Detection (Extra credit: worth 5 points) Extend the advanced ISA redundancy detection so that it works also for HAS relationships. When either a HAS relationship or an ISA relationship is input that causes any previously input relationships (of either HAS or ISA form) to become redundant, report these and remove the redundant links from the internal data structures.