CSE 473

Spring 2004

Solutions for PS3 (non-programming part)

Problem 1 (R&N) 18.7. [4 points]

If one leaves out an example of one class, then the majority of the remaining examples are always of the other class. Thus the majority classifier will always predict the wrong answer.

Problem 2 (R&N 11.4 a, b, & d) [many alternate solutions are possible]

1. [2 points] Initial state is:

at(monkey, A) & At(bananas, B) & At(box, C) &

height(monkey, low) & height(bananas, high) &

pushable(box) & climbable(box)

2. [4 points] Actions are

action: go(?x, ?y)

precond: at(monkey, ?x) & ?x <> ?y

effect: at(monkey, ?y) & not(at(monkey, ?x)

action: push (?b, ?x, ?y)

precond: at(monkey, ?x) & pushable(?b) & ?x<>?y

effect: at(?b, ?y) & at(monkey, ?y) & not(at(?b, ?x)) & not(at(monkey, ?x))

action: climb-down (?b)

precond: on(monkey, ?b) & height(monkey, high)

effect: not(on(monkey, ?b)) & not(height(monkey, high)) &

height(monkey, low)

action: climb-up(?b)

precond: at(monkey, ?x) & at(?b, ?x) & climbable(?b) & height(monkey, low)

effect: on(monkey, ?b) & height(monkey, high) & not(height(monkey, low))

action: grasp(?o)

precond: height(monkey, ?h) & height(?o, ?h) & at(monkey, ?x) & at(?o, ?x)

effect: have(monkey, ?o) & not(at(?o, ?x)) & not(height(?o, ?h))

action: un-grasp(?o)

precond: height(monkey, ?h) & at(monkey, ?x) & have(monkey, ?o)

effect: not(have(monkey, ?o)) & at(?o, ?x) & height(?o, ?h)

4. [2 points] Qualification problem.

Add to initial state: weight(box, light)

Replace action:

action: push (?b, ?x, ?y)

precond: at(monkey, ?x) & pushable(?b) & ?x<>?y & weight(?b, light)

effect: at(?b, ?y) & at(monkey, ?y) & not(at(?b, ?x)) & not(at(monkey, ?x))

Problem 3 [R&N 11.17a, c]

1. [2 points] Yes. This will find a plan whenever the normal SATPlan finds a plan no longer than T_max. [But fundamentally this is a terrible idea because the cost of solving a SAT formula corresponding to a t+1 size planning problem is much, much greater than solving a t-sized problem and solving a t-1-sized problem and all the smaller problems. So trying to prove the existence of a short plan and only trying harder problems if that fails is a much faster method. This problem is designed to test your understanding of the principles, not to build a new, faster planner.]

3. [4 points] There is no simple and clear way to make WalkSAT find short solutions, because it has no notion of the length of a plan. The fact that the propositional variables refer to action-instances and fluents is part of the encoding – not part of WalkSAT. So the only way to do what we ask is to make some drastic changes to WalkSAT (which would be a real pain to implement, especially efficiently!) for example. One could identify (as a new input to WalkSAT or some implicit naming convention) different types of variables (e.g. which are action variables and what timestep do they occur) and then have WalkSAT preferentially:
• Tend to initialize acion variables with greater time values with a noop action (instead of a real action).
• Choose to flip the value of action and state variables more frequently if they refer to actions and fluents at early time steps.