Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Faculty of Science

COMP-424: Artificial Intelligence (Winter 2017)

Midterm Examination

Question 1: Search [6 points]

Consider the search problem represented by this graph, in which nodes represent locations and edges represent possible paths between them. Edge weights correspond to the cost of traversing between the nodes attached to that edge. The start node is A and the goal node is E.

a) What is the order of the nodes visited by a depth-first search algorithm? Assume that the algorithm breaks ties by visiting nodes in alphabetical order.

b) Consider the following heuristic function h(x) = {A:3, B:4, C:1, D:1, E:0, F:7}

What is the order of the nodes visited by the A* search algorithm?

c) Is the heuristic admissible? Explain your answer. If so, indicate one change in the heuristic function that would make the heuristic inadmissible. If not, indicate changes in the heuristic function that would make the heuristic admissible.

Question 2: Constraint Satisfaction [14 points]

The following is a CSP with 3 variables: X, Y, and Z.

Dom(X) = {1, … , 10} (i.e., integers between 1 and 10, inclusive)

Dom(Y) = {5, … , 15} (i.e., integers between 5 and 15, inclusive)

Dom(Z) = {5, … , 20} (i.e., integers between 5 and 20, inclusive)

Subject to constraints:

X > Y

Y + Z = 12

X + Z = 16

a) Draw the constraint graph.

b) Apply arc-consistency repeatedly so that the constraints are generalized arc-consistent. State the updated domain of each variable.

c) Show the search tree generated by applying backtracking search on the reduced domain you got from part b), without forward checking. Clearly show the domain of each variable at every point in the search.

d) Show the search tree generated by applying backtracking search on the reduced domain you got from part b), with forward checking. Clearly show the domain of each variable at every point in the search.

Question 3: Game Playing [10 points]

Suppose we have the following game search tree.

a) Circle the nodes, including the terminal leaf nodes, which are visited in a minimax search algorithm that uses alpha-beta pruning (ordering nodes from left to right). Cross out each edge that leads to a subtree that is pruned.

b) Which action should the MAX player take according to minimax strategy, D or H?

c) Explain why your answer in part b) may not be optimal if the MIN player does not play according to the same minimax strategy by providing a counterexample.

Question 4: Logic [12 points]

Consider the following Knowledge Base (KB):

1. Every wug is a dreck.

2. John owns a wug called Goo.

3. No linguist harms a dreck.

4. Every wug owner is a linguist.

a) Write the four sentences above in First-Order Logic, using constants John, Sherry, Goo, and predicates Wug(x) [x is a wug], Dreck(x) [x is a dreck], Linguist(x) [x is a linguist], Owns(x, y) [x owns y], and Harms(x, y) [x harms y].

b) Convert sentence 4 above into Conjunctive Normal Form.

c) Give an interpretation with at least two domain elements in which the above set of sentences is true.

d) Give an interpretation with at least two domain elements in which the above set of sentences is false.

Question 5: Planning in the Observable Wumpus World [8 points]

Recall the Wumpus World that we discussed in the lecture. Here are the rules of the Wumpus world:

 The cave is a 4x4 grid, with exterior walls and no interior walls.

 A cell may have a pit, gold, or a Wumpus.

 The cave has exactly one gold and one Wumpus.

 Cells directly adjacent to a Wumpus have a Stench.

 Cells directly adjacent to a pit have a Breeze.

 The hero has the following actions available: MoveAhead, TurnLeft, TurnRight, FireArrow, and GrabGold

 The hero has one arrow which can be fired in a straight line.

Suppose that our hero is clever and has brought a map of the Wumpus cave, so that the environment is now fully observable.

a) How many physical states are there in the game? Be sure to account for all relevant aspects of the hero and of the environment that can be altered by the hero. You can just write out the expression as a product. There is no need to evaluate it to a single number.

b) Give a STRIPS or PDDL action schema representation for the operator FireArrow. The action should only be applicable when the hero is facing the Wumpus and has an arrow in stock. Assume you have access to a predicate WumpusAhead(), which returns true iff the hero is facing the Wumpus. Define and explain any other predicates that you use.

Question 6: Short Answer [10 points]

For each of the following sentences, circle exactly one response from the choices in the parentheses to make the statement true.

a) In uninformed search methods, the size of the search tree directly determines the ( time / space / time and space ) complexity of the search.

b) Uniform-cost search is ( optimal / not optimal ) for the case of graph search with a general cost function.

c) Hill-climbing is a special case of simulated annealing with the temperature ( T→∞ / T→0 ).

d) In simulated annealing, taking a random step corresponds to following the strategy of ( exploitation / exploration ).

e) When solving CSPs, a popular heuristic is to assign to a variable with the ( most / fewest ) remaining legal values.

f) Applying a perception function during search under uncertainty typically (increases / decreases / does not affect) the number of states in the belief.

g) In an AND-OR search tree, the ( AND nodes / OR nodes ) corresponds to the case where the agent chooses between multiple possible actions.

h) The default policy is used during the ( descent / rollout / update / growth ) phase in Monte Carlo Tree Search.

i) A logical statement that is ( valid / satisfiable / unsatisfiable ) is necessarily also ( valid / satisfiable / unsatisfiable ). [Choose two different words in each part of this question]

j) ( Generalized modus ponens / resolution ) is a complete inference procedure for first-order logic.