Constructing the example

To answer these questions, we use the AlgebraicJulia tools at our disposal.

using Catlab
using DataMigrations;

In general, the steps for transferring a plan using an analogy are:

1. Define the source planning domain.
2. Create a plan in that source planning domain by: (i) defining an initial state and goal state and (ii) solving for a sequence of actions (rewrite rules) that gets you from the initial state to the goal.
3. Define the target planning domain.
4. Define an analogy from the target planning domain to the source planning domain.
5. Transfer the plan by transferring each state in the source plan to a state within the target planning domain.

In the framework of AlgebraicJulia:

• Planning domains will be presented as schema categories, based on FreeSchema.
• Planning states will be presented as attributed \mathsf{C}-sets, specified using @acset_colim.
• Analogies will be specified as a migration functor, @migration, from the target schema category to the source schema category.
• Plan transfer will be done using a functorial data migration, migrate(...).

Step 1: Tower of Hanoi Schema

For Question A. (“Could I stack blocks in Blocksworld like I am in Tower of Hanoi?”) above, the source planning domain is Tower of Hanoi. A schema category for this domain must capture the notions of disks, pegs, disks being on pegs, and a disk being smaller than another disk (per the table above). The schema category for Tower of Hanoi is:

@present OntTowerOfHanoi(FreeSchema) begin
  Disk::Ob
  Peg::Ob

  diskIsOnPeg::Hom(Disk, Peg)

  Smaller::Ob
  isSmaller_l::Hom(Smaller, Disk)
  isSmaller_r::Hom(Smaller, Disk)

  Clear::AttrType
  isClear::Attr(Disk, Clear)

  MyBool::AttrType
  MyString::AttrType
end
@acset_type TowerOfHanoi(OntTowerOfHanoi);

Note: MyBool and MyString are defined to allow AttrTypes in the target domain that do not have counterparts, such as isOnTable in Blocksworld, to be sent somewhere in the source domain.

Step 2: Plan in Tower of Hanoi

For this example, we’ve constructed a planning problem consisting of three disks where disk₁ < disk₂ < disk₃ (x < y means Disk x is smaller than Disk y). In this problem, we start off with disk₁ and disk₃ on peg₁ and disk₂ on peg₂. The goal is to have disk₁, disk₂, and disk₃ on peg₁.

Initial State, init. For this problem, we define the initial state using the follow ACSet:

To specify ACSets, it is necessary to define all the components of the functor, which can be cumbersome and confusing using the native specification for @acset (see examples in here).

Fortunately, we can use yTowerOfHanoi and @acset_colimit to compactly define states. Using these tools, we can label our set and function assignments using friendly terms, such as disk1, peg2, smaller1, and isClear(disk1) = true.

yTowerOfHanoi = yoneda(TowerOfHanoi{Bool,Bool,String});  
init = @acset_colim yTowerOfHanoi begin
  (disk1, disk2, disk3)::Disk
  (peg1, peg2, peg3)::Peg
  (smaller1, smaller2, smaller3)::Smaller
  isSmaller_l(smaller1) == disk1  # disk1 < disk2
  isSmaller_r(smaller1) == disk2
  isSmaller_l(smaller2) == disk2  # disk2 < disk3
  isSmaller_r(smaller2) == disk3
  isSmaller_l(smaller3) == disk1  # disk1 < disk3
  isSmaller_r(smaller3) == disk3
  diskIsOnPeg(disk1) == peg1
  diskIsOnPeg(disk2) == peg2
  diskIsOnPeg(disk3) == peg1
  isClear(disk1) == true
  isClear(disk2) == false
  isClear(disk3) == true
end;

Goal State, goal. And the goal state is specified using the follow ACSet:

