B551 Elements of Artificial Intelligence - Fall 2008

Reasoning Logically

Logic gives a framework for expressing world knowledge and applying it in a uniform, well-understood way. However, going from text or world situations to encode the needed knowledge can be difficult. Do the questions, being sure to note any assumptions you make:

• Russell and Norvig 7.8 d, e
• Russell and Norvig 8.6 a, b, d, j

Reasoning Under Uncertainty

1. One motivation for medical expert systems is that medical professionals may draw sub-optimal conclusions based on intuitive reasoning that ignores probability theory. For example, say Mary is given test T for disease X, and the test result is positive. If test T has a false positive rate of .2%, a the doctor might tell her that there is a 99.8% chance she has disease X. This sounds reasonable but may be wildly wrong! Before reading further, think about why (you don't need to hand in the reason that you come up with).

   Using Bayes' theorem, find the correct probability that Mary has X, assuming (1) the false positive rate is correct, (2) that the probability of a positive test, given that a person has X, is .999, and (3) that the prior probability of disease X is .0002.

   Note: The false positive rate is the percent of positive tests results expected when the test is given to people who do not have the disease, i.e., P(positive test result| do not have disease).

2. An eccentric benefactor presents you with three boxes, one of which contains a diamond, and tells you that you can keep the diamond if you guess the right box. The benefactor asks you to guess which box contains the diamond, and you do so and tell the benefactor.

   The benefactor doesn't yet let you open the box to see if the diamond is inside. Instead, the benefactor uses knowledge of where the diamond actually is to pick an empty box that you did not pick, and opens that empty box to show you that it is empty. The benefactor then asks you if you would like keep your guess that the diamond is in the box you picked earlier, or to switch and guess that the diamond is in the other closed box.

   Does it benefit you to switch? Substantiate your answer by using Bayes' theorem to decide the probabilities of each closed box containing the diamond, after you have picked a box and the benefactor has shown you that one of the other boxes is empty. Explain your application of Bayes' theorem, and then give a common-sense justification of your answer.

   Note: This is a classic problem that will challenge your intuitions, so after deriving the answer you might want to test it experimentally. If you do so and your original answer turns out to be wrong, you may change your answer before submitting it, but also think about why you went wrong.

Planning as Search Through Situations

1. In class we discussed the need for guidance for planning as search through situations. Pick a simple planning domain not discussed in class or the texbook, and sketch how you would define a heuristic function for estimating distance to a goal? (An intuitive description is fine.) Does your heuristic sometimes misjudge distance? If so, give an example. If not, explain why not.
2. Would there be difficulty representing the needed considerations in a form which could be handled by a first-order predicate calculus reasoner? Explain your answer.

Handing in the assignment

You may either hand this in as hard copy in class, or electronically as a pdf file, using Oncourse. If you hand it in electronically, you may either express quantification, etc., with the normal symbols (e.g., generating your pdf with LaTeX), or may use scheme-like notation, for example, (forall (x) ...), (not ...), ...