Problem 1: Classical Planning
- (a) Consider the 8 puzzle with the Slide schema. Consider (i) ignoring Blank(s2) in the precondition as a heuristic and (ii) ignoring Blank(s2) ∧ Adjacent(s1, s2) in the precondition as a heuristic. Which of (i) or (ii) will result in fewer nodes being explored when used with the A* algorithm? Explain why.
Both are admissible heuristics for 8 puzzle. The first case h1 is actually the sum of Manhattan distance to goal for each tile; the second situation h2 is the number of misplaced tiles. h1 will always explore fewer nodes with A*. In other words, h1 dominates h2.
- (b) Consider the Air Cargo problem. Describe how to modify the problem so that each plane can only carry one cargo.
We could add a precondition for action Load to ensure there are not other cargo on the plane.
Action(Load(c, c′, p, a),
PRECOND:At(c, a)∧At(p, a)∧¬In(c′,p)∧Cargo(c)∧Cargo(c′)∧Plane(p)∧Airport(a)EFFECT: ¬At(c, a) ∧ In(c, p))
- (c) In the Air Cargo problem, write the successor state axiom for the fluent At(P1, SF O).
At(P1,SFO)t+1 ⇔ Fly(P1,JFK,SFO)t ∨ (At(P1,SFO)t ∧ ¬Fly(P1,SFO,JFK)t)
Problem 2: Decision Theory
- (a) Bob is risk adverse but rational. His utilities for A, B, and C are U(A) = 0, U(B) = 100 and U(C) = 40. He is given a choice between C and a lottery [0.4, A; 0.6, B]. Which would he choose and why?
The expected utility of the lottery is U(lottery) = 0.4 ∗ 0 + 0.6 ∗ 100 = 60 is bigger than U(c). An agent is rationally by choosing an action that maximizes the expected utility; therefore, Bob would choose to the lottery within two choices.
- (b) Alices utility function for money is U(x) = x. Argue that Alice is risk seeking. (Hint: U(x) is a strictly convex function. Jensens inequality may be useful here.)
For any lottery p,
the expected value of the lottery would be x ̄ = E[x] = p(x) ∗ x;
p x∈X
the expected utility of the lottery would be E[u(x)] = x∈X p(x) ∗ U(x).
f(x) is a strictly convex function, since f′(x) = 2x, f′′(x) = 2 > 0.
According to Jensen equality, for any strictly convex function, we have E[f(x)] >
f(E[x]), which means E[U(x)] > U(E[x]) = U(x ̄ ). We could conclude that Alice is p
risk seeking.
(c) Cathy prefers A to B but prefers lottery C = [0.2, A; 0.8, B] to lottery D = [0.3, A; 0.7, B]. Argue that there is no utility function that satisfies Cathy’s preferences.
Cathy prefers A to B, which means that U(A) > U(B);
Cathy prefers lottery C to lottery D, showing that U(lottery C) = 0.2 ∗ U(A) + 0.8 ∗ U(B) > U(lottery D) = 0.3 ∗ U(A) + 0.7 ∗ U(B). We get U(A) < U(B) after simplification. The two formulas are actually contradicted, which indicates that there is no utility function that satisfies Cathy’s preferences.