goal = @acset_colim yTowerOfHanoi begin
  (disk1, disk2, disk3)::Disk
  (peg1, peg2, peg3)::Peg
  (smaller1, smaller2, smaller3)::Smaller
  isSmaller_l(smaller1) == disk1  # disk1 < disk2
  isSmaller_r(smaller1) == disk2
  isSmaller_l(smaller2) == disk2  # disk2 < disk3
  isSmaller_r(smaller2) == disk3
  isSmaller_l(smaller3) == disk1  # disk1 < disk3
  isSmaller_r(smaller3) == disk3
  diskIsOnPeg(disk1) == peg1
  diskIsOnPeg(disk2) == peg1
  diskIsOnPeg(disk3) == peg1
  isClear(disk1) == true
  isClear(disk2) == false
  isClear(disk3) == true
end;

Given this problem, it is straightforward to solve for a plan in our heads. One reasonable solution involves two intermediate states that result in: (i) disk₁ being on peg₃, and (ii) disk₂ being on peg₁. The next state would be the goal state.

The intermediate states at ACSets look like:

Plan. The plan, therefore, passes through states [init, state₁, state₂, goal] in order.

Step 3: Blocksworld Schema

In this example, the target planning domain is Blocksworld. The schema category should capture the notions of blocks, a block being on another block, and blocks being on the table (per the table above). The schema category for Blocksworld is:

@present OntBlocksworld(FreeSchema) begin
  Block::Ob

  InOn::Ob
  inOn_l::Hom(InOn, Block) 
  inOn_r::Hom(InOn, Block)

  Clear::AttrType
  isClear::Attr(Block, Clear)
  OnTable::AttrType
  isOnTable::Attr(Block, OnTable)

  MyBool::AttrType
  MyString::AttrType
end
@acset_type Blocksworld(OntBlocksworld);

Step 4: Define the analogy

Now that we have defined the two planning domains, we can define an analogy between them using a migration functor. This migration functor is from the Blocksworld schema category to the Tower of Hanoi schema category (Note: This is contravariant relative to the direction of plan transfer. See (Spivak and Kent 2012) for contravariant data migrations.)

Each component of the Blocksworld schema category (namely every ::Ob, ::Hom, ::AttrType, and ::Attr) must correspond to a structure based on the Tower of Hanoi schema category. Most of the components have trivial analogies that can be reasoned by quick intuition, such as Block => Disk and Clear => Clear.

This migration, however, establishes two non-trivial correspondences: (i) the assignment of InOn relations and (ii) the assignment of the isOnTable attribute.

Assigning InOn. When defining this migration functor, we are faced with the situation where the notion of IsOn is not present in the Tower of Hanoi planning domain. All is not lost, however, because we can infer the ordering of the disks based purely on the fact that one disk is smaller than another and the pair of disks are on the same peg. This can be captured by describing an abstracted pattern of this phenomena:

  ...
  InOn => @join begin
    disk1::Disk
    disk2::Disk
    peg::Peg
    diskIsOnPeg(disk1) == peg
    diskIsOnPeg(disk2) == peg
    smaller::Smaller
    isSmaller_l(smaller) == disk1  # disk1 < disk2
    isSmaller_r(smaller) == disk2
  end  # a disk is on another if it is smaller and on the same peg
  inOn_l => disk1
  inOn_r => disk2
  ...

In AlgebraicJulia, this pattern is a diagram forming a conjuctive query, @join.

Assigning isOnTable. Perhaps the more difficult situation we find ourselves in is how we assign a corresponding Boolean value to the attribute isOnTable. In Tower of Hanoi, the notion of disks being on a table is not capture. However, intuitively we can see that a disk being on the table is analogous to being at the bottom of a stack for a given peg. This is true when a disk is the largest disk of all the disks on the same peg. We can define an anonymous Julia function, given by ((x -> begin ... end)), that determines this value.

  ...
  # A disk, x, is on the table if it is the largest disk on a peg.
  isOnTable => (x -> begin

    # Step 1. Get the peg that the disk `x` is on
    p = diskIsOnPeg(x) 

    # Step 2. Get all the disks on the same peg as `x`
    dop = [i for (i, x) in enumerate(collect(diskIsOnPeg)) if x == p]

    # Step 3. Filter `smaller` to only relations that involve the disks 
    # that were selected
    smaller′ =  [
      i 
      for (i, rel) in enumerate(zip(collect(isSmaller_l), collect(isSmaller_r))) 
      if all(d -> d in dop, rel)
    ]

    # Step 4. Check if disk is not contained in `isSmaller_l` in `smaller′`
    !(x in collect(isSmaller_l)[smaller′]) 
  end) 
  ...

