Homework #2 (Problem Set)
CSE 3521/5521
Autumn 2021
Due: Thursday, September 23 by 11:59pm
Due: Friday, September 24 by 11:59pm
Worth 50 points
I. Preparation
1. Read/study the assigned reading sections from Chapter of AI: A Modern Approach, 3rd edition (Russell and Norvig)
2. Read/study the lecture notes on Planning and search algorithm
II. Collaboration & Piazza
Please read the course policy on Academic Misconduct in the syllabus. You may discuss the problems with your classmates at a high level only. Though, you must formulate your own solution without any help from others or third party sources.
In your solution, you need to list with whom you have discussed for each problem (please do so in the first page).
Do not post any part of your solution or spoilers on Piazza.
III. Guidelines
You will place your solutions to this portion of the homework (Problem Set) into a single PDF file named HW2_problems_name_dotnumber.pdf (e.g., HW2_problems_shareef_1.pdf).
It is highly suggested that you directly type your solutions and save them as a PDF file. If you write your solutions on paper and scan it you run the risk that the TA won’t be able to read your solution. In this case the TA will not give credit for any portion that is not readable.
You should write down the derivation of your answers, and highlight your answers clearly!
IV. Problems
Search [30 points]
Figure 1 above shows a state space graph, in which state A is the start state and state G is the goal state. Each edge is directed and associated with a cost. Please apply the five search algorithms — DFS, BFS, UCS, greedy, and A* — that you learned in the lectures to find the solution. Use the TREE-SEARCH algorithm (not the GRAPH-SEARH algorithm). Please read the hints at the end of this question before answering the question.
1. Please apply DFS to search the solution. Please consider that your fringe is implemented by stack and you always push the successor states following the alphabet order (A-to-Z). For example, if you are expanding node A, then you will push its three successor states in the order of B, C, F into the stack.
(2.5 points) How many nodes do you need to expand (including expanding A and the node containing G) until you find the solution?
(2.5 points) What is the solution (i.e., state sequence) outputted by DFS? Your solution should contain both states A and G.
2. Please apply BFS to search the solution. Please consider that your fringe is implemented by queue and you always enqueue the successor states following the alphabet order (A-to-Z). For example, if you are expanding node A, then you will enqueue its three successor states in the order of B, C, F into the queue.
(2.5 points) How many nodes do you need to expand (including expanding A and the node containing G) until you find the solution?
(2.5 points) What is the solution (i.e., state sequence) outputted by BFS? Your solution should contain both states A and G.
3. Please apply UCS to search the solution. If there are two candidate nodes (i.e., partial plans) whose costs are the same, expand the one whose number of states is smaller first. For example, if A-B-D (cost 5) and A-B-C-E (cost 5) are both in your fringe, you will expand A-B-D before expanding A-B-C-E.
(2.5 points) How many nodes do you need to expand (including expanding A and the node containing G) until you find the solution?
(2.5 points) What is the solution (i.e., state sequence) outputted by UCS? Your solution should contain both states A and G.
4. Please apply Greedy Best First search to search the solution. Please apply the following heuristic h: the minimum number of edges to travel through to achieve G. For example, h(B) is 2. If there are two candidate nodes (i.e., partial plans) whose heuristic values are the same, expand the one whose number of states is smaller first. For example, if A-B-D (h=1) and A-B-C-E (h=1) are both in your fringe, you will expand A-B-D before expanding A-B-C-E.
(2.5 points) How many nodes do you need to expand (including expanding A and the node containing G) until you find the solution?
(2.5 points) What is the solution (i.e., state sequence) outputted by greedy search? Your solution should contain both states A and G.
5. Please apply A* search to search the solution. Please apply the following heuristic h: the minimum number of edges to travel through to achieve G. For example, h(B) is 2. If there are two candidate nodes (i.e., partial plans) whose g + h values are the same, expand the one whose number of states is smaller first. For example, if A-B-D (g+h=6) and A-B-C-E (g+h=6) are both in your fringe, you will expand A-B-D before expanding A-B-C-E.
(2.5 points) How many nodes do you need to expand (including expanding A and and the node containing G) until you find the solution?
(2.5 points) What is the solution (i.e., state sequence) outputted by A* search? Your solution should contain both states A and G.
(2.5 points) What is the cost of the optimal solution
(2.5 points) Which algorithm can achieve it? (Write down all the algorithms that can.
Hints:
· Since you are working on tree searches, you may expand multiple nodes (i.e., partial paths) that have the same last states and you should count all of them. For example, you may expand A-B-C and then A-C and you should count both of them.
· As an example of how to count how many nodes you expand, if you expand “A”, and then ”F” (i.e., A-F), and then “B’” (i.e., A-B), and then “G” (i.e., A-F-G) in the search process, then you expand 4 nodes. You expand a node (i.e., A-F) only when you check if its last state (i.e., “F”) is a goal or not (if not, adding the successors into the fringe), not when you put that node (i.e., A-F) into your fringe.
· A solution is the state sequence (in the problem set) or action sequence (in the programming set) that can directly lead you from the start state to the goal state. It is NOT the sequence of nodes that you expand in your search process. For instance, in the above example, you expand 4 nodes, but your solution is A-F-G.
Adversarial Search [20 points]
Figure 2 shows an adversarial search tree, in which the blue nodes (i.e., ”A”, ”D”, ”E”, ”F”, ”G”) are max nodes and the red nodes (i.e., ”B”, ”C”) are min nodes. The gray nodes are the goal states, each has its utility value (the higher, the better). Each max or min node has two actions: ”go left” or ”go right”. For example, if you are at ”A”, then you can go left to arrive at ”B” or go right to arrive at ”C”.
Note that, you are provided with this entire adversarial search tree, which has not been traversed/expanded yet. Your job is to do minimax search, determining each node’s value and finding out the minimax solution from ”A” to the goal states.
1. Please perform the adversarial (minimax) search to:
(3.5 points) Fill in the value of each node
(2.5 points) Find out the minimax predicted state-sequence. A predicted state-sequence is a “path” from “A” to the gray (leaf) nodes. For example, “A“-“C“-“G“-“N“ (or equivalently, right-right-left) can be a valid predicted state-sequence BUT it may not be the minimax predicted state-sequence.
2. Apply α-β pruning to redo the minimax search. Note that, in α-β pruning, you are expanding/traversing the tree in a depth-first-search fashion, in which you will always choose the left action first and then the right action. In other words, the node expansion order will be “A“-“B“-“D“-“H“-“I“-“E“-“J“-“K“-“C“-“F“-“L“-“M“-“G“-“N“-“O“, but some nodes might be pruned/skipped without being visited. Every min or max node will have its (α, β), which are initialized by its parent and may be updated when its children are being expanded. The initial (α, β) to node “A” is (-∞, ∞).
See the lecture slides for more details. Specifically, please follow the “Alpha-Beta Implementation” slide to update each min or max node’s value and its (α, β) The slide provides a recursive implementation for the depth-first-search fashion. If you are visiting a leaf node, you simply return its utility value. Note that (α, β) in that slide are called/passed by values.
(7.5 points) Fill in the value of each node. If a node is pruned (i.e., no need to visit according to α-β pruning), please put X as the answer for that node. For a gray node, if it is visited, simply fill in its utility value. Note that, the values of the nodes can be ∞or -∞ and can be different from the previous question.
(3 points) Find out the minimax predicted state-sequence. A predicted state-sequence is a “path” from “A“ to the gray (leaf) nodes. For example, “A“-“C“-“G“-“N“ (or equivalently, right-right-left) can be a valid predicted state-sequence BUT it may not be the minimax predicted state-sequence.
3. (3.5 points) Now let us consider the expectimax search by changing each red min node to an expectation node. The probability for the left and right actions are 50% and 50%. Please fill in the value of each node.
V. Carmen submission
Combine your solution to this portion Homework #2 (Problem Set) with your solution to Homework #2 (Programming Set), which is your solution to this programming portion, into one .zip file named HW2_name_dotnumber.zip (e.g., HW2_shareef_1.zip). You should have a total of three files in the zip file.