February 19

More planning.

  • Air Cargo
  • Spare Tire
  • Three Block Tower
  • Shopping
  • Socks and Shoes
  • Cake
In [1]:
from planning import *
from notebook import psource

Air Cargo Problem

In the Air Cargo problem, we start with cargo at two airports, SFO and JFK. Our goal is to send each cargo to the other airport. We have two airplanes to help us accomplish the task. The problem can be defined with three actions: Load, Unload and Fly. Let us look how the air_cargo problem has been defined in the module.

In [2]:
psource(air_cargo)


def air_cargo():
    """
    [Figure 10.1] AIR-CARGO-PROBLEM

    An air-cargo shipment problem for delivering cargo to different locations,
    given the starting location and airplanes.

    Example:
    >>> from planning import *
    >>> ac = air_cargo()
    >>> ac.goal_test()
    False
    >>> ac.act(expr('Load(C2, P2, JFK)'))
    >>> ac.act(expr('Load(C1, P1, SFO)'))
    >>> ac.act(expr('Fly(P1, SFO, JFK)'))
    >>> ac.act(expr('Fly(P2, JFK, SFO)'))
    >>> ac.act(expr('Unload(C2, P2, SFO)'))
    >>> ac.goal_test()
    False
    >>> ac.act(expr('Unload(C1, P1, JFK)'))
    >>> ac.goal_test()
    True
    >>>
    """

    return PlanningProblem(init='At(C1, SFO) & At(C2, JFK) & At(P1, SFO) & At(P2, JFK) & Cargo(C1) & Cargo(C2) & Plane(P1) & Plane(P2) & Airport(SFO) & Airport(JFK)', 
                goals='At(C1, JFK) & At(C2, SFO)',
                actions=[Action('Load(c, p, a)', 
                                precond='At(c, a) & At(p, a) & Cargo(c) & Plane(p) & Airport(a)',
                                effect='In(c, p) & ~At(c, a)'),
                         Action('Unload(c, p, a)',
                                precond='In(c, p) & At(p, a) & Cargo(c) & Plane(p) & Airport(a)',
                                effect='At(c, a) & ~In(c, p)'),
                         Action('Fly(p, f, to)',
                                precond='At(p, f) & Plane(p) & Airport(f) & Airport(to)',
                                effect='At(p, to) & ~At(p, f)')])

At(c, a): The cargo 'c' is at airport 'a'.

~At(c, a): The cargo 'c' is not at airport 'a'.

In(c, p): Cargo 'c' is in plane 'p'.

~In(c, p): Cargo 'c' is not in plane 'p'.

Cargo(c): Declare 'c' as cargo.

Plane(p): Declare 'p' as plane.

Airport(a): Declare 'a' as airport.

In the initial_state, we have cargo C1, plane P1 at airport SFO and cargo C2, plane P2 at airport JFK. Our goal state is to have cargo C1 at airport JFK and cargo C2 at airport SFO. We will discuss on how to achieve this. Let us now define an object of the air_cargo problem:

In [3]:
airCargo = air_cargo()
In [4]:
airCargo.goal_test()
Out[4]:
False
In [5]:
airCargo.init
Out[5]:
[At(C1, SFO),
 At(C2, JFK),
 At(P1, SFO),
 At(P2, JFK),
 Cargo(C1),
 Cargo(C2),
 Plane(P1),
 Plane(P2),
 Airport(SFO),
 Airport(JFK)]
In [6]:
airCargo.goals
Out[6]:
[At(C1, JFK), At(C2, SFO)]

It returns False because the goal state is not yet reached. Now, we define the sequence of actions that it should take in order to achieve the goal. The actions are then carried out on the airCargo PlanningProblem.

The actions available to us are the following: Load, Unload, Fly

Load(c, p, a): Load cargo 'c' into plane 'p' from airport 'a'.

Fly(p, f, t): Fly the plane 'p' from airport 'f' to airport 't'.

Unload(c, p, a): Unload cargo 'c' from plane 'p' to airport 'a'.

This problem can have multiple valid solutions. One such solution is shown below.

