EECS 3401 3.0 Intro to AI and LP Fall 2018
Dept. of Electrical Eng. & Computer Sci. York University
Assignment 3
Total marks: 110.
Note: Your report for this assignment should be the result of your own individual work. Take care to avoid plagiarism (“copying”). You may discuss the problems with other stu- dents, but do not take written notes during these discussions, and do not share your written solutions.
1. [40 points] Consider the following example:
Metastatic cancer is a possible caue of a brain tumor and is also an expla- nation for an increased total serum calcium. In turn, either of these could cause a patient to fall into an occasional coma. Severe headache could also be explained by a brain tumor.
a) Represent these causal links in a belief network. Let a stand for “metastatic can- cer”, b stand for “increased total serum calcium”, c stand for “brain tumor”, d stand for “occasional coma”, and e stand for “severe headaches”.
b) Give an example of an independence assumption that is implicit in this network. c) Suppose that the following probabilities are given:
Pr(a) = .2 Pr(b|a)=.8 Pr(c|a)=.2 Pr(e|c)=.8 Pr(d|b,c)=.8 Pr(d|b,c ̄)=.8
P r ( b | a ̄ ) = . 2 Pr(c | a ̄) = .05 P r ( e | c ̄ ) = . 6 Pr(d| ̄b,c)=.8 P r(d | ̄b, c ̄) = .05
and assume that it is also given that some patient is suffering from severe headaches but has not fallen into a coma. Calculate the joint probabilities for the eight remaining possibilities (that is, according to whether a, b, and c are true or false).
d) According to the numbers given, the a priori probability that the patient has metastatic cancer is .2. Given that the patient is suffering from severe headaches but has not fallen into a coma, are we now more or less inclined to believe that the patient has cancer? Justify your answer.
1
Out: November 21
Due: December 4 at 23:59
2. [70 points]
a) DevelopaPrologimplementationofasituationcalculusactiontheoryforShakey’s world as described in Exercise 10.4 of the Russell and Norvig 3rd edition text- book (also appearing as Exercise 11.13 in the 2nd edition of the book). Use the primitive action names that appear in the exercise. For the fluents, use RobotLoc(location, situation), meaning that the robot is at location in situ- ation s, BoxLoc(box, location, situation), meaning that box is at location in situation s, OnT op(box, situation), meaning that the robot is on top of box in situation s, Up(switch,situation), meaning that switch is up in situation s, and LightOn(light, situation), meaning that light is on in situation s. Also, use the non-fluent predicates In(location, room) and Controls(switch, light), and possibly others to specify the types of entities in the domain, e.g. IsBox(b). Write a precondition axiom for each action and a successor state axiom for each fluent. Also write axioms describing the initial state pictured in Figure 11.17. Assume there is a light in each room (except the corridor), and that it is on if the switch is up. For the initial location of the robot, use a constant such as locInitRobot, and similarly for the boxes and switches. There is an exam- ple Prolog implementation of a situation calculus action theory for an “elevator control” application domain on the course web site.
b) Suppose that we want to achieve the goal of having Box2 in Room2. Express this goal as a situation calculus sentence. Also write a ground situation term that represents a plan that achieves this goal when executed in the initial state of Figure 11.17. Use your Prolog implementation of the action theory in a) to confirm that the plan is executable (legal) and achieves the goal.
c) Write a Golog program that represents the plan in b) and show that it can be executed successfully. Use the Golog interpreter on the course web site.
d) Write a Golog procedure allLightsOn that can be executed to turn on all the lights. The procedure should always terminate successfully and should succeed in turning on all the lights as long as a there is a box in some room that can be used by the robot to reach the switch. Run your procedure and show that it can be executed successfully in the initial situation of Figure 11.17 and that all the lights are on in the resulting situation. Your code should define subprocedures as appropriate and not be unnecessarily complex.
(e) Use the Golog iterative deepening planning procedure (in the Golog interpreter file) to generate a plan to achieve the goal of having Box2 in Room2. For the search procedure to find a solution, you will have to define the forward filtering fluent Acceptable(a, s) appropriately. Try using the following task- specific heuristics: i) until the robot is at the location of Box2, go is the only
2
acceptable action, and ii) once the robot is at the location of Box2, push of Box2 is the only acceptable action.
Document your code appropriately.
To hand in your report for this assignment, submit your answers to question 1 as a pdf file and your code and test results for question 2 electronically. To submit electronically, use the following Prism lab command:
submit 3401 a3 a3q1.pdf a3q2.pl a3q2tests.txt
Your Prolog code should work correctly on Prism.
You may also submit your answers to question 1 on paper. In this case, use the EECS
3401 drop box in the LAS building.
3