Homework 1. Assigned [Sep 9, 2004] Due [Sep 20, 2004] Qn I. Consider the following "artificial" planning domain, which contains the (artificial) operators described below: operator O1 prec: P Eff: R, ~S operator O2 prec: Q Eff: S operator O3 prec: P Eff: M operator O4 prec: R,S Eff: P,Q,R,S operator O5 prec: R,S Eff: P The initial state is {P,Q} and the desired goals are {P,Q,R,S} I.a Show first level of the search tree generated by progression search. Also show the branch that leads to the goal state I.b Show first level of the search tree generated by regression search. Also show the branch that leads to the initial state I.c. Assuming that we do open condition P is considered first, show the *complete* set of partial plans generated by a POP planner to resolve this flaw. Also show the entire branch that leads to a solution plan (with annotations so I know you understand POP algorithm). II. Consider the following problem: Operator O1 eff: for all x If P1(x) then Q(x) for all x If P2(x) then Q(x) for all y If R(y) then W(y) for all u If M(u) then ~Q(u) for all u If N(u) then ~Q(u) Operator O2 forall x if J(x) then W(x) Init state: P1(a),J(a) [Remember--init state is complete. So we only specify things that are true; the rest are false] Goals: there exists x Q(x) ^ W(x) II.1. Assuming there are two objects, a and b in the domain, write down the set of "ground STRIPS operators" that correspond to O1. II.2. Using the lifted action representation, show how a regression planner solves this problem. Did you learn anything interesting about how regression will change in the presence of conditional and quantified effects? (Pay special attention to which goals O1 is being used to support in which branch; make sure you don't skip any possible branches...) II.3. Show how a partial order planner solves this problem.