CS121

Introduction to Artificial Intelligence

Winter 2004

 

 

 

Homework #5

(Planning, Adversarial Search, Probabilities)

Out: 2/11/04 — Due: 2/18/04

 

 

How to complete this HW: First copy this file; then insert your answers in the file immediately below each question; finally submit the completed file to the submission webpage https://www.stanford.edu/class/cs121/hwsub/hw5.fft before 2/18at midnight.

 

Note on Honor Code: You must NOT look at previously published solutions of any of these problems in preparing your answers. You may discuss these problems with other students in the class (in fact, you are encouraged to do so) and/or look into other documents (books, web sites), with the exception of published solutions, without taking any written or electronic notes. If you have discussed any of the problems with other students, indicate their name(s) here:

………………………………………………………………………………………………

Any intentional transgression of these rules will be considered an honor code violation.

 

General information: In the following, whenever an explanation is required (“Why?”), there will not be full-credit without an explanation. Keep explanations short and to the point. Excessive verbosity will be penalized. If you have any doubt on how to interpret a question, either tell us in advance, so that we can help you understand the question, or tell us how you understand it in your returned solution.

 

Grading:

 

Problem#

Max. grade

Your grade

I

5

 

II

5

 

III

5

 

IV

5

 

V

5

 

Total

10

 

 

 

I. (5 points) Planning – A robot ROBOT operates in an environment made of two rooms R1 and R2 connected by a door D. A box B is located in R1 and the door’s key is initially in R2. The door can be open or closed (and locked). Figure 1 illustrates the initial state, which is described by: IN(ROBOT,R2), IN(K,R2), OPEN(D)

 

 

Figure 1: Initial state for Problem I

 

The only actions available to the robot are:

Grasp-Key-In-R2

Lock-Door

Go-From-R2-To-R1-With-Key

Put-Key-In-Box

They are represented as follows, where P stands for “precondition” and E for “effect”:

 

Grasp-Key-In-R2

      P: IN(ROBOT,R2), IN(K,R2)

      E: HOLDING(ROBOT,K)

 

Lock-Door

      P: HOLDING(ROBOT,K)

      E: ุOPEN(D), LOCKED(D)

 

Go-From-R2-To-R1-With-Key

      P: IN(ROBOT,R2), HOLDING(ROBOT,K), OPEN(D)

      E: ุIN(ROBOT,R2), ุIN(K,R2), IN(ROBOT,R1), IN(K,R1)

 

Put-Key-In-Box

      P: IN(ROBOT,R1), HOLDING(ROBOT,K)

      E: ุHOLDING(ROBOT,K), ุIN(K,R1), IN(K,B)

 

1.      Let the goal be G = IN(K,BOX), LOCKED(D). Give a plan solving this problem. (Just give the sequence of actions, without explanation.)

 

2.      What is the regression of G through the operator Put-Key-In-Box?

 

3.      Describe how backward planning generates a plan to achieve G. Show a solution path in the search tree. Label the nodes of this path with the regressed goals and its arcs with the operators. [You may present the information in text form.]

 

II. (5 points) Planning – Sketch how you would combine forward and backward planning to perform bi-directional planning. How can the bi-directional planning algorithm detect that it has found a solution? Identify two important issues that may make the approach impractical (too computational intensive).

 

III. (5 points) Adversarial Search – Consider the following game tree, in which the values of the evaluation function (indicated between brackets besides the tree leaves) are from the first player’s point of view:

 

(A  (B  (D  (J [9]   K [2]))

            (E   (L [4]  M [-1]))

            (F   (N [6]  O [-2])))

      (C  (G  (P [1]   Q [8]))

            (H  (R [1]   S [1]))

            (I   (T [-3]  U [5]))))

 

A is the root. Its children are B and C. B’s children are D, E, and F. Etc … The value of the evaluation function of J is 9, that of K is 2, etc…

 

1.   Perform depth-first search (with the ordering of the nodes as listed above) of the game tree with a-b pruning. Give the final a or b value at each node of the game tree that has not been pruned and indicate all the nodes that the first player would not examined. What move will the first player make?

 

2.   Assume that alpha-beta technique keeps track of the tree path that is responsible for the final alpha value of the root of the tree. This path connects the root of the tree to some leaf node x. What is this node?

 

3.   Assume the first player generates a sub-tree (singular extension) from x and gets the following sub-tree:

      (x         (X  (X1 [4)] X2 [2]))

                  (Y  (Y1 [3]  Y2 [-1] Y3 [7])))

      Should the first player change decision? [Answer yes or no.]

 

IV. (5 points) Probabilities – Consider two propositions A and B with prior probabilities P(A) and P(B).

 

1.      What is the definition of “A and B are conditionally independent”?

 

2.      Show that P(A|BูA) = 1

 

3.      Prove that if A and B are conditionally independent, then A and ุB (not B) are also conditionally independent.

 

 

V. (5 points) Probabilities – An agent is given the following knowledge about a car:

ท        If the battery and the headlight bulbs are both ok, then the headlights will work.

ท        If the battery is ok and the starter is ok, then the engine will start.

The agent is also told that the prior probabilities that the headlight bulbs fail, that the battery fails, and that the starter fails are H, B, and S, respectively, and that these three events are independent (pairwise and globally).

     

  1. There are 8 possible situations depending on whether each of the three components (bulbs, battery, and starter) is failing or not. What is the probability of each situation?

 

  1. What is the prior probability of the engine not starting?

 

  1. Suppose that the agent observe that the engine does not start. What are the new probabilities that the headlight bulbs are broken, that the battery is failing, and that the starter is broken?