Final Homework set for CSE 574 Spring 2003.

Opened: [Nov  9, 2004]

Expected Due date: [December 1st, 2004]


Qn I. [Temporal Constraint Networks]

Consider start times of three events X, Y and Z.  Y can start at least
1 unit or at most 2 units after X. Z can start at least 1 unit or at
most 4 units after Y. Z can start right along with X, or at most 5
units after X.

1. Represent this as a temporal constraint network problem. Is this a
simple or disjunctive temporal network?

2. Using the constraint composition, compute the constraint between X and
Z (using the path X-->Y-->Z)

3. Using the constraint intersection, compute the tightest constraint
between X and Z (by intersecting the constraint from path X-->Z and
the path X-->Y-->Z). Is this constraint tighter than the constraint
X [2 2.5][3 3.5] Z ?


4. Give the distance graph corresponding to this simple network.


5. Run the floyd-warshall algorithm on the distance graph, and compute
the all pairs shortest distances between all the events. According to
this analysis, what is the true constraint between X and Z? Did you
get the same answer as 3? 

6. Suppose X starts at time 6. What is the earliest times Y and Z can
   start? 

Qn II. [Scheduling:]


] Consider the following three jobs that need to be scheduled on a
unary capacity machine in a job shop scheduling scenario:

    i   EST = 0  LFT= 20  dur= 15
    j   EST = 5  LFT= 40  dur= 20
    k   EST = 15 LFT=25   dur =5


Show the start time and PCP encodings for this problem. 

Qn III. [Conformant planning]

Consider a domain with three literals, P, Q and  R. 

Suppose in the initial state, we only know that either P or Q is true
(not both).  Our goal is to make Q true.

Consider the following three actions with conditional effects:

A1: P=> [Q V R]
A11:P=> [Q V ~R]
A2: R=> Q
 
[Assume that the disjunction is exclusive--that is the effect Q V R
means either Q or R will be true--not both]

1. What is the size of the belief space for this problem? (i.e.,
   number of belief states).

2. Show the initial belief state corresponding to this problem.

3. Show the set of actions that can be applied to this belief state
   and the resulting belief states. 

4. Show one path (actions, and belief states) that lead to the
   goal.

5.(added) Show how regression search solves this problem

Qn IV. [Conditional Planning]

To the problem in III, suppose we added three sensing actions:

P?, Q?, R? 

Each of which will tell us whether the corresponding literal is true
or false. 

We also have another effect for A1, which involves deleting Q, if it
were true. So A1 is now:

A1: P=>[Q V R] ; Q=> ~Q

The initial state and the goal state, as well as the rest of the
actions, remain the same.


1. What is the size of the belief space now for this problem?
   **What are the number of observation classes?

2. Show the complete set of actions that can be applied to the initial 
   belief state, and for each one, the belief states that results

3. Show one path (actions, belief states) that lead to the goal.


Qn V. [Note: you should be ready to discuss the answer to this
question as part of the interactive review in the last class 12/6]

  1. List five ideas/techniques that you learned in this course
  that you thought were most interesting.

  2. List five ideas/technqiues that you thought got over-play
  and were not worth the time we spent on them.

  3. List any ideas that you thought would be covered in the
    course, and would have liked them to see covered, but finally were
not.

  4.  List five "non-obvious" (to you) details or cross-connections
      that _you_ were able to  appreciate over the semester 


MDP question to be added. 

			      ----------

Special Question: 
 The URL
http://www-rcf.usc.edu/~skoenig/icaps/icaps04/programdetails.html

 contains the list of  papers and their PDF sources from ICAPS 2004 (which is the most recent planning
and scheduling conference).

Your task is to:

 1. Select a paper from the technical session. Any paper is fine.

 2. Read it.

 3. Write a review of the paper. Your review should be 1 page long and have the following
    components:
      3.1 A brief summary (in your words) of the main contribution(s)
          of the paper.
      3.2 One or two most important ideas in the paper and why they
           are important. you can also relate these to
           state-of-the-art as covered in the class (if applicable)
      3.3 One or two important shortcomings of the paper that you
          could detect
      3.4 Identify one or two important directions in which the work 
          can be extended 
      3.5 A summary decision--if you were the reveiwer, would you have
          accepted the paper? Justify your decision.