CS 343 Artificial Intelligence
Homework 3: Planning and Probabilistic Reasoning


Due: April 12th
  1. You're a busy student. You need to complete a project for a class. You would also like to check out and read a novel that was just heartily recommended to you. Being a good student, you prioritize your tasks wisely and read only after you completed the homework. 

    Action:  CheckOut(b,t) "Check out book b from the library at time t"
Preconditions:  Now(t), TimeAfter(t,n), LibraryOpen(t)
Add:  HaveBook(b), Now(n)
Delete:  Now(t)

Action: Read(b, t)   "Read book b at time t"
Preconditions: HaveBook(b), Now(t), TimeAfter(t,n), HomeworkDone(c)
Add: BookRead(b), Now(n)
Delete: Now(t)

Action: DoHomework(c,t)  "Do homework for class c at time t"
Preconditions: Now(t), TimeAfter(t,n), Assigned(c)
Add: HomeworkDone(c), Now(n)
Delete: Now(t)

    Where the state predicates are interpretted as follows: 

    Now(t)  "The time is now t"
TimeAfter(t,n)  "The next time after t is n"
LibraryOpen(t) "The library is open at time t"
HaveBook(b) "You have book b"
Assigned(c) "Homework was assigned for class c"
HomeworkDone(c) "Homework for class c is done"
BookRead(b) "Book b was read"

    Consider the initial state: 

    Now(7:30PM)
TimeAfter(7:30PM, 8:30PM)
TimeAfter(8:30PM, 9:30PM)
TimeAfter(9:30PM, 10:30PM)
LibraryOpen(7:30PM)
Assigned("CS343")

    And the goal (given in this order): 

    BookRead("One Hundred Years of Solitude") & HomeworkDone("CS343")

    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 attending a class) 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. Consider using a partial order planner for solving this problem. Draw the final plan created by the POP algorithm, showing causal links and ordering constraints (distinguishing them from each other), as well as all actions and preconditions. Explain how the ordering constraints arose when the plan was consructed, identifying threats that arose and specifying how they were resolved.

  3. One approach to resolving ambiguous words in English is to use Bayesian reasoning based on surrounding words. Consider the word ``class'' as meaning one of the following:
    1. ``prototype for an object in Object-Oriented Programming(OOP)'';
    2. ``education imparted in a series of lessons or class meetings'';
    3. ``people having the same social or economic status'';
    Assume we treat the presence of the following words anywhere in a sentence as evidence (symptoms):
    1. ``people'' (``People often forget to define a deconstructor for their class'', ``People are often late to class'', ''The struggle of lower class people is the driving force of progress'');
    2. ``program'' (``This program does not use the window class'', ``This class is a required part of the natural science program'', ``The government's tax program does not address the needs of the lower class'');
    3. ``student'' (``This window class was written by a clever student'', ``The student was late to class'', ``The student was concerned with the problems of the working class'');
    4. ``education'' (``Learning how to write an abstract class is a vital part of your education'', ``Not attending the class will hamper your education'', ``Lowering the cost of education is an important issue for the middle class'').
    Assume that the following prior and conditional probabilities are measured (where m is a possible meaning for the ambiguous word).

    m OOP lessons economic status
    P(m) 0.1 0.6 0.3
    P(`people' | m) 0.001 0.1 0.1
    P(`program' | m) 0.1 0.01 0.001
    P(`student' | m) 0.01 0.2 0.01
    P(`education' | m) 0.005 0.05 0.05

    Consider using a simple (naive) Bayesian framework in which we assume the probability of each evidence word is independent given the meaning of the target ambiguous word. Compute the posterior probability for each of the possible meanings of ``class'' for the following case:

    P(m | not `people', `program', `student', not `education') (e.g. ``Did the student complete the homework program for the class?'')

  4. Consider the following graph of a Bayesian network. Assume each of the random variables are binary-valued.

    Answer the following questions, providing short explanations for your answers.

    a) How many conditional-probability parameters need to be specified for this network?

    b) How many conditional-probability parameters need to be specified to give the complete joint probability distribution for this problem?

    c) Consider the following interpretation of the network: a is smoking, b is having a cold, c is sore throat, d is inflammed lungs, e is sneezing, and f is coughing. Assume the nodes at c, d, and f are modeled as noisy-or nodes, combining independent probabilistic causes; and that parameters are set at some reasonable values to model this problem. Assume we first learn that coughing is true and we compute that smoking is the most likely explanation. Next we learn that sneezing is true. Qualitatively, what happens to the probability of smoking, does it go up or down? According to the theory of Bayes nets, why does this happen?