Towers of Hanoi

In this exercise, we will use telingo to play with a classical planning problem: the Towers of Hanoi. In the original version, we have three poles, let us call them a, b and c, and a set of n holed disks, all of them of different sizes (different diameter). For simplicity, we will assume that each disk is represented as a number that also stands for its size, so that we would have disks from 1 (the smallest disk) to n (the largest disk). In the initial state, all disks form a tower at pole a as shown in the image (for n=5):

The final goal is forming the same tower but on pole c. At each step, we can only move one disk from the top of one pole to the top of another pole. For instance, at the initial state shown above, the two possible actions are move(a,b) or move(a,c). The main constraint of the puzzle is that we can never put a disk D on top a smaller disk C<D. As an example, if we start in the initial state and perform move(a,b)in the first step (leaving disk 1 on pole b), we cannot perform again move(a,b)as the second action, because that would leave now disk 2 on top of the smaller disk 1.

We will implement a planner in telingo for solving this problem, but allowing different initial and goal states, and leaving the possibility of varying the set of poles.

What to do

• Encode the planning problem in telingo, but separate the general encoding hanoi.lp from the different problem instances tower01.lp, tower02.lp, you try, depending on the configuration (poles, disks in the initial state, disks in the goal state) for each scenario. Each execution would look like
  
      telingo hanoi.lp towers01.lp
  
  The solutions must be expressed as sequences of predicate move(P,Q)meaning that we move the top disk from pole P to the top of pole Q.
•  Solve the standard Tower of Hanoi problem (with poles a,b,c) varying the number of disks.
  
  Question 1: How many disks can you handle with a timeout of 1 minute?
  
  The sequence of actions for moving all the poles corresponds to the well-known strategy moveplan(N,P,Q,A) meaning "move N disks from P to Q using A as auxiliary pole". This relation is recursively described as follows:
  
  moveplan(N,P,Q,R) (for N>1) is decomposed into
  
  • moveplan(N-1,P,A,Q)
  • move(P,Q)
  • moveplan(N-1,A,Q,P)

whereas moveplan(1,P,Q,R) trivially becomes move(P,Q).

Question 2: For n=2 the solution takes 3 steps, for n=3 it takes 7 steps. Use the recursive relation above to find a formula for the length of the solution for an arbitrary n.

Question 3: For n=4 how many steps are required if, instead of 3 poles, we have 5 poles (a, b, c, d ,e) available?

• We will also make experiments with control rules. For instance, a general control rule is not to move the same disk two consecutive times.
  
  Question 4: if we implement this control rule, is there any variation in the execution time?
  
  
• Finally (optional), knowing the "moveplan" relation, we can completely fix the sequence of steps for the standard Tower of Hanoi problem. Use a predicate moveplan(N,P,Q,A,M,T) meaning "move N disks from P to Q using A as auxiliary pole, making M movements and starting at time point T" to unfold a sequence of facts "mustmove(P,Q,T)" meaning that the mandatory move a step T is move(P,Q). Include the following telingo constraint
  
  #program initial.
  :- mustmove(P,Q,T), not &tel{ T> move(P,Q) }.
  
  to enforce the movements
  
  Question 5: is there any difference in execution time?
  
  Question 6: if we allow 5 poles, is the plan obtained in this way still minimal?
  

Assessment and Delivery