AI: Problem Set 5

Assigned: Mar. 30
Due: Apr. 13

Consider the following microworld: There are a number of different locations; there are items to be moved from one location to another; and there are cases that hold the items. An item must be inside a case in order to be moved safely, but not all items fit inside all cases. Assume that a case can hold only one item at a time.

Thus conceptually there are three different kinds of actions:

For example, given the starting situation:
Item I1 is at location L1.
Case C1 is at location L2.
Item I2 is inside case C1.
I2 fits inside C1.
I1 fits inside C1.
and the goal ``Item I1 is at location L2,'' then that can be achieved with the following plan:
Take I2 out of C1.
Carry C1 to L1.
Put I1 into C1.
Carry C1 to L2.
(Depending on how you view the location of items inside cases, it may be desirable to add another step, ``Take I1 out of C1.'')

Problem 1

Show how this microworld can be encoded in the STRIPS representation. (Hint: It will be necessary to divide the action of moving an empty case from moving a case containing an object.)

Answer: As discussed in the email, the hint was in error. Only one action is needed.

The fluents are at(O,L) (Item or case O is at location L and not inside a case), empty(C) (case C is empty), and in(I,C) (item I is inside case C). There are atemporal predicates case(C) and fits(I,C) (Item I fits inside case C). The actions are:

Name: putin(I,C,L). 
Preconditions: at(I,L), at(C,L), empty(C), fits(I,C).
Add list: in(I,C),
Delete list: at(I,L), empty(C).

Name: takeout(I,C,L)
Preconditions: in(I,C), at(C,L).
Add list: at(I,L), empty(C)
Delete list: in(I,C).

Name: move(C,L1,L2)
Preconditions: at(C,L1)
Add list: at(C,L2)
Delete list: at(C,L1)
Constraints: L1 != L2.

Problem 2

Show how this microworld can be encoded in a propositional representation. Your description should be at the level of detail of the handout on propositional planning.

Answer: (Note: this is not the direct translation of the STRIPS representation. It is a more effficient representation, relying heavily on the domain constraints, in the style of the handout. There are many different possible answers.)

In all the following I ranges over items, C over cases, O over objects (items and cases), L over locations and T over times.

The fluents are at_O_L_T, in_I_C_T, and empty_C_T. The atoms in_I_C_T are only generated if I fits in C.

The actions are putin_I_C_L_T, takeout_I_C_L_T, and move_C_L_T. The atoms putin_I_C_L_T and takeout_I_C_L_T are generated only for I and C such that I fits in C.

Causal axioms:

putin_I_C_L_T => in_I_C_[T+1].
takeout_I_C_L_T => at_I_L_[T+1]
move_C_L_T => at_C_L_[T+1]  

Preconditions:

putin_I_C_L_T => at_I_L_T ^ at_C_L_T ^ empty_C_T.
takeout_I_C_L_T => in_I_C_T ^ at_C_L_T.
move_C_L can always be performed; hence, no precondition axiom is needed.

Domain constraints:

~(at_O_L1_T ^ at_O_L2_T) for each object O and locations L1 != L2.

~(at_I_L_T ^ in_I_C_T) for each item I, location L, and case C.

~(in_I_C1_T ^ in_I_C2_T) for each item I and cases C1 != C2.

at_I_L1_T V ... V at_I_Lk_T V in_I_C1_T V ... V in_I_Cm_T,
   where I is an item, L1 ... Lk range over the locations and C1 ... Cm
   range over the cases.

at_C_L1_T V ... V at_C_Lk_T.
   where I is an item and L1 ... Lk range over the locations. 

empty_C_T < = > ~(in_I1_C_T V in_I2_C_T V ... V in_Iq_C_T) 
   where C is a case and I1 ... I1 ranges over the items.

Frame axioms:

(~at_C_L_T ^ at_C_L_[T+1]) => move_C_L_T

(~at_I_L_T ^ at_I_L_[T+1]) => (takeout_I_C1_L_T V ... V takeout_I_Ck_L_T)
    where C1 ... Ck ranges over all the cases that I fits into.

(~in_I_C_T ^ in_I_C_[T+1]) => (putin_I_C_L1_T V ... V putin_I_C_Lm_T)
    where L1 ... Lm ranges over all the locations.
The frame axioms for "at" and "in" relations becoming false and the frame axioms for "empty" follow from the domain constraints.

One action at a time

~[move_C1_L1_T ^ move_C2_L2_T] where either C1 =! C2 or L1 != L2.
~[takeout_I1_C1_L1_T ^ takeout_I2_C2_L2_T] where either I1 != I2, C1 != C2,
    or L1 !=L2.
~[putin_I1_C1_L1_T ^ putin_I2_C2_L2_T] where either I1 != I2, C1 != C2,
    or L1 !=L2.
~[move_C1_L1_T ^ takeout_I2_C2_L2_T]
~[move_C1_L1_T ^ putin_I2_C2_L2_T]
~[takeout_I2_C2_L2_T ^ putin_I2_C2_L2_T]

Problem 3

Show how this microworld can be encoded in PDDL.

Answer:

(define  (domain cases)
   (:requirements adl)
   (:types physobj - object
           case item - physobj
           location - object)
   (:predicates (at ?x - physobj ?l - location)
                (in ?x - item ?c - case)
                (fits ?i - item  ?c - case)
                (empty ?c - case))
   (:action move 
       :parameters (?c - case ?l1 ?l2 - location)
       :effect (and (at ?c ?l1) (not (at ?c ?l2)))
       :precondition (and (at ?c ?l2) (not (= ?l1 ?l2)))
   (:action putin 
        :parameters (?i - item ?c - case ?l - location)
        :effect (and (in ?i ?c) (not (empty ?c)) (not (at ?i ?l)))
        :precondition (and (at ?i ?l) (at ?c ?l) (empty ?c) (fits ?i ?c)))
   (:action takeout
        :parameters (?i - item ?c - case ?l - location)
        :efffect (and (at ?i ?l) (empty ?c) (not (in ?i ?l)))
        :precondition (and (in ?i ?c) (at ?c ?l))))