CS5446-AI Planning and Decision Making Solved

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 eachplane 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, c0, p, a),

PRECOND: At(c, a) ∧ At(p, a) ∧¬In(c0,p) ∧ Cargo(c) ∧ Cargo(c0) ∧ 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,SFO).

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 ¯xp = E[x] = Px∈X p(x) ∗ x; the expected utility of the lottery would be E[u(x)] = Px∈X p(x) ∗ U(x). f(x) is a strictly convex function, since f0(x) = 2x, f00(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( ¯xp). We could conclude that Alice is 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.

 

2