CMSC 471 - Homework #5

Due 11/12/07

You can hand-draw the partial-order plan and semantic network if you need to, but the rest of your homework should be typed. Don't forget your statement of sources.

1. Planning Representations (25 pts.)

Our agent is hungry and unhappy, and wants to go on a vacation, sunbathe, and eat well. Our agent starts out rich, but only has limited options, some of which will consume a substantial part of its wealth.

(a) (7 pts.) Describe only the Happy predicate using the situation calculus. You should have one or more possibility axioms (one for each relevant action)  and one or more successor-state axioms (one for each relevant action). These axioms should characterize how the state of the Happy predicate changes as a result of the actions in the domain, in terms of the domain predicates listed above.
(You may want to refer to pages 330-333 in the book.)

(b) (7 pts.) Describe the actions in this domain as STRIPS operators. Be sure to include all preconditions, add lists, and delete lists.  (See pages 377-378.)

(c) (5 pts.) Show two different legal plans (sequences of actions) for achieving the goal described above from the given initial state.

(d) (6 pts.) How many legal plans are there for this goal? Explain your answer.  Does the answer change depending on whether or not repeated states are allowed?

2. Partial-Order Planning (25 pts.)

Suppose that the agent starts building a partial-order plan to achieve the goal in the domain from problem #1. The agent decides to drive to Ocean City and eat at Burger King. Draw the partial-order plan at this point in the planning process. You do not need to show the dependencies associated with static predicates. Show all dependencies (ordering links and causal links) associated with dynamic predicates. Ordering links should be drawn as a thin, single arrow; causal links, as a double or thick arrow.

Now suppose that the agent decides to satisfy its Happiness goal using the Sunbathe action. Insert this action into the plan, showing all dependencies. Will this plan succeed? If so, complete the partial plan, resolving any threats that arise. If not, complete the partial plan to the point where planning fails, and explain the source of the failure.

3. Semantic Networks (25 pts.)

Represent the following KB using a semantic network: How would a semantic network be used to answer the following questions? Discuss how alternative implementations might yield different answers, and what other information might be needed in order to provide an unambiguous question.

(a) Is 471 hard?

(b) Is 341 hard?

(c) Is STAT 355 hard?

(d) Is 201 a prerequisite for 471?


4. Probability Basics (25 pts.)

(R&N 13.9) Using only the basic laws of probability theory (the three axioms of probability, the definition of conditional probability, the product rule, and/or Bayes' rule), prove the following theorems:

(a) (12 pts.) Prove the conditionalized version of the general product rule:

P(A ^ B | E) = P(A | B ^ E) P(B | E)
(b) (13 pts.) Prove the conditionalized version of Bayes' rule:
P(A | B ^ C) = P(B | A ^ C) P(A | C) / P(B | C)