CSE 573 – Artificial Intelligence I – Autumn 2001

Homework #3 A

Due in class Wednesday Nov 14th



Note: the second part of this assignment – #3B – will be distributed later this week, and will be due on Monday Nov 19th. It will involve specifying and solving a planning problem using a planning-as-satisfiability planner we will provide.


1. Diagnostic Reasoning


In the lecture on consistency-based diagnosis we mentioned that costs can be assigned to assumptions to account for the cost of checking if they actually hold. Describe in high-level pseudo-code the design of a complete diagnosis system that does the following:

  1. Input is:

    1. a propositional Horn knowledge base KB that describes the proper functioning of some device;

    2. an initial set of observations Obs0, that includes the fact that the device is not working properly (e.g. “~EngineRuns”);

    3. a set U of propositions that represent facts whose truth is unknown, but which are true when things are working normally (e.g., “FuelLineOK”); and

    4. a cost function COST(p) that gives the cost of determining if a proposition p from U is true or false.

  2. The system is able to diagnosis single, double, or triple faults. It repeatedly determines the least-costly possible diagnosis, and makes observations to see if that diagnosis holds. Note that any particular unknown proposition need only be observed at most once.

Be as concise as possible. Specify the data structures and operations in high-level terms, as long as it is clear exactly how your algorithm operates.

2. First-order Logic and Ontologies


In this exercise you will write an ontology in first-order logic for a fragment of your knowledge of how computer systems work. Then, you will give a resolution refutation proof of some theorems that follow from this knowledge base.


(2.1)

Objects in the domain include specific files, computers, and URL’s. There is a hierarchy of file types, and various relationships between files and computers. You will have to make choices regarding the way your represent your knowledge. In any case you must be consistent in the axioms (first-order formulas) you write: for example, do not use a symbol in one place as a predicate and another place as a function. Write axioms to represent (at least) the following knowledge. Some of these statements may require several axioms to represent.


  1. Computers are all PC, Mac, or Unix systems.

  2. Files are either data files or program files. Graphics files are kinds of data files. Browsers are a kind of program.

  3. Programs include Netscape, IE (Microsoft Internet Explorer), Ghostview, and Acrobat. Netscape and IE are browsers.

  4. The subtypes of graphic files are gif, jpeg, ps (postscript), and ppt (Powerpoint).

  5. A copy of IE is installed on all PC’s, and a copy of Netscape on all Macs and Unix systems.

  6. Netscape and IE can both interpret gif and jpeg files.

  7. IE can interpret ppt files.

  8. Ghostview can interpret ps files.

  9. A computer can display a file if a program that can interpret the file is installed on the computer, and the file is accessible from the computer.

  10. A file is accessible from a computer if the file is installed on the computer, or if the file has a URL and a browser is installed on the computer.


Next, represent the following facts:

  1. The file “vacation.jpg” is installed on Bill’s computer.

  2. John’s computer is a PC, and has a copy of Ghostview installed.

Now, prove the following theorems:


(2.2) Bill’s computer can display the file vacation.jpg.


(2.3) John’s computer can display any graphics file that has a URL.


(2.4) Axiomatize some other fragment of knowledge of your choice about the way computers work with files. Include both the English gloss and the logical form for at least four formulas.