Introduction to AI: Midterm Grading Policy and Sample Solution 1. (10 Points) Agents (Grader: Tao-Hsuan Chang) Critique the following statements. (a) (3 Points) A system must think like a human in order to pass the Turing Test reliably. Grading policy: • (1 point) Argue AGAINST it. • (2 points) Justification. • You should provide at least one reason that is related to system. Sample solution: Against. Instead of thinking like a human, a system can pass the Turing Test if it acts like a human. (b) (3 Points) An agent that senses only partial information about the state cannot be perfectly rational. Grading policy: • (1 point) Argue AGAINST it. • (2 points) Justification. Sample solution: Against. By definition (p.36 in AIMA), an agent is rational as long as it selects an action that is expected to maximize its performance measure for each state. Therefore, an agent can be rational even if it senses only partial information. (c) (4 Points) Utility-based agents are best suited for achieving multiple goals in dynamic environments. Grading policy: • (1 points) Argue FOR or AGAINST it with explanation • (3 points) Justification Sample solution: • For: When there are multiple goals, utility-based agent can possess utility function for each goal, and weight up the utilities based on its preference. Therefore, utility-based agent with multiple goals can still perform rationally in dynamic environment. • Against: Comparing to learning agents, utility-based agent is less flexible for dynamic environment. 2. (20 Points) Problem Solving as Search (Grader: Tao-Hsuan Chang) Consider the search space in Figure 1, where S is the start node and G1, G2, and G3 satisfy the goal test. Arcs are labeled with the cost of traversing them and the estimated cost to a goal is reported inside the nodes. For each of the following search strategies, indicate which goal state (if any) is reached. (a) (3 Points) Iterative Deepening Grading policy: • (3 points) Indicate one correct GOAL with PATH Sample solution: S → A → G1 or S → C → G3 (b) (3 Points) Hill Climbing Grading policy: • (3 points) Indicate one correct GOAL with PATH Sample solution: S → B stop Note: The objective function in local search is used to measure how good a state is. In this problem, it is better to use the estimated cost as the objective function. If you use path cost as the objective function, you have to declare it explicitly. In this case, your answer should be either S → B → C → G3 or S → (B → F → D) loop. 1 Figure 1: Search space. (c) (3 Points) A∗ Grading policy: • (3 points) Indicate one correct GOAL with PATH Sample solution: S → B → F → D → G2 (d) (3 Points) For A∗ , please list, in order, all the states popped off of the OPEN list. When all else is equal, nodes should be removed from OPEN in alphabetical order. Grading policy: • (3 points) Show the list Sample solution: S → B → C → F → D → G2 Note: Multiple nodes popped from OPEN list can be shown twice if the f-cost is reasonable. (e) (4 Points) Consider the evaluation function f (n) = w · g(n) + (1 − w) · h(n) Which search algorithm do you get when w = 0? And, when w = 1? Grading policy: • 2 points for each case Sample solution: • w = 0: it is greedy best-first search. • w = 1: it is uniform-cost search. (f ) (4 Points) Given an admissible heuristic h(n), what range of values should w take to guarantee an admissible search strategy? Justify your answer briefly. Grading policy: • (2 points) 1/2 ≤ w ≤ 1 • (2 points) Justification Sample solution: Define f ′ (n) = f (n)/w = g(n) + (1 − w)/w ∗ h(n) = g(n) + h′ (n), where h′ (n) = 1−w w h(n). A search strategy using f (n) is admissible if and only if a search strategy using f ′ (n) is also admissible. (In A∗ search, the ordering in the fringe would not change if the f-cost is multiplied by a constant.) Since h(n) is admissible, the new heuristic function h′ (n) = (1 − w)/w ∗ h(n) is admissible if and only if 0 ≤ (1 − w)/w ≤ 1. Therefore, 1/2 ≤ w ≤ 1. Note: You will get partial points if you have explanation, at least the meaning of admissibility. 3. (20 Points) Constraint Satisfaction Problems (Grader: Yen-Ling Kuo) Consider the problem of coloring the map of southern European countries as shown in Figure 2 with red, green, and blue, so that any two neighboring countries have different colors. 2 Figure 2: Map of Southern European Countries. (a) (6 Points) Formulate the problem as a CSP by defining the corresponding constraint variables and its constraint graph. Grading policy: • (3 Points) Constraint variables • (3 Points) Constraint graph Sample solution: The coloring problem can be formulated as follows. • Constraint variables: P ortugal(P ), Spain(S), F rance(F ), Holland(H), Belgium(B), Luxembourg(L), Switzerland(SW ), and Italy(I). • Constraint graph: The nodes correspond to the variables defined above. The arcs correspond to the constraints that the neighboring countries should have different colors. (b) (4 Points) Give two instances of how constraint propagation can cut down the search. Grading policy: • 2 points per instance • You will lose 1 point in each instance if you only illustrate the constraint propagation without finding an inconsistency and backtrack. Sample solution: • Consider the partial assignment S = green, L = blue, and H = green. It leaves the only legal value “red” for F . If we assign “red” to F , it will leave no value for B and make an inconsistency. Therefore, we can cut down the search and backtrack. 3 • Similarly, consider the partial assignment L = blue, H = green, and SW = green. It leaves the only legal value “red” for F . If we assign “red” to F , it will leave no value for B and make an inconsistency. Therefore, we can cut down the search and backtrack. (c) (5 Points) Use the example to explain how AC-3 can be further used to improve the search for a solution. Grading policy: • (2 Points) An example of AC-3. • (3 Points) Explain how AC-3 can be used to improve the search. You will get 1 point if you mention that it rechecks the affected arcs. You will get another 2 points if you mention that it may find inconsistency earlier to cut down the search. Sample solution: The AC-3 algorithm uses a queue to keep track of the arcs that need to be checked for inconsistency. It removes the inconsistent value and put the possible affected arcs in the queue to recheck the arc-consistency again. In this way, we can cut down the search by finding inconsistency earlier. Take the first answer in 3(b) for example, and trace through on possible ordering. (We only show some of the arc-checking to demonstrate the result.) • Remove F − S, delete “green” from F because there is no value from the domain of S being consistent with F = green. Insert B − F , L − F , SW − F , and I − F into the queue. • Remove F − L, delete “blue” from F , leaving only “red”. Insert L − B into the queue. • Remove B − L, delete “blue” from B. Insert H − B and F − B into the queue. • Remove B − H, delete “green” from B, leaving only “red”. Insert B − L into the queue. • Remove B − F , delete “red” from B, leaving empty domain for B. (Inconsistency!) In this example, we can use AC-3 to improve the search by finding the inconsistency and backtrack earlier. (d) (5 Points) Please argue for or against the statement that “The map coloring problem with four colors is path consistent.” Grading policy: • (2 Points) Answer: for • (3 Points) Justification Sample solution: For. In the map coloring problem, given the colors of any adjacent countries, we can choose color other than the colors of given countries to assign a consistent color to a third neighboring country since there are four colors. 4. (15 Points) Game Search (Grader: Yen-Ling Kuo) Consider a two-player zero-sum game. Figure 3 shows a 3-ply game tree with the first four nodes visited by minimax search so far. (a) (6 Points) Please complete the minimax search and label all non-leaf MAX/MIN nodes with the alpha/beta bounds respectively. Grading policy: • (1 Point per Node) Alpha/beta bound for each node Sample solution: The final alpha/beta bounds of the game is shown in Figure 4. (b) (4 Points) Circle all nodes in the search tree that will be pruned by alpha-beta during a leftto-right exploration of your tree. Grading policy: • (1 Point per Node) Circle the pruned nodes Sample solution: The red circled nodes in Figure 4 can be pruned by alpha-beta pruning. (c) (5 Points) Reorder your branches to maximize the number of nodes that can be pruned. Write the re-ordered list of values from left to right. Grading policy: 4 Figure 3: Minimax search with Alpha Beta pruning on a game tree. Figure 4: The alpha/beta bounds for each non-leaf nodes. • (5 Point) The re-ordered list that prunes the most nodes. Sample solution: You can only exchange the adjacent leaf/nonleaf nodes in your reordering Figure 5: The reordered game tree. to maintain the structure of the game. The order that prunes the most nodes is “20, 8, 47, 9, -20, 10, 32, -9”. (See Figure 5) 5. (20 Points) Propositional Logic (Grader: Chien-Ju Ho) Many websites are blocked by the Great Firewall of China. Let propositions D, I, and B denote “Dalai Lama”, “Tibet Independence”, and “Blocked” respectively. Consider the following sentence: [(D ⇒ B) ∨ (I ⇒ B)] ⇒ [(D ∧ I) ⇒ B] 5 (a) (6 Points) Determine whether this sentence is valid, satisfiable (but not valid), or unsatisfiable, using enumeration. Grading Policy: • (4 points) Truth table of the sentence. • (2 points) Answer: valid. Sample Solution: As shown in Table 1, the sentence is valid since it is true in all models. Table 1: Truth Table D True True True True False False False False I True True False False True True False False B True False True False True False True False (D ⇒ B ∨ I ⇒ B) True False True True True True True True (D ∧ I) ⇒ B True False True True True True True True Sentence True True True True True True True True (b) (6 Points) Convert the left-hand and right-hand sides of the main implication into Conjuntive Normal Form, showing each step. Grading Policy: • You will get 3 points for the conversion in each side. Sample Solution: (D ⇒ B) ∨ (I ⇒ B) ≡ (¬D ∨ B) ∨ (¬I ∨ B) ≡ ¬D ∨ B ∨ ¬I (D ∧ I) ⇒ B ≡ ¬(D ∧ I) ∨ B ≡ (¬D ∨ ¬I) ∨ B ≡ ¬D ∨ ¬I ∨ B (c) (8 Points) Prove your answer to (a) using resolution. Grading Policy: • (4 points) Formulation of resolution • (4 points) Prove (a) using resolution Sample Solution: ¬[(D ∧ I) ⇒ B] ≡ ¬(¬D ∨ ¬I ∨ B) ≡ D ∧ I ∧ ¬B Figure 6: The resolution process. 6. (15 Points) Short-Answer Questions (Grader: Chien-Ju Ho) 6 (a) (5 Points) What are the properties of search problems that make local search a good choice? Grading Policy: • (5 points) Illustrate at least two properties. • You will get 3 points if only the path irrelevancy is mentioned. • You will get 4 points if you only give one property. Sample Solution: Your answers can include, but are not limited to the following: • • • • The The The The state space of the problem is large or infinite. solutions of the problem are densely distributed in the state space problem to be solved is an optimization problem. path to the goal is irrelevant. (b) (5 Points) Give examples of two different ways for designing good admissible heuristics. Grading Policy: • (5 points) 3 points for the first example and 2 points for the other. Sample Solution: • Use the cost of an optimal solution to a relaxed problem as the heuristic function of the original problem. • Use the cost of a subproblem of the original problem as the heuristic function. (c) (5 Points) Is simulated annealing a complete and optimal search strategy? Justify your answer briefly. Grading Policy: • (1 points) Answer: No • (4 points) Justification • You will get points by showing your understanding of simulated annealing. Sample Solution: If the schedule lowers T slowly enough in simulated annealing, the probability of being optimal and complete for simulated annealing would approach 1. (d) (Bonus 5 Points) Please provide any concrete suggestion for the course. 7

© Copyright 2020