Final Homework set for CSE 574 Spring 2003.

Opened: [May  3, 2003]

Due: [May  14, 2003; 12noon]


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: PCP]


] 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 how the PCP scheduling algorithm schedules these (show the way
slacks are calulated, min slack pair is picked, and an ordering
committed etc.). 

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.


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?

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. [MDP]

 Consider the following approach for solving classical planning
 problems. Set them up as MDPs, with the Reward function being M (M
 >>1) in states where all goals are satisfied and 0 everywhere
 else. The cost of doing any action in any state is taken to be d (d
 << M). The goal states are modeled as sink states (i.e., any action
 done from that state returns the agent to that state). Compute the
 optimal infinite horizon policy for the MDP. Use this as the basis
 for deriving the plan for the problem.

   a. Exactly how do you derive the plan for the problem given its
   optimal policy?

   b. Compared to the normal classical planning approaches, what are the
   advantages/disadvantages for this way of solving a classical planning
   problem? 

   c. Suppose we start with a value vector that corresponds to the
   immediate rewards of the states, and run value iteration (rather
   than policy iteration) for a small fixed number of iterations (not
   until convergence). Could the values that invidual states get by this
   process be useful for a classical planner? 


Qn VI:
  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 


			      ----------