Assignment 2: Inference With Knowledge Using Partial-Order Properties
|
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Autumn 2017
|
![](../bar.gif) |
The reading for this assignment is
Knowledge Representation
in The Elements of Artificial Intelligence with Python.
|
Due Friday, October 13 through
Catalyst CollectIt
at 11:59 PM.
|
Part I. Written Answers (20 points).
-
Exercise 3 on page 154.
-
Exercise 4 on page 155.
|
Part II. ISA Hierarchy Manipulation: Inference Through Transitivity (80 points)
The Python code for a program called Linneus that manages a small knowledge base is available
here.
Add the features described below to the Linneus program.
Hint 1: Draw graphs of the partial orders corresponding to example and analyze how the graph must
be searched in order to satisfy the new command.
-
> Tell me what you know about 'animal', with justification.
An animal is an organism; you told me that directly.
An animal is a thing, because an animal is an organism and an organism is a thing.
An animal is something more general than a mammal, because a mammal is an animal.
An animal is something more general than a dog, because a dog is a mammal and an mammal is an animal.
An animal is something more general than a fish, because a fish is an animal.
That's all I know about 'animal'.
The starter code includes a "test" feature that will give you some evidence
about whether your program implements this feature correctly or not. This test
feature was developed by A2 lead TA Connor Schenck.
|
Extra Credit Option
(Cycle detection and elimination is worth 5 points of extra credit.)
- Cycle Detection and Elimination. Because the ISA relation is a partial order,
it must obey the antisymmetry property, which states that if x R y and y R x, then
x = y. Because of transitivity, this means than in any cycle, such as
a R b, b R c, and c R a, it must be the case that a = b = c.
When the user inputs statements that form such a cycle, your program should detect
that a cycle would be formed by the latest statement, if processed normally.
It should report that to the user and then perform the following changes to the database:
Determine which node is the starting point in the cycle (for example x when
x R y and y R x are input in that order). Make all the other nodes in the cycle
become "aliases" of the starting node, and merge them into the starting node.
That means any edge involving one of these nodes has one of its endpoints replaced
by the starting node. The program should be able to use the aliases in further
interactions. An example is given below.
> A creature is a being.
I understand.
> A being is a living-thing.
I understand.
> A living-thing is a creature.
I infer that creature, being, and living-things are all names
for the same thing, and I'll call it creature.
> A bug is a creature.
I understand.
> Is a bug a being?
Yes.
> Why is a bug a being?
Because a bug is a creature, and being is another name for creature.
> A living-thing is an organism.
I understand.
> Is a bug an organism?
Yes.
> Why is a bug an organism?
Because a bug is a creature, and a creature is an organism.
|
What to Turn In
Each student should
Turn in a file PartI.txt and a file PartII.py.
Your PartI.txt file should contain your name and the answers to the questions in Part I.
Your PartII.py file should begin with a multiline string that gives, on the first line,
your name, and on the next line, an indication of whether you did the extra-credit option.
Here is an example.
'''PartII.py
John Doe, CSE 415, Autumn 2017, University of Washington
Instructor: S. Tanimoto.
Assignment 2 Part II. ISA Hierarchy Manipulation
Extra credit (Cycle detection and processing) implemented and working.
'''
The rest of your file PartII.py should contain a version of the Linneus program that
provides the implementation of the features according to your status comments.
|
Updates and Corrections
If necessary, substantial updates and corrections will be posted here and mentioned in class or on
GoPost.
|
Feedback Survey
After submitting your solution, please answer this
survey
|