完成关于Uninformed Search等的AI简答题。
Probability Review
This question is meant to review part of the probability prerequisite. It might be helpful to look into resources under General Resources.
Let A, B, C, D be four random variables.
(a) What is the smallest set of independence or conditional independence relationships we need to assume for the following scenarios?
- (i) [1 pt] P(A, B) = P(A|B)P(B)
- (ii) [1 pt] P(A, B) = P(A)P(B)
- (iii) [2 pts] P(A, B, C) = P(A|B)P(B|C)P(C)
- (iv) [3 pts] P(A, B, C) = P(A)P(B|C)P(C)
- (v) [3 pts] P(A, B, C) = P(A)P(B)P(C)
(b) Simplify the following expressions to one probability expression. Please show your work.
Uninformed Search and Heuristics
Consider the following simplified version of the classic Atari video game, Montezuma’s Revenge: It is played on the board illustrated below. An agent (represented by the person icon in cell (1,3)) wishes to grab the key (in cell (3,0)). A skull starts in cell (5,2) and moves to the right by one cell after each action is executed until it ends up in the rightmost cell, at which point it starts moving to the left, and repeats this pattern back and forth.
The agent can be facing either left or right. There are 10 possible actions for the agent: 2 turning actions (face_left, face_right) and 8 moving actions (left, right, up, down, left_up, left_down, right_up, right_down). The agent can move up or down while facing either direction, but can move sideways or diagonally only if facing in that direction. For example, if the agent is facing right but tries to move left up, the agent will not move and nothing will happen. Furthermore, if the agent is already facing left and a face_left action is taken, nothing happens.
Lastly, the agent cannot move into a cell currently occupied by the skull, or a wall.
- (a) Answer the following questions for the Montezuma’s revenge board above:
- (i) [7 pts] Let N be the number of possible cell locations that the agent can be in, and let M be the number of possible cell locations that the skull can be in. Recall that for “pacman pathing”, the representation of the state was (x, y) where x was the row and y was the column of pacman’s position. Describe a representation of a state in the state space for this game and give an expression for the size of the state space.
- (ii) [3 pts] What is the goal test?
- (b) Now, consider the simplified board below, which has no skull and no facing-direction for the agent (i.e., the agent can move in any of the 8 directions as long as it remains in the board). For the three following graph search algorithms, perform the search procedure yourself (please show your work) and provide answers to the questions below regarding the nodes expanded during the search as well as the final path found by the algorithm.
On this board, assume that a diagonal move has a cost of 3, whereas moving left, right, up, or down has a cost of 1. Do notice the difference in costs, and recall which algorithms use this cost information and which algorithms do not.
Remember that the search procedure should begin at the agent’s starting position (C). To break ties when adding nodes of equal cost to the frontier, follow alphabetical order.
Finally, when listing the order/number of nodes expanded, do not include nodes which are taken off the frontier but discarded immediately due to already having been expanded.- (i) [8 pts] Breadth-first graph search
Frontier data structure: FIFO.
Recall that BFS selects the shallowest unexpanded node in the frontier for expansion, which will be the oldest node in the frontier. - (ii) [8 pts] Uniform-cost graph search
Frontier data structure: priority queue (make sure you update/reorder the whole frontier after each addition)
Recall that UCS keeps track of the lowest cost, g(v), to get from the start node to the node v. - (iii) [8 pts] A graph search (with Manhattan distance to the goal as the heuristic)
Frontier data structure: priority queue (make sure you update/reorder the whole frontier after each addition)
Recall that A computes f(v) for the nodes v that it expands, with f(v) = g(v) + h(v) where g(v) is the lowest cost to reach v from the start node and h(v) is an estimate of the distance from v to the goal.
- (i) [8 pts] Breadth-first graph search
- (c) [10 pts] Given your answers above, what are the qualitative differences between the results achieved by BFS, UCS, and A*? Which one finds the shortest path (in number of steps)? Which one finds the optimal path (in cost)?
- (d) For the same board and setting as part (b), give an example for each of the following types of heuristics. Please briefly explain why the example you chose satisfies the requested properties.
- (i) [3 pts] Admissible and consistent.
Note: You can use a heuristic that we have frequently used in this class, or you can just assign any set of numbers to the states that qualifies as an admissible and consistent heuristic.
State s - (ii) [4 pts] Admissible but inconsistent
- (iii) [3 pts] Inadmissible and inconsistent
- (i) [3 pts] Admissible and consistent.
- (e) (i) [8 pts] For this new version of the game, your friend Nancy suggests taking the old game setting from part (b) and now adding the ability for the agent to perform a maximum of one “teleportation” action during the game. That is, on one of the agent’s moves, it can choose to jump from its current state to any other non-goal state on the board, and the cost of teleporting is 1.
- How does this new teleportation ability change the state space of the game from part (b), which was (x, y)? Does anything need to be added or removed?
- Nancy argues that in this new game, at least one previously consistent heuristic can become inconsistent.
Note: we define heuristics for this problem as being a function of only the cell location: They cannot incorporate anything that did not exist in the old version of the game that we are comparing to.
If you believe Nancy is right, give an example of a heuristic that used to be consistent in the old game but is no longer consistent in this new game. Make sure to explain why it is no longer consistent (perhaps with a drawing of a board state and an explanation).
If you believe Nancy is wrong, provide an argument for why a heuristic that was consistent in the old game must also remain consistent in this new game. Be specific about your reasoning and use mathematical quantities such as heuristic costs of states h(v) and true costs of actions c(v, a, v’).