In [7]:
solution = [expr("Load(C1 , P1, SFO)"),
            expr("Fly(P1, SFO, JFK)"),
            expr("Unload(C1, P1, JFK)"),
            expr("Load(C2, P2, JFK)"),
            expr("Fly(P2, JFK, SFO)"),
            expr("Unload (C2, P2, SFO)")] 

for action in solution:
    airCargo.act(action)
In [8]:
airCargo.goal_test()
Out[8]:
True
In [9]:
airCargo.init
Out[9]:
[Cargo(C1),
 Cargo(C2),
 Plane(P1),
 Plane(P2),
 Airport(SFO),
 Airport(JFK),
 NotAt(C1, SFO),
 At(P1, JFK),
 NotAt(P1, SFO),
 At(C1, JFK),
 NotIn(C1, P1),
 NotAt(C2, JFK),
 At(P2, SFO),
 NotAt(P2, JFK),
 At(C2, SFO),
 NotIn(C2, P2)]

The Spare Tire Problem

Let's consider the problem of changing a flat tire of a car. The goal is to mount a spare tire onto the car's axle, given that we have a flat tire on the axle and a spare tire in the trunk.

In [10]:
psource(spare_tire)


def spare_tire():
    """[Figure 10.2] SPARE-TIRE-PROBLEM

    A problem involving changing the flat tire of a car
    with a spare tire from the trunk.

    Example:
    >>> from planning import *
    >>> st = spare_tire()
    >>> st.goal_test()
    False
    >>> st.act(expr('Remove(Spare, Trunk)'))
    >>> st.act(expr('Remove(Flat, Axle)'))
    >>> st.goal_test()
    False
    >>> st.act(expr('PutOn(Spare, Axle)'))
    >>> st.goal_test()
    True
    >>>
    """

    return PlanningProblem(init='Tire(Flat) & Tire(Spare) & At(Flat, Axle) & At(Spare, Trunk)',
                goals='At(Spare, Axle) & At(Flat, Ground)',
                actions=[Action('Remove(obj, loc)',
                                precond='At(obj, loc)',
                                effect='At(obj, Ground) & ~At(obj, loc)'),
                         Action('PutOn(t, Axle)',
                                precond='Tire(t) & At(t, Ground) & ~At(Flat, Axle)',
                                effect='At(t, Axle) & ~At(t, Ground)'),
                         Action('LeaveOvernight',
                                precond='',
                                effect='~At(Spare, Ground) & ~At(Spare, Axle) & ~At(Spare, Trunk) & \
                                        ~At(Flat, Ground) & ~At(Flat, Axle) & ~At(Flat, Trunk)')])

At(obj, loc): object 'obj' is at location 'loc'.

~At(obj, loc): object 'obj' is not at location 'loc'.

Tire(t): Declare a tire of type 't'.

Let us now define an object of spare_tire problem:

In [11]:
spareTire = spare_tire()
In [12]:
spareTire.goal_test()
Out[12]:
False

As we can see, it hasn't completed the goal. We now define a possible solution that can help us reach the goal of having a spare tire mounted onto the car's axle. The actions are then carried out on the spareTire PlanningProblem.

The actions available to us are the following: Remove, PutOn

Remove(obj, loc): Remove the tire 'obj' from the location 'loc'.

PutOn(t, Axle): Attach the tire 't' on the Axle.

LeaveOvernight(): We live in a particularly bad neighborhood and all tires, flat or not, are stolen if we leave them overnight.

In [13]:
solution = [expr("Remove(Flat, Axle)"),
            expr("Remove(Spare, Trunk)"),
            expr("PutOn(Spare, Axle)")]

for action in solution:
    spareTire.act(action)
In [14]:
spareTire.goal_test()
Out[14]:
True

Here is another way to solve the problem:

In [15]:
spareTire = spare_tire()

solution = [expr('Remove(Spare, Trunk)'),
            expr('Remove(Flat, Axle)'),
            expr('PutOn(Spare, Axle)')]

for action in solution:
    spareTire.act(action)
