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.