Problem 1: Uninformed Search (10 points)
|
|  Yüklə 70.5 Kb.
|
| Mehran Sahami Handout #10
CS121 August 7, 2001 Midterm Examination Solutions Problem 1: Uninformed Search (10 points) Show which nodes are expanded, and the order in which they are expanded using:
A, B, C, D, E, F, G, H, I, J
A, B, E, L, M, F, C, G, H, N, O
by 1 in each iteration) A, A, B, C, D, A, B, E, F, C, G, H, I, D, J Problem 2: Heuristic Search (18 points) Suppose that you are given a heuristic function h-hat. Although h-hat is not admissible, it is nearly admissible, in the sense that there is some small constant such that: 0 h-hat(n) h(n) + for every node n. Prove that, with such a heuristic, the A* algorithm will find a path to the goal (assuming one exists) for which the total cost g is within of optimal. Proof: Let y be a goal node with optimal cost. We denote this optimal cost g(y) = g*. We perform a proof by contradiction. Negating the desired result, we assume that A* has found a path to a goal node v which has total cost g(v) > g* + . In order for node v to be expanded, it means than no other node in the OPEN list for A* could have a smaller f-hat value. f-hat(v) = g(v) + h-hat(v) > g* + (since g(v) > g* + , and h-hat(v) 0)
f-hat(y) = g(y) + h-hat(y) = g* + h-hat(y) g* + (since h(y) = 0) Now, let node u be some node on the path to the optimal goal y that has not yet been expanded, but is on the OPEN list. Note that such a node u must exist since the goal y is on some path from the root, and y has not yet been expanded (otherwise we would have found a goal node prior to v). Realize that, f-hat(u) = g(u) + h-hat(u) g(u) + h(u) + . Now, we note that g(u) + h(u) is simply the cost of reaching the optimal goal y, going through the node u. But since u lies on the path to the optimal goal y, it means that the cost of reaching the optimal goal y going through node u, is simply g* the cost of reaching the optimal goal node. Thus, f-hat(u) g* + . This f-hat value is lower than v, which means that node u must get expanded before expanding node v. However, if this were the case, and node u can represent any node on the path to y, it means that all nodes on the path to y (including y) must be expanded before node v. Hence we have a contradiction, so the goal node v that is found cannot have cost > g* + . So the goal node found must be within of optimal. Problem 3: Alpha-Beta (12 points) Consider the following game tree. The value for each leaf node in the tree is shown immediately below each node. The first player is the maximizing player. 
Pruned nodes: Q I (and, thus, T and U) K (and, thus, X and Y)
The first player should make the move that leads to node B. Problem 4: Delayed-Reinforcement Learning (12 points)
The exploitation vs. exploration trade-off refers to the fact that an agent may learn a policy that is non-optimal, but still achieves a positive reward. As a result, the agent may choose to follow this policy and obtain the reward. This exploitation of the existing policy, however, may cause the agent to foregoing the opportunity to learn a more optimal policy that achieves a greater discounted reward. Such a policy may exist, but if the agent has not explored the space of policies sufficiently, then this better policy may not be found. Occasionally taking random actions helps address this problem, for two reasons. First, since the agent is exploiting its current policy most of the time, it is still obtaining positive rewards in general. However, by taking occasional random actions, the agent will explored parts of its world that it would otherwise have not ventured into if it was rigidly exploiting its current policy. Hence, the agent can balance exploiting getting rewards with its current policy, while also occasionally exploring other parts of its worls to try to learn better policies.
Yes, the simulation is guaranteed to eventually find an optimal policy. The reason for this is that there are two criteria for guaranteeing finding an optimal policy. The first is that the reinforcement learning be done using 0 < < 1. This is given. The second is that every state in the world be visited infinitely often. Since the simulation contains an element of randomness and may proceed for possibly infinite time steps, every state in the world will be visited a potentially infinite number of times. This theoretically guarantees that an optimal policy will be converged on by the agent. In practice, an optimal policy is generally found after a large number of simulation steps when a small element of randomness is used. Problem 5: Propositional Logic (15 points) Use resolution to perform the following proof: Given: (P Q R) S Q R
S P R
Problem 6: Predicate Logic (23 points)
Mouse(Angelica) (forall x) (Dog(x) Friend(Bob, x)) Cat(Cecil) Dog(David) (forall x) ([Friend(Bob, x) Cat(x)] Friend(Angelica, x)) (forall x) (Dog(x) Cat(x))
with s = {x2/x4}
with s = {x1/x5}
with s = {x3/x6}
with s = {x7/David} |