In [16]:
spareTire.goal_test()
Out[16]:
True
In [17]:
spareTire.init
Out[17]:
[Tire(Flat),
 Tire(Spare),
 NotAt(Spare, Trunk),
 At(Flat, Ground),
 NotAt(Flat, Axle),
 At(Spare, Axle),
 NotAt(Spare, Ground)]

Notice that both solutions work, which means that the problem can be solved irrespective of the order in which the Remove actions take place, as long as both Remove actions take place before the PutOn action.

We have successfully mounted a spare tire onto the axle.

Three Block Tower Problem

This problem's domain consists of a set of cube-shaped blocks sitting on a table. The blocks can be stacked, but only one block can fit directly on top of another. A robot arm can pick up a block and move it to another position, either on the table or on top of another block. The arm can pick up only one block at a time, so it cannot pick up a block that has another one on it. The goal will always be to build one or more stacks of blocks. In our case, we consider only three blocks. The particular configuration we will use is called the Sussman anomaly after Prof. Gerry Sussman.

In [18]:
psource(three_block_tower)


def three_block_tower():
    """
    [Figure 10.3] THREE-BLOCK-TOWER

    A blocks-world problem of stacking three blocks in a certain configuration,
    also known as the Sussman Anomaly.

    Example:
    >>> from planning import *
    >>> tbt = three_block_tower()
    >>> tbt.goal_test()
    False
    >>> tbt.act(expr('MoveToTable(C, A)'))
    >>> tbt.act(expr('Move(B, Table, C)'))
    >>> tbt.goal_test()
    False
    >>> tbt.act(expr('Move(A, Table, B)'))
    >>> tbt.goal_test()
    True
    >>>
    """

    return PlanningProblem(init='On(A, Table) & On(B, Table) & On(C, A) & Block(A) & Block(B) & Block(C) & Clear(B) & Clear(C)',
                goals='On(A, B) & On(B, C)',
                actions=[Action('Move(b, x, y)',
                                precond='On(b, x) & Clear(b) & Clear(y) & Block(b) & Block(y)',
                                effect='On(b, y) & Clear(x) & ~On(b, x) & ~Clear(y)'),
                         Action('MoveToTable(b, x)',
                                precond='On(b, x) & Clear(b) & Block(b)',
                                effect='On(b, Table) & Clear(x) & ~On(b, x)')])

On(b, x): The block 'b' is on 'x'. 'x' can be a table or a block.

~On(b, x): The block 'b' is not on 'x'. 'x' can be a table or a block.

Block(b): Declares 'b' as a block.

Clear(x): To indicate that there is nothing on 'x' and it is free to be moved around.

~Clear(x): To indicate that there is something on 'x' and it cannot be moved.

Let us now define an object of three_block_tower problem:

In [19]:
threeBlockTower = three_block_tower()
In [20]:
threeBlockTower.goal_test()
Out[20]:
False
In [21]:
threeBlockTower.init
Out[21]:
[On(A, Table),
 On(B, Table),
 On(C, A),
 Block(A),
 Block(B),
 Block(C),
 Clear(B),
 Clear(C)]
In [22]:
threeBlockTower.goals
Out[22]:
[On(A, B), On(B, C)]

As we can see, it hasn't completed the goal. We now define a sequence of actions that can stack three blocks in the required order. The actions are then carried out on the threeBlockTower PlanningProblem.

The actions available to us are the following: MoveToTable, Move

MoveToTable(b, x): Move box 'b' stacked on 'x' to the table, given that box 'b' is clear.

Move(b, x, y): Move box 'b' stacked on 'x' to the top of 'y', given that both 'b' and 'y' are clear.

In [23]:
solution = [expr("MoveToTable(C, A)"),
            expr("Move(B, Table, C)"),
            expr("Move(A, Table, B)")]

for action in solution:
    threeBlockTower.act(action)
In [24]:
threeBlockTower.init
Out[24]:
[Block(A),
 Block(B),
 Block(C),
 On(C, Table),
 Clear(A),
 NotOn(C, A),
 On(B, C),
 Clear(Table),
 NotOn(B, Table),
 NotClear(C),
 On(A, B),
 Clear(Table),
 NotOn(A, Table),
 NotClear(B)]
