Homework 4 -- due Tuesday April 29

1. [everyone] Answer the following questions:
   1. [20 points] Question 10.22 from Russell and Norvig
   2. [15 points] Question 11.6 from Russell and Norvig
   3. [15 points] Question 11.11 from Russell and Norvig
   4. [20 points] Question 11.13 from Russell and Norvig
   5. [20 points] You are given the following STRIPS-like schema to move blocks around:
      Action: Move(b,x,y)
      PRECOND: On(b,x) and Block(b) and Clear(b) and Clear(y)
      EFFECT: On(b,y) and Clear(x) and not On(b,x) and not Clear(y))
      
      1. If you want to rewrite it using successor-state axioms, how many successor-state axioms do you need? explain briefly.
      2. Write the corresponding successor-state axiom(s).
2. [Graduate Students only][10 points]
   Undergraduate students do not need to answer this question. They will get credit (10 points) for it without having to do any work. However, undergraduates are welcome to answer this question, which will count as extra credit (up to 1% of the final score).
   Consider the problem of moving one or more objects from a location to another and consider cases in which an object can be carried togheter with another object. For instance, multiple cups on a tray are moved when the tray is moved, a cup on a saucer which is on a tray is moved with the tray, a cup on a saucer is moved when the saucer is moved. A cup can also be moved directly.
   1. Define one or more operators for moving objects. Make sure the operator(s) allow moving individual objects as well as objects carrying other objects. Define the predicates you use and make sure the notation you use for writing the operator(s) is clearly defined.
   2. Can you write the operator(s) using STRIPS-like operators or do you need to extend the planning language? if yes, specify the extensions you need and how they affect the planning algorithm. Explain how easy (or difficult) it is to generalize the operator(s) to handle variations on the problem.
   3. Show the initial state for a problem in which there is a cup on a saucer on a tray, a plate and a spoon on the same tray, and the tray is on table. Show the goal state for a situation in which the cup and the spoon are on the saucer on a desk.
   4. What is the situation space for the problem defined in the previous question?
   Copyright: © 2008 by the Regents of the University of Minnesota
   Department of Computer Science and Engineering. All rights reserved.
   Comments to: Maria Gini
   Changes and corrections are in red.