1994 Qual Programming Question

This document discusses the Lisp programming question for the 1994 Ph.D. Qualifying Exam in Artificial Intelligence, given at the Institute for the Learning Sciences. You should first read the question below and try to do the problem yourself. If you want to put yourself in the position of the students who took the qual, give yourself one hour.

After doing the problem, read an analysis of the problem. This will help you "grade" your solution.

Finally, for comparison purposes, you can look at my solution. It was not done in an hour.


Congratulations! You've been hired to help build UGH (the Ultimate GBS Helper), a tool for making simple investigate goal-based scenario systems. An investigative GBS has the following standard structure:

The student has to determine which of several possible outcome actions to do, by doing a series of probes (experiments, explorations, etc.) to gather evidence for some hypothesis about what's going on in the scenario.

For example, in a sickle cell counselor GBS, there are:

Each probe yields a particular result, and each result is evidence for or against one or more hypotheses. A key issue in such a GBS is noticing when the student selects an outcome action that is either unjustified by or inconsistent with the results of the probes done so far.

Your job

Your job is to write the module that keeps track of the student's probes and the hypotheses they affect. Other parts of the UGH system will handle the interface and deciding how to respond if the student selects an unjustified or inconsistent outcome action.

The UGH group has already defined some simple representations for the sickle cell application to help you design your module.

(setq *possible-facts*
   `((husband-has-disease husband-has-trait husband-ok)
     (wife-has-disease    wife-has-trait    wife-ok)
 

*possible-facts* holds a list of lists of facts. Exactly one fact in each set has to be true.

(setq *probe-results*
   `((look-husband-blood
       (husband-sickle-blood husband-has-disease)
	  (husband-round-blood husband-has-trait)
	  (husband-round-blood husband-ok))
	(electro-husband-blood
	  (husband-trait-sign husband-has-disease)
	  (husband-trait-sign husband-has-trait)
	  (husband-no-trait-sign husband-ok))
      ...
	))
 

*probe-results* says how facts affect probe results. Each item in the list is the name of a possible probe action, followed by lists of results and the facts that have to be true for that result to occur. Although it doesn't occur here, if a particular result is followed by several fact names, that means that all those facts have to be true for a particular result to occur. Notice that the same result, e.g., seeing round blood cells, may occur for more than one reason--that's what makes investigations tricky! The remaining items in the above list, for looking at the wife's blood, should be obvious.

(setq *scenario* `(husband-has-trait wife-ok))

A scenario is just a consistent set of true facts. In this scenario, the husband has the sickle cell trait, but the wife has neither the disease nor the trait.

Specify the design (and as much implementation as you have time for) for the following functions:

The UGH group is working under tight memory constraints. There's no room for loading some constraint maintenance package. You have to do all this in regular Common Lisp.

Since you may be taken off the project at any time, even at an hour's notice, describe your algorithms well enough so that another programmer could take over.

As you do this, you should also comment on any flaws (fatal or inconvenient) that you see in the above scheme. Are there kinds of evidential relationships between results and hypotheses that can't be represented? Are there kinds of justification relationships between hypotheses and outcome actions that can't be represented?