In [25]:
threeBlockTower.goal_test()
Out[25]:
True

Shopping Problem

This problem requires us to acquire a carton of milk, a banana and a drill. Initially, we start from home and it is known to us that milk and bananas are available in the supermarket and the hardware store sells drills. Let's take a look at the definition of the shopping_problem in the module.

In [26]:
psource(shopping_problem)


def shopping_problem():
    """
    SHOPPING-PROBLEM

    A problem of acquiring some items given their availability at certain stores.

    Example:
    >>> from planning import *
    >>> sp = shopping_problem()
    >>> sp.goal_test()
    False
    >>> sp.act(expr('Go(Home, HW)'))
    >>> sp.act(expr('Buy(Drill, HW)'))
    >>> sp.act(expr('Go(HW, SM)'))
    >>> sp.act(expr('Buy(Banana, SM)'))
    >>> sp.goal_test()
    False
    >>> sp.act(expr('Buy(Milk, SM)'))
    >>> sp.goal_test()
    True
    >>>
    """

    return PlanningProblem(init='At(Home) & Sells(SM, Milk) & Sells(SM, Banana) & Sells(HW, Drill)',
                goals='Have(Milk) & Have(Banana) & Have(Drill)', 
                actions=[Action('Buy(x, store)',
                                precond='At(store) & Sells(store, x)',
                                effect='Have(x)'),
                         Action('Go(x, y)',
                                precond='At(x)',
                                effect='At(y) & ~At(x)')])

At(x): Indicates that we are currently at 'x' where 'x' can be Home, SM (supermarket) or HW (Hardware store).

~At(x): Indicates that we are currently not at 'x'.

Sells(s, x): Indicates that item 'x' can be bought from store 's'.

Have(x): Indicates that we possess the item 'x'.

In [27]:
shoppingProblem = shopping_problem()
In [28]:
shoppingProblem.init
Out[28]:
[At(Home), Sells(SM, Milk), Sells(SM, Banana), Sells(HW, Drill)]
In [29]:
shoppingProblem.goal_test()
Out[29]:
False

Let's look at the possible actions

Buy(x, store): Buy an item 'x' from a 'store' given that the 'store' sells 'x'.

Go(x, y): Go to destination 'y' starting from source 'x'.

We now define a valid solution that will help us reach the goal. The sequence of actions will then be carried out onto the shoppingProblem PlanningProblem.

In [30]:
solution = [expr('Go(Home, SM)'),
            expr('Buy(Milk, SM)'),
            expr('Buy(Banana, SM)'),
            expr('Go(SM, HW)'),
            expr('Buy(Drill, HW)')]

for action in solution:
    shoppingProblem.act(action)
In [31]:
shoppingProblem.goal_test()
Out[31]:
True
In [32]:
shoppingProblem.init
Out[32]:
[Sells(SM, Milk),
 Sells(SM, Banana),
 Sells(HW, Drill),
 NotAt(Home),
 Have(Milk),
 Have(Banana),
 At(HW),
 NotAt(SM),
 Have(Drill)]

Socks and Shoes

This is a simple problem of putting on a pair of socks and shoes. The problem is defined in the module as given below.

In [33]:
psource(socks_and_shoes)


def socks_and_shoes():
    """
    SOCKS-AND-SHOES-PROBLEM

    A task of wearing socks and shoes on both feet

    Example:
    >>> from planning import *
    >>> ss = socks_and_shoes()
    >>> ss.goal_test()
    False
    >>> ss.act(expr('RightSock'))
    >>> ss.act(expr('RightShoe'))
    >>> ss.act(expr('LeftSock'))
    >>> ss.goal_test()
    False
    >>> ss.act(expr('LeftShoe'))
    >>> ss.goal_test()
    True
    >>>
    """

    return PlanningProblem(init='',
                goals='RightShoeOn & LeftShoeOn',
                actions=[Action('RightShoe',
                                precond='RightSockOn',
                                effect='RightShoeOn'),
                        Action('RightSock',
                                precond='',
                                effect='RightSockOn'),
                        Action('LeftShoe',
                                precond='LeftSockOn',
                                effect='LeftShoeOn'),
                        Action('LeftSock',
                                precond='',
                                effect='LeftSockOn')])