We can determine that the variable x refers to a Disk because the source object of isOnTable::Hom(Block, onTable) is Block and we know that Block => Disk in our migration functor.

Putting this all together, we get the following migration functor:

F = @migration OntBlocksworld OntTowerOfHanoi begin
  Block => Disk
  InOn => @join begin
    disk1::Disk
    disk2::Disk
    peg::Peg
    diskIsOnPeg(disk1) == peg
    diskIsOnPeg(disk2) == peg
    smaller::Smaller
    isSmaller_l(smaller) == disk1  # disk1 < disk2
    isSmaller_r(smaller) == disk2
  end  # a disk is on another if it is smaller and on the same peg
  inOn_l => disk1
  inOn_r => disk2
  Clear => Clear
  isClear => isClear
  OnTable => MyBool
  isOnTable => (x -> begin
    p = diskIsOnPeg(x) 
    dop = [i for (i, x) in enumerate(collect(diskIsOnPeg)) if x == p]
    smaller′ =  [
      i 
      for (i, rel) in enumerate(zip(collect(isSmaller_l), collect(isSmaller_r))) 
      if all(d -> d in dop, rel)
    ]
    !(x in collect(isSmaller_l)[smaller′]) 
  end) 
  MyBool => MyBool
  MyString => MyString
end;

Once defined, this never needs to be defined again. This means that we can transfer any plan in Tower of Hanoi to an analogous Blocksworld plan using this specification.

Step 5: Transfer Plan

To transfer a plan, we can now very easily migrate each state in the Tower of Hanoi plan using a functorial data migration:

new_init = migrate(Blocksworld,  init, F)
new_state₁ = migrate(Blocksworld, state₁, F)
new_state₂ = migrate(Blocksworld, state₂, F)
new_goal = migrate(Blocksworld, goal, F)

We will address why we are migrating states instead of whole rewrite rules later in the post.

Therefore, the new plan in Blocksworld will look like:

Valid: Tower of Hanoi to Blocksworld

We have determined that seeking an analoguous Tower of Hanoi plan in the Blocksworld domain is a valid inquiry and can be computed. This is because the data migration is (suspected to be) functorial.

That is: the relationships that define how a Tower of Hanoi state behaves can be meaningfully interpreted within Blocksworld. The idea of a disk being on another—defined relationally as “smaller and on the same peg”—translates naturally into the InOn structure in Blocksworld. Similarly, a disk being at the bottom of the peg (i.e., the largest on that peg) maps correctly to a block being isOnTable.

So even though Blocksworld has no concept of “pegs” and Tower of Hanoi has no explicit notion of “on-ness,” the mapping works because the structure of relationships is preserved.

Invalid: Blocksworld to Tower of Hanoi

Now, checking that a Blocksworld plan works in the Tower of Hanoi domain is a different story.

Blocksworld doesn’t impose size constraints. It doesn’t distinguish between placing a smaller block on a larger one—or the reverse. It doesn’t have pegs, and it doesn’t require exclusivity about what “stack” a block belongs to. So if we try to map a Blocksworld plan back into Tower of Hanoi, we run into trouble.

# Not valid code
F⁻¹ = @migration OntTowerOfHanoi OntBlocksworld begin
  Disk => Block
  Peg => ??  # no notion of stack position
  diskIsOnPeg => ?? # no notion of blocks on "pegs"
  Smaller => ??  # smaller does not imply on top of
  isSmaller_l => ??
  isSmaller_r => ??
  Clear => Clear
  isClear => isClear
end

Why? Because Tower of Hanoi expects more structure than Blocksworld can provide. The destination domain asks questions that the source domain can’t answer.

Without extra information, we can’t make that translation… and that’s okay. Not all mappings are invertible, which perhaps signals something far more interesting–the lack of a true analogy from Blocksworld to Tower of Hanoi.