Please answer all the questions , tables
Question 3 CAP 6635 Artificial Intelligence (2022 Spring) Question 1. [5 pts] A robot agent is exploring a field and wants to travel from “Start” to “Goal”. The state graph is shown in Figure 2. Figure 1 The available actions at each state are denoted by arrows with a path cost label above each arrow. For each of the following graph search strategies, list the Fringe structure, the order of the states which are expanded in the fringe (using table provided for each method), as well as the path returned by graph search (states are expanded only once and break the tie in favor the state with a lower alphabetical order). (a) Breath First Search (1 pt) Fringe: Node visited/expanded Path to reach the Goal state: (b) Depth First Search (1 pt) Fringe: Node visited/expanded Path to reach the Goal state: (c) Uniform-Cost Search with the step cost marked above each arrow (1 pt) Fringe: Node visited/expanded Path to reach the Goal state: (d) Best First Search using f(N)=h(N), with the heuristic values listed inside each node (1 pt) Fringe: Node visited/expanded Path to reach the Goal state: (e) A* Search using the heuristic values listed inside each node (1 pt) Fringe: Node visited/expanded Path to reach the Goal state: Figure 2 Question 2 [6 pts] Figure 2 shows a robot navigation field, where the red square (d2) is the robot, and green square (c7) is the goal. The shad 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 to find path from d2 to c7. · Report nodes in the fringe in the orders they are included in the fringe. [0.5 pt] · Report the order of the nodes being expanded. [0.5 pt] · Report the final path from d2 to c7. [0.5 pt] · Use Breadth First Search to find path from d2 to c7. · Report nodes in the fringe in the orders they are included in the fringe. [0.5 pt] · Report the order of the nodes being expanded. [0.5 pt] · Report the final path from d2 to c7. [0.5 pt] · Use Best First Search to find path from d2 to c7 (Using Manhattan distance as the heuristic function) · Report nodes in the fringe (including their f(N) values) in the orders they are included in the fringe. [0.5 pt] · Report the order of the nodes being expanded. [0.5 pt] · Report the final path from d2 to c7. [0.5 pt] · Use A* to find path from d2 to c7 (Using Manhattan distance as the heuristic function). · Report nodes in the fringe (including their f(N) values) in the orders they are included in the fringe. [0.5 pt] · Report the order of the nodes being expanded. [0.5 pt] · Report the final path from d2 to c7. [0.5 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 3 [2 pts]. In the game tree showing in Figure 3, assume ( denotes a Max node and ( denotes a Min node. Please show utility values for each node (1 pt). Pleas also mark the nodes which are pruned by the (-( pruning method (1 pt) Figure 3 Question 4 [3 pts]: Figure 4 shows the Wumpus world game, where the agent starts from location [4,4], and does not sense breeze or stench. After the agent enters [4,4], it moves to [4,3] and senses a “Breeze”. Then the agent travels back to [4,4], and then moves to [3,4]. At location [3,4], the agent senses a “Stench”. · Please use propositional logics to write sentences to describe the observations and rules & backgrounds (after agent travels from location [4,4]->[4,3] ->[4,4] -> [3,4], and only consider Pit and Wumpus). (1 pt) · Please use resolution to derive that there is no Pit at location [3,3] and there is no Wumpus at location [3,3]. In other words, prove that KB ╞ ( P3,3 and KB ╞ ( W3,3 (2 pts) Figure 4 Question 5 [4 pts] Givin following sentences, (1) Allergy causes running nose (2) Not all people are allergic to dogs (3) People allergic to dogs will develop allergy (4) Oscar is a dog (5) Daisy is allergic to Oscar Prove that Daisy will develop running nose (i.e., prove RN(Daisy)). Using following defined predicates/variables: D(x) x is a dog RN(x) x has a running nose A(x) x has an allergy A2(x,y) x is allergic to y Oscar Oscar Daisy Daisy (1) Using first order logic to express each sentence [1 pt] (2) Converting each sentence to clause format [1 pt] (3) Using Unification and resolution to prove that Daisy will develop running nose [2 pts]