Department of Computer Science
1.
COMPSCI 367 Artificial Intelligence Assignment 2 due October 9, 2016 Note: Please submit your assignment via the CS Assignment Dropbox by 23:59 on the due
date. Late assignments will not be marked.
The total mark for this assignment is 50. This assignment counts towards 15% of your final
mark.
The work done on this assignment must be your own work. Think carefully about any problems you come across, and try to solve them yourself before you ask anyone else for help. Under no circumstances should you work together with another student on any code used in this assignment.
[25 marks] Figure 1 shows a depiction of an electrical distribution system in a house. In this house, power comes into the house through circuit breakers and then it goes to power outlets or to lights through light switches. For example, light l1 is on if there is power coming into the house, if circuit breaker cb1 is on, and if switches s1 and s2 are either both up or both down. This is the sort of model that normal householders may have of the electrical power in the house, and which they could use to determine what is wrong given evidence about the position of the switches and which lights are on and which are off. The diagnostic assistant is there to help a householder or an electrician troubleshoot electrical problems.
Figure 2 shows the resulting belief network after the independence of each variable has been considered. The belief network also contains the domains of the variables, as given in the figure, and conditional probabilities of each variable given its parents.
• For each wire wi, the variable Wi has domain {live, dead}, which denotes whether there is power in wire wi. Wi = live means that wi has power, while Wi = dead means that wi has no power.
• The variable Outside power with domain {live, dead} denotes whether there is power coming into the system.
• For each switch si, the variable Si pos denotes the position of si with domain {up, down}.
• For each switch si, the variable Si st denotes the state of switch si with domain
{ok, upside down, short, intermittent, broken}.
– Si st = ok means switch si is working normally.
– Si st = upside down means switch si is installed upside-down.
– Si st = short means switch si is shorted and acting as a wire.
– Si st = intermittent means switch Si is working intermittently.
– Si st = broken means switch si is broken and does not allow electricity to flow.
• For each circuit breaker cbi, the variable Cbi st has domain {on,off}. Cbi st = on means power can flow through cbi and Cbi st = off means that power cannot flow through cbi
COMPSCI 367 Artificial Intelligence Assignment 2 Page 1 of 4
• For each light li, the variable Li st with domain {ok,intermittent,broken} denotes the state of the light. Li st = ok means that li will light if powered, Li st = intermittent means that light li intermittently lights if powered, and Li st = broken means light li does not work.
• For each light li, the variable Li lit has domain {true,false} Questions:
(a)
[5 marks] Download all the input data (.csv) from the course website. Build a function genBSFromCSV(filepath) using the gRain package.
• Define a conditional probability distribution for each variable in the belief network using the corresponding .csv file.
• Build a dependency formula using dependencies.csv (this is required by cptable()).
• Specify the domain of each random variable in cptable() using domain.csv.
• Your function should output the belief network, i.e., if you call the function class
on the output of your function, you should get CPTgrain grain.
[5 marks] Build a function query(list h, list e) based on the belief network, where
list h is a list of hypothesis and their values, list e is a list of evidences and their values. • You may implement the function using any tools provided by gRain.
• Your function should output the required posterior probability.
[5 marks] Implement a function queryReason(list evidence) to compute a most proba- ble reason that L1 lit is false, while S1 st = ok,S2 st = ok,L1 st = ok and W0 ···W3 = live using the last function. The output should be a random variable with a corresponding val- ue, and the probability of the variable having this value.
[10 marks] Implement the variable elimination (VE) algorithm to compute the posterior probability of L1 lit = false given S1 st = ok,S2 st = ok,L1 st = ok and W0 · · · W3 = live (using the operations for data frames)
• Implement all steps in the file problem1.r.
• You MUST comment your program to indicate each step of the VE algorithm.
(b)
(c)
(d)
2.
Submission: You should put all the answers for this problem in a single R script file named problem1.r. You should use comments to indicate and separate each sub-question. Do NOT change the names of any function provided in the questions.
[25 marks] Deep Space One (DP1)(http://www.jpl.nasa.gov/nmp/), a spacecraft launched by NASA in October 1998, used AI technology for its diagnosis and control. Figure 3 depicts a part of the actual DS1 engine design. To achieve thrust in an engine, fuel and oxidizer must be injected. The whole design is highly redundant to ensure its operation even in the presence of multiple failures (mainly stuck or inoperative valves).
Now you are going to build a belief network model to help diagnose DS1. (Note that whether the valves are black or white, and whether or not they have a bar are irrelevant for this assignment.)
To build your belief network, you may have to consider the following scenarios:
COMPSCI 367 Artificial Intelligence Assignment 2 Page 2 of 4
Figure 1: An electrical system in a building.
• Valves can be open or closed.
• A valve can be ok, in which case the gas will flow if the valve is open and not if it is closed; broken, in which case gas never flows; stuck, in which case gas flows independently of whether the valve is open or closed; or leaking, in which case gas flowing into the valve leaks out instead of flowing through.
• There are three gas sensors that can detect gas leaking (but not which gas); the first gas sensor detects gas from the rightmost valves (v1,…,v4), the second gas sensor detects gas from the center valves (v5,…,v12), and the third gas sensor detects gas from the leftmost valves (v13, …, v16).
Questions:
(a)
(b) (c)
[12 marks] Build a belief network representation of the domain. You only must consider the topmost valves (those that feed into engine e1). Make sure there are appropriate probabilities (you need to assign probabilities yourself). Illustrate your belief network using a directed graph.
• Nodes are conditional tables of the random variables.
• Directed edges should be drawn between tables to indicate dependencies between the
random variables.
[8 marks] Create a data profile (using .csv files, similar to Problem 1) for your belief network.
[5 marks] Compute the following queries using the .csv files and the functions that you have built in Problem 1.
COMPSCI 367 Artificial Intelligence Assignment 2 Page 3 of 4
Figure 2: The belief network of the electrical system.
• Given that the first sensor detects leaking, what is the probability that e1 thrusts?
• Given that all the sensors detects leaking, what is the probability that e1 thrusts?
• Given that v5, v8 = closed and the second sensor detects leaking, what is the proba- bility that e1 thrusts
Submission:
• You should put your answer to (a) in a PDF document named Problem2a.pdf.
• You should put all R programs in a single R script file named problem2.r. Please use
comments to indicate and separate each question clearly.
• In addition, for (b), you need to store all your .csv files in a folder named “data”. For each .csv file, the file name should be the name of a random variable. A row name in a .csv file should be an assignment of a random variable and its parent random variable. Then submit a package named problem2.zip that includes all files for this question.
COMPSCI 367 Artificial Intelligence Assignment 2 Page 4 of 4
Figure 3: Deep Space 1
COMPSCI 367 Artificial Intelligence Assignment 2 Page 5 of 4