CPSC422 Spring 2007
Assignment 4

Due: 2:00pm, Thursday 12 April 2007.

The aim of this assignment is to learn more meta-interpreters and abduction.

Please read and post to the bulletin board in the course WebCT site for hints on how to solve these problems.

This assignment is optional. If you do it, it can replace the mark of your lowest assignment. If you don't do it, you can spend more time on your project. The exam, however, will assume that you know the material in this assignment.

You can get CILog from http://www.cs.ubc.ca/spider/poole/ci2/code/cilog/CILog2.html.

Question 1

Write a meta-interpreter in Prolog for the CIlog language (using <- for implication and & for conjunction) that allows for assumables. Your program should find the minimal sets of assumables that imply a goal (and in particular the minimal conflicts) using iterative deepening on the number of assumables.

Question 2

The following question can either be done in CILog, or using the meta-interpreter you wrote from question 1.

The following picture shows a simplified redundant communication network between an unmanned spacecraft (sc) and ground control centre (gc). There are two indirect high bandwidth (high gain) links which are relayed through satellites (s1, s2) to different ground antennae (a1, a2). Furthermore, there is a direct, low bandwidth (low gain) link between the ground control centre's antenna (a3) and the spacecraft. The low gain link is affected by atmospheric disturbances, it works if there are no disturbances (no_dist) and the spacecraft's low gain transmitter (sc_lg) as well as antenna 3 a3 are ok. The high gain links always work if the spacecraft's high gain transmitter (sc_hg), the satellites' antennae (s1_ant, s2_ant), the satellites' transmitters (s1_trans, s2_trans), and the ground antennae (a1, a2) are ok.

To keep matters simple, just consider messages from the space craft going through these channels to the ground control centre.

Suppose we have the following predicates:

• alive(sc) that is true if sc is alive
• ok(C) that is true if component C is functioning normally. The components that we model are sc_lg, sc_hg, s1_ant, s2_ant, s1_trans, s2_trans, a1, a2, a3.
• send_signal_lg(sc) is true if the spacecraft sends a low-gain signal.
• send_signal_hg(sc) is true if the spacecraft sends a high-gain signal.
• get_signal(S) is true if satellite S gets a signal from the spacecraft.
• send_signal(S) is true if satellite S sends a signal to Earth.
• get_signal(gc) is true if ground control gets a signal from the spacecraft.
• no_dist is true if there is not atmospheric disturbance.

1. Write a set of clauses that model the story above.
2. Ground control is worried, because they haven't received a signal from the spacecraft (no_signal(gc)). They know for sure that all ground antennae are ok (i.e., ok(a1), ok(a2) and ok(a3)) and satellite s1's transmitter is ok (ok(s1_trans)). They are not sure about the state of the spacecraft, it's transmitters, the satellites' antennae, s2's transmitter, and atmospheric disturbances.

   Specify a set of assumables and an integrity constraint which model the situation.

3. Using the assumables and the integrity constraints from (b), what is the set of minimal conflicts?
4. What is the set of minimal consistency-based diagnoses?

Question 3

This question explores using abduction for the domain of question 2.

Suppose that an atmospheric disturbance dist could produce static or no signal in the low bandwidth signal. To receive the static, antenna a3 and the spacecraft's low bandwidth transmitter sc_lg must be working. If a3 or sc_lg aren't working or sc is dead, there is no signal. Specify the rules and assumables that need to be added to the knowledge base of question 3 so that we can explain the possible observations no_signal(gc), get_signal(gc) or static(gc)? You may ignore the high bandwidth links. You can invent any symbols you need.

Show that it works in CILog 2.

Question 4

[Note that this question is worth marks, so don't forget to do it.]

1. For each question and each part in this assignment, say how long you spent on it. Was this reasonable? What did you learn?
2. Tell us every person you discussed this with (including the TA and fellow students), and every external source (e.g., web site, research paper, book) you referenced to do this assignment.