CS 343 Artificial Intelligence
Homework 3: Planning and Probabilistic Reasoning


Due: April 16, 2009
  1. Jack is a sports freak. He belongs to a group which has many sports events scheduled at various times during the day. Below are the STRIPS descriptions of the actions that Jack uses. 

    Action: Play(g,l,t)   "Play game g at location l at time t"
Preconditions: RightNow(t), Scheduled(g,l,t), At(l), TimeAfter(t,n)
Add: HadFunAt(g), RightNow(n)
Delete: RightNow(t)

Action: Go(h,t)  "Go from h to t"
Preconditions: At(h)
Add: At(t)
Delete: At(h)

    Where the state predicates are interpreted as follows: 

    RightNow(t)  "The current time is t"
TimeAfter(t,n)  "The next time after t is n" 
At(l)  "Jack is at l"
Scheduled(g,l,t)  "Game g is scheduled to be played at location l at time t"
HadFunAt(g)   "Game g has been played and it was fun"
    Jack doesn't like to waste any time not doing any sports so he has a sports car which is very fast and can get from one facility to another immediately. Also notice that when playing a game Jack gets so into it that he forgets about the gradual progress of time. For him time just "jumps" from the starting time to the ending time of the game.

    Consider the initial state: 

    At(IF)
RightNow(9:30am)
TimeAfter(9:30am, 10:30am)
TimeAfter(10:30am, 11:30am)
Scheduled(Ping-pong, Gregory, 9:30am)
Scheduled(Soccer, IF, 9:30am)
Scheduled(Soccer, IF, 10:30am)

    Jack's goals are (given in this order): 

     HadFunAt(Ping-pong) & HadFunAt(Soccer)

    a) Show a detailed, nested trace of subgoals and actions (like that given on pages 19-22 of the lecture notes on planning) resulting when STRIPS is used to solve this problem. Assume that different instantiations of an action (i.e. different ways of binding its variables) that are capable of achieving a goal (such as different times of playing a game) are considered as alternative actions for achieving the goal. Assume that when there are multiple action instantiations for achieving a goal, that STRIPS first considers the action instantiation with the least number of currently unsatisfied preconditions. Finally, clearly show the final plan constructed and all the facts that are true in each state of the world after each action is executed.

    b) Would STRIPS be able to solve this problem if the order of the goals were reversed? Would it get an optimal solution, a suboptimal solution, or no solution at all? Briefly explain exactly what would happen in this case.

  2. Naive Bayes is frequently applied to categorizing text (e.g. documents, web pages) based on the presence or absence of different words. Assume we want to categorize science texts into the following categories: Physics, Biology, Chemistry. The following probabilities have been estimated from analyzing a corpus of preclassified web pages gathered from Yahoo:

    c Physics Biology Chemistry
    P(m) 0.35 0.40 0.25
    P(`atom' | m) 0.1 0.01 0.2
    P(`carbon' | m) 0.005 0.03 0.05
    P(`proton' | m) 0.05 0.001 0.05
    P(`life' | m) 0.001 0.1 0.008
    P(`earth' | m) 0.005 0.006 0.003
    P(`force' | m) 0.05 0.005 0.008

    Assuming the probability of each evidence word is independent given the category of the text, compute the posterior probability for each of the possible categories for each of the following short texts. Assume the categories are disjoint and complete for this application. Assume that words are first stemmed to reduce them to their base form (atoms -> atom; forces -> force, protons -> proton). Simply ignore any word stems that are not in the table above.

    a) The carbon atom is the foundation of life on earth.

    b) The carbon atom contains 12 protons.

    c) String theory attempts to unify all of the forces on earth.

  3. A company is considering a plot of land and deciding whether to drill for oil there. Fees and expenses associated with drilling the plot for oil are $2M (with no cost for doing nothing). If they strike oil, they will receive $10M; if they do not strike oil, they will receive nothing. The probability of striking oil on any given plot in this region is P(oil)=0.45.

    The expected value of an action, E[action], is defined as the the sum of the value of each possible outcome multiplied by the probability of that outcome as a result of the action.

    Compute:
    a) E[drill]
    b) E[!drill]

    The company has the option of paying for a geological survey test that will provide additional information about the possibility of oil at this specific plot. The test costs $0.3M to perform and has the following probabilities of returning a positive result: P(pos_result | oil) = .95, P(pos_result | !oil) = .15.

    c) Compute P( pos_result ).

    If the company chooses to pay for the test, compute the following and justify your results:
    d) E[ drill ] if the test result is positive.
    e) E[ drill ] if the test result is negative (!pos_result).
    f) E[!drill ] (with a negative or positive test result).

    If the company always chooses the action that maximizes expected value,
    g) Should the company pay for the test? Why or why not? Note that in order to correctly answer this question, you will need to do some additional calculations beyond the above.

  4. Babies don't have too many needs, but they have even fewer ways to communicate those needs to their parents. Parents need some way to figure out what is the matter with their child. Assume we know the following:

    P(sick) = .3
    P(ache | sick) = .75
    P(ache | !sick) = .1
    P(tired) = .6
    P(cry | ache,tired) = .9
    P(cry | ache,!tired) = .65
    P(cry | !ache,tired) = .55
    P(cry | !ache,!tired) = .2

    a) Assuming that the above conditional probabilities are sufficient to specify the CPTs for a Bayes net for this problem, draw a picture for such a Bayesian network.

    b) Compute the full joint probability table for this Bayesian network. Please model your table after the following template:

    sick!sick
     tired   !tired   tired   !tired 
    achecry    
    !cry    
    !achecry    
    !cry    

    Calculate (show your work):
    c) P(cry)
    d) P(tired | cry)
    e) P(tired | ache,cry)
    f) P(sick | cry)
    g) P(sick | ache,cry)