LeftSockOn: Indicates that we have already put on the left sock.

RightSockOn: Indicates that we have already put on the right sock.

LeftShoeOn: Indicates that we have already put on the left shoe.

RightShoeOn: Indicates that we have already put on the right shoe.

In [34]:
socksShoes = socks_and_shoes()
In [36]:
socksShoes.goal_test()
Out[36]:
False
In [37]:
solution = [expr('RightSock'),
            expr('RightShoe'),
            expr('LeftSock'),
            expr('LeftShoe')]

for action in solution:
    socksShoes.act(action)
    
socksShoes.goal_test()
Out[37]:
True

Cake Problem

This problem requires us to reach the state of having a cake and having eaten a cake simlutaneously, given a single cake. Let's first take a look at the definition of the have_cake_and_eat_cake_too problem in the module.

In [39]:
psource(have_cake_and_eat_cake_too)


def have_cake_and_eat_cake_too():
    """
    [Figure 10.7] CAKE-PROBLEM

    A problem where we begin with a cake and want to 
    reach the state of having a cake and having eaten a cake.
    The possible actions include baking a cake and eating a cake.

    Example:
    >>> from planning import *
    >>> cp = have_cake_and_eat_cake_too()
    >>> cp.goal_test()
    False
    >>> cp.act(expr('Eat(Cake)'))
    >>> cp.goal_test()
    False
    >>> cp.act(expr('Bake(Cake)'))
    >>> cp.goal_test()
    True
    >>>
    """

    return PlanningProblem(init='Have(Cake)',
                goals='Have(Cake) & Eaten(Cake)',
                actions=[Action('Eat(Cake)',
                                precond='Have(Cake)',
                                effect='Eaten(Cake) & ~Have(Cake)'),
                         Action('Bake(Cake)',
                                precond='~Have(Cake)',
                                effect='Have(Cake)')])

Since this problem doesn't involve variables, states can be considered similar to symbols in propositional logic.

Have(Cake): Declares that we have a 'Cake'.

~Have(Cake): Declares that we don't have a 'Cake'.

In [40]:
cakeProblem = have_cake_and_eat_cake_too()
In [41]:
cakeProblem.goal_test()
Out[41]:
False

Let us look at the possible actions.

Bake(x): To bake ' x '.

Eat(x): To eat ' x '.

We now define a valid solution that can help us reach the goal. The sequence of actions will then be acted upon the cakeProblem PlanningProblem.

In [42]:
solution = [expr("Eat(Cake)"),
            expr("Bake(Cake)")]

for action in solution:
    cakeProblem.act(action)
    
cakeProblem.goal_test()
Out[42]:
True

One might wonder if the order of the actions matters for this problem. It did not matter in the spare tire problem. Let's see for ourselves.

In [43]:
cakeProblem = have_cake_and_eat_cake_too()

solution = [expr('Bake(Cake)'),
            expr('Eat(Cake)')]

for action in solution:
    cakeProblem.act(action)

---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-43-b340f831489f> in <module>
      5 
      6 for action in solution:
----> 7     cakeProblem.act(action)

/home/classes/cs470/hws/aima/planning.py in act(self, action)
     58             raise Exception("Action '{}' not found".format(action_name))
     59         if not list_action.check_precond(self.init, args):
---> 60             raise Exception("Action '{}' pre-conditions not satisfied".format(action))
     61         self.init = list_action(self.init, args).clauses
     62 

Exception: Action 'Bake(Cake)' pre-conditions not satisfied

It raises an exception. Indeed, according to the problem, we cannot bake a cake if we already have one. In planning terms, '~Have(Cake)' is a precondition to the action 'Bake(Cake)'. Hence, this solution is invalid.

In [ ]: