Please complete every point very detailed, for example part 1-do the 4 points marked, part -complete the table, part 3-complete the table and answer question 1, 2 and 3..part 4-answer the questions 1,2,3,4, and 5....part 5-answer the 3 points and part 6-answer the questions 1,2,3,4,5 and 6.
Figure 1 Question 1 [3 pts]: Figure 1 shows a robot navigation field, where the red square (d2) is the robot, and green square (b7) is the goal. The shade squares (such as b2, c2, etc.) are obstacles. The robot is not allowed to move in diagonal line. Node are coded using an alphabet letter followed by a digit (such as a0, b1, b2 etc.). When two sibling nodes are inserted into fringe (queue), use deque order to favor node with a lower alphabet and a lower digit. For example, if d1 and e2 are sibling nodes, d1 will be dequeued first (because “d” has a lower alphabetic order than “e”). If a1 and a2 are sibling nodes, a1 will be dequeued first (because “1” has a lower digit than “2”). Node expanded/visited does not need to be revisited. • Use Depth First Search (DFS) to find path from d2 to b7. o Report nodes in the fringe in the orders they are included in the fringe. [0.25 pt] o Report the order of the nodes being expanded. [0.25 pt] o Report the final path from d2 to b7. [0.25 pt] • Use Breadth First Search (BFS) to find path from d2 to b7. o Report nodes in the fringe in the orders they are included in the fringe. [0.25 pt] o Report the order of the nodes being expanded. [0.25 pt] o Report the final path from d2 to b7. [0.25 pt] • Use Best First Search to find path from d2 to b7 (Using Manhattan distance as the heuristic function) o Report nodes in the fringe (including their f(N) values) in the orders they are included in the fringe. [0.25 pt] o Report the order of the nodes being expanded. [0.25 pt] o Report the final path from d2 to b7. [0.25 pt] • Use A* to find path from d2 to b7 (Using Manhattan distance as the heuristic function). o Report nodes in the fringe (including their f(N) values) in the orders they are included in the fringe. [0.25 pt] o Report the order of the nodes being expanded. [0.25 pt] o Report the final path from d2 to b7. [0.25 pt] DFS Fringe: Node visited/expanded BFS Fringe: Node visited/expanded Best First Search Fringe: f(N)=g(N) Node visited/expanded A* Search Fringe: f(N)=h(N)+g(N) Node visited/expanded Question 2 [1 pt]: Figure 2 shows a Bayesian network. Assume x ⊥ y denotes that x are independent of y, and x ⊥ y | z denotes that x and y are conditionally independent, given z. Complete Table 1, and use to mark correct answers. [1 pt] Figure 2 Table 1 (must use to mark correct answers) Relationship True False A⊥B A⊥B | C A⊥H A⊥H | E E⊥F | H E⊥F | C A⊥F | C C⊥G | H A⊥E| C C⊥D|B Question 3 [2 pts]: Table 2 shows joint probability distributions between three random variables A, B, and C, with respect to observed values (each has binary values T or F). Table 2 A B C P(A, B, C) F F F 0.2 F F T 0.05 F T F 0.2 F T T 0.05 T F F 0.1 T F T 0.15 T T F 0.1 T T T 0.15 (1) Calculate probability value P(A=T), using only variables showing in Table 2. [0.5 pt] (2) Calculate probability value P(A=F | B = T), using only variables showing in Table 2. [0.5 pt] (3) Are A and B independent or not? Explain your answer? [1 pt] Question 4 [3 pts]: A company intends to build a quality control system to automatically determine whether a product, such as an engine, coming off an assembly line is “bad” or “good”. In order to make the decision, the company observed that three features are mostly relevant to the quality of the product: • Wobbly: the engine may be wobbly (which can be detected from a motion sensor); • Rumbly: the engine may be rumbly (which can be detected from a sound sensor), and • Hot: the engine may be overheated (which can be detected from a heat sensor). Each of the above sensors gives a Boolean observation: “true” or “false”, and an engineer formulates the problem using the following variables and domains: Decision: B {bad, good} Evidence: W, R, H {true, false} The engineer wants to use a Naive Bayes (NB) classifier for making the automatic decision, and builds an NB classifier which predicts whether a product is “bad” or “good” (1) Using Naïve Bayes assumption, draw Bayesian network of the classification model (including all evidence and decision in the network) [0.5 pt]. (2) Using Naïve Bayes assumption, write formula to calculate joint probability of the Bayesian network, i.e., P(B, W, R, H), using symbols B, W, R, H. [0.5 pt] (3) Using naive Bayes assumption, please write an expression of posterior probability of P(B|W, R, H) using probabilities of the forms P(B), P(W|B), P(R|B), and P(H|B) [0.5 pt]. (4) Explain how to use P(B|W, R, H) to determine whether a product is “bad” or “good” [0.5 pt] (5) The engineer has observed several engines which recently came off the assembly line. Based on these observations, suppose a new engine is observed to have the following feature values: W=false, R=true, H=false. What prediction will the naive Bayes classifier make: bad or good? Please justify the answer [1 pt] Question 5 [3 pts]: Givin following sentences, (1) Those who love all dogs are loved by someone (2) Those who kill dogs are loved by no one. (3) Henry loves all animals (4) Dog is an animal (5) Either Sam or Henry killed the dog, whose name is Pluto. Prove that Sam killed the dog. Using following defined predicates/variables: D(x) x is a dog Animal(x) x is an animal Love(x,y) x loves y (equivalently, y is loved by x) K(x,y) x kills y Sam Sam Henry Henry Pluto Pluto • Using first order logic to express each sentence [1 pt] • Converting each sentence to clause format [1 pt] • Using Unification and resolution to prove that Sam killed the dog [1 pt] Question 6 [3 pts]: Figure 3.a shows a 4x4 robot navigation field. The shade squares are obstacles, and the two cells [4,2] and [4,3] are terminal states, and the values showing are the reward of the terminal states (each cell is also a state). The reward for each of the rest states (except the obstacles) is -0.05. In order to train a robot to navigate in the field, a stochastic transition model showing in Figure 3.b is used. At any particular location, say [1,1], if the robot cannot move in a certain direction (e.g., there is wall or obstacle), it will remain in the same position. For example, when the robot is at [1,1], it cannot move to the left because of the wall. The discount =1, and the initial utility values of each state are 0. Figure 3.a Figure 3.b (1) What is the meaning of the transition model showing in Figure 3.b [0.25 pt] (2) What are the objective of using such as transition model (with stochastic process) for learning [0.25 pt] (3) Use value iteration algorithm to find all cells’ utility values after the FIRST iteration (exclude terminal states and obstacles). Solutions must show calculations for cells [3,1], [3,2], [3,3], [3,4], [4,1] and [4,4], respectively. For remaining cells, you can just report their results [1 pt] (4) Use value iteration algorithm to find all cells’ utility values after the SECOND iteration (exclude terminal states and obstacles). Solutions must show calculations for cells [3,1] [3,2], [3,3], [3,4], [4,1], and [4,4], respectively. For remaining cells, you can just report their results [1 pt] (5) Why the reward for the non terminal states (except the obstacles) are set as a small negative value (such as -0.05)? [0.25 pt] (6) If the reward for each of the rest states (except the obstacles) is -2, how would robot behave during the learning process, comparing to the reward -0.05, and explain why [0.25 pt]