Not Enough Thoughts

Hhop: blocks world (part 3)

This is the last of a series of posts showing how to use Hhop to do HTN planning in a blocks world. The first post showed the specification of the world and the primitive actions, and the second showed how to specify domain knowledge in the form of a set of methods for moving blocks to some desired goal position. Now, I’ll finish up with some simple examples.

The contents of this post come from the source of the Hhop.Blocks.Example module.

> module Hhop.Blocks.Example where
> import Hhop.Plan
> import Hhop.Util
> import Hhop.Blocks.World
> import Hhop.Blocks.Tasks
> import qualified Data.Map as M

We define a simple example blocks world, with 3 blocks.

> data Ex =
>   A | B | C
>   deriving (Bounded, Enum, Eq, Ord, Show)

For a starting state, block A is on B, and B and C are both on the table.

> state :: BlocksWorld Ex
> state = M.fromList [
>   (A, OnBlock B),
>   (B, OnTable),
>   (C, OnTable)
>   ]

We wish to build a stack of three blocks, A, B, C, in order from bottom to top.

> goal :: BlocksGoal Ex
> goal = M.fromList [
>   (C, B),
>   (B, A)
>   ]

Now, we can search for plans that, given the blocks domain, achieve the task of moving all blocks to their goal positions.

> plans :: [[BlocksPrim Ex]]
> plans = plan blocksDomain state (Move goal .> done)

A single plan is returned.

[[UnStack A B,PutDown A,PickUp B,Stack B A,PickUp C,Stack C B]]

We define a slightly larger world, with 4 blocks. To avoid name collisions, I’ll start with the letter D. In a real program, I’d probably use module namespaces to avoid that sort of thing.

> data Ex2 =
>   D | E | F | G
>   deriving (Bounded, Enum, Eq, Ord, Show)

The starting state is D on F, and E on G.

> state2 :: BlocksWorld Ex2
> state2 = M.fromList [
>   (D, OnBlock F),
>   (E, OnBlock G),
>   (F, OnTable),
>   (G, OnTable)
>   ]

The goal is to rearrange the stacks, so D is on G and E is on F.

> goal2 :: BlocksGoal Ex2
> goal2 = M.fromList [
>   (D, G),
>   (E, F)
>   ]

As before, search for plans that move all blocks to their goal position.

> plans2 :: [[BlocksPrim Ex2]]
> plans2 = plan blocksDomain state2 (Move goal2 .> done)

Again, several possible plans are found. With four blocks, there’s a few more options.

[[UnStack D F,PutDown D,UnStack E G,Stack E F,PickUp D,Stack D G],[UnStack D F,PutDown D,UnStack E G,PutDown E,PickUp D,Stack D G,PickUp E,Stack E F],[UnStack D F,PutDown D,UnStack E G,PutDown E,PickUp E,Stack E F,PickUp D,Stack D G],[UnStack E G,PutDown E,UnStack D F,Stack D G,PickUp E,Stack E F],[UnStack E G,PutDown E,UnStack D F,PutDown D,PickUp D,Stack D G,PickUp E,Stack E F],[UnStack E G,PutDown E,UnStack D F,PutDown D,PickUp E,Stack E F,PickUp D,Stack D G]]

This planning problem is bw_large_d from the SHOP distribution, and includes 19 blocks.

> data Ex3 =
>   H1 | H2 | H3 | H4 | H5 | H6 | H7 | H8 | H9 | H10 |
>   H11 | H12 | H13 | H14 | H15 | H16 | H17 | H18 | H19
>   deriving (Bounded, Enum, Eq, Ord, Show)
> state3 :: BlocksWorld Ex3
> state3 = M.fromList [
>   (H1, OnBlock H12),
>   (H12, OnBlock H13),
>   (H13, OnTable),
>   (H11, OnBlock H10),
>   (H10, OnBlock H5),
>   (H5, OnBlock H4),
>   (H4, OnBlock H14),
>   (H14, OnBlock H15),
>   (H15, OnTable),
>   (H9, OnBlock H8),
>   (H8, OnBlock H7),
>   (H7, OnBlock H6),
>   (H6, OnTable),
>   (H19, OnBlock H18),
>   (H18, OnBlock H17),
>   (H17, OnBlock H16),
>   (H16, OnBlock H3),
>   (H3, OnBlock H2),
>   (H2, OnTable)
>   ]
> goal3 :: BlocksGoal Ex3
> goal3 = M.fromList [
>   (H15, H13),
>   (H13, H8),
>   (H8, H9),
>   (H9, H4),
>   (H12, H2),
>   (H2, H3),
>   (H3, H16),
>   (H16, H11),
>   (H11, H7),
>   (H7, H6)
>   ]
> plans3 :: [[BlocksPrim Ex3]]
> plans3 = plan blocksDomain state3 (Move goal3 .> done)

There is an extremely large number of possible plans: since it doesn’t really matter what order we move most of the blocks, the set of possible sequences of moves is growing exponentially with the number of blocks. We’ll look only at the first plan found:

head plans3
[UnStack H1 H12,PutDown H1,UnStack H9 H8,PutDown H9,UnStack H8 H7,PutDown H8,UnStack H11 H10,Stack H11 H7,UnStack H10 H5,PutDown H10,UnStack H5 H4,PutDown H5,UnStack H4 H14,PutDown H4,PickUp H9,Stack H9 H4,PickUp H8,Stack H8 H9,UnStack H12 H13,PutDown H12,PickUp H13,Stack H13 H8,UnStack H14 H15,PutDown H14,PickUp H15,Stack H15 H13,UnStack H19 H18,PutDown H19,UnStack H18 H17,PutDown H18,UnStack H17 H16,PutDown H17,UnStack H16 H3,Stack H16 H11,UnStack H3 H2,Stack H3 H16,PickUp H2,Stack H2 H3,PickUp H12,Stack H12